CSCE 774 - Robotic Systems - Fall 2011

University of South Carolina

Instructor: Jason O'Kane

Tuesdays and Thursdays, 12:30-1:45pm, 300 Main Street, Room B102

About this course

This class is an introduction to some of the current research in robotics. Specifically, we will focus on planning algorithms, that is, computational techniques that robots can use to plan their future actions. After completing this course, you should be able to understand, critique, design, and implement planning algorithms for robots.

The format will mix lectures by the instructor and student-led discussions of important and interesting published research papers in the field.

Documents

Announcements

See all announcements

Homework

Due Date
Homework 1 Sep 20
Homework 2 Oct 18

Schedule

Past
Date Topic Other
Aug 18 1. What to expect from this course
1A. What is a robot?
1B. Basic ingredients of planning problems
syllabus, first-day survey
Aug 23 2. Discrete Deterministic Planning
2A. Notation
2B. Planning as graph search
Aug 25 2C. Planning with costs
3. Value iteration
3A. Determinisitc value iteration
Aug 30 3A. Determinisitc value iteration (examples, termination actions)
3B. Value iteration on continuous spaces
Sep 1 4. Unpredictable transitions
4A. Notation: A game against nature
4B. Nondeterministic value iteration
Sep 6 4C. Probabilistic value iteration
Sep 8 5. State uncertainty
5A. Initial conditions
5B. Sensing and observations
Sep 13 5C. Information spaces
Sep 15 5C. Information spaces (I-maps; derived I-states)
5D. Nondeterministic I-states (definition)
Sep 20 5D. Nondeterministic I-states (filtering)
Homework 1 due
Sep 22 5D. Nondeterministic I-states (filtering; examples)
Sep 27 Guest speaker: Nick Stiffler on visibility-based pursuit-evasion
Sep 29 Library time: Work on Homework 1
Oct 4 5E. Probabilistic I-states
Oct 6 Guest speaker: Jeremy Lewis on Minimalist Navigation. (Cancelled)
Oct 11 6. What are planning algorithms good for?
Oct 13 5E. Probabilistic I-states (updating; sufficient I-maps) Project: topic (due 10/14)
Oct 18 7. Planning with I-states Homework 2 due
Future
Oct 20 Fall break: No classes Project: related work
Oct 25 8. Reinforcement learning Quiz
Oct 27 Presentation 1: Distance-optimal navigation in an unknown environment without sensing distances. B. Tovar, R Murrieta, and S. M. LaValle. IEEE Transactions on Robotics, 23(3):506-518, June 2007. [pdf]

Presenter: Yang Song

Nov 1 Presentation 2: An Exploration of Sensorless Manipulation. M. A. Erdmann and M. T. Mason. IEEE Journal of Robotics and Automation, 4(4):369-379. 1988. [pdf]

Presenter: Jordan Bradshaw

Nov 3 Presentation 3: Landmark-Based Robot Navigation. A. Lazanas and J.-C. Latombe. Algorithmica 13(5):472-501, 1995. [pdf]

Presenter: Keith Haynes

Nov 8 Presentation 4: Simplicial Dijkstra and A* Algorithms for Optimal Feedback Planning. D. S. Yershov and S. M. LaValle IEEE/RSJ International Conference on Intelligent Robots and Systems, 2011. [pdf]

Presenter: Yang Song

Nov 10 Presentation 5: Shadow Information Spaces: Combinatorial Filters for Tracking Targets J. Yu and S. M. LaValle. IEEE Transactions on Robotics, to appear. [pdf]

Presenter: Keith Haynes

Nov 15 Presentation 6: Communication-Assisted navigation in robotic swarms F. Ducatelle, G. A. Di Caro, C. Pinciroli, F. Mondada, and L. Gambardella. IEEE/RSJ International Conference on Intelligent Robots and Systems, 2011. [pdf]

Presenter: Jordan Bradshaw

Nov 17 Presentation 7: Exploration and Map-Building under Uncertainty with Multiple Heterogeneous Robots. L. Munoz-Gomez, M. Alencastre-Miranda, R. Lopez-Padilla, and R. Murrieta-Cid. IEEE International Conference on Robotics and Automation, 2011. [pdf]

Presenter: Yang Song

Nov 22 Presentation 8: Effect of sensor and actuator quality on robot swarm algorithm performance. N. Hoff, R. Wood, and R. Nagpal IEEE/RSJ International Conference on Intelligent Robots and Systems, 2011. [pdf]

Presenter: Jordan Bradshaw

Project: progress report
Nov 24 Thanksgiving break: No classes
Nov 29 Presentation 9: The Multi-robot Coverage Problem for Optimal Coordinated Search with an Unknown Number of Robots. H. J. Min and N. Papanikolopoulos IEEE International Conference on Robotics and Automation, 2011. [pdf]

Presenter: Keith Haynes

Dec 1 Project presentations; Wrap-up; Evaluations Project: presentation
Dec 5-9 Exam week Project: exit interview
Project: final report (due 12/5)

Papers (not selected)

C: Randomization for Robot Tasks: Using Dynamic Programming in the Space of Knowledge States. M. Erdmann. Algorithmica 10:248-291. 1993. [pdf]

F: Simple Robots with Minimal Sensing: From Local Visibility to Global Geometry. S. Suri, E. Vicari, and P. Widmayer. [pdf]

J: A Differential Game Approach to Planning in Adversarial Scenarios: A Case Study on Capture-the-Flag. H. Huang, J. Ding, W. Zhang, and C. J. Tomlin IEEE International Conference on Robotics and Automation, 2011. [pdf]