AE 498 MPA: Motion planning for aerospace vehicles

• University of Illinois at Urbana-Champaign
• Fall Semester, 2006
• Assistant Professor Tim Bretl

Note

• Online course reserves from the UIUC library are available here, from which you can download all of the required reading. Almost all of it came from the following databases, which can also be accessed from any on-campus computer:
• IEEE Xplore
• The International Journal of Robotics Research from Sage Publications.
• AIAA Electronic Library

Schedule (subject to change)

• Aug 24. Introduction.

• (Classical path planning)

• Aug 29. Configuration space and path planning (1).

• Aug 31. Configuration space and path planning (2).

• Sep 5. Configuration space and path planning (3).

• Sep 7. Probabilistic sampling-based planning.
• Kavraki, Svetska, Latombe, and Overmars. Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Transactions on Robotics and Automation, 12(4):566-580, 1996.
• Hsu, Latombe, and Kurniawati. On the probabilistic foundations of probabilistic roadmap planning. International Journal of Robotics Research, 25(7):627-643, July 2006. [SLIDES from Miles Johnson]

• (Kinodynamic motion planning)

• Sep 12. Kinodynamic motion planning: time-scaling
• Bobrow, Dubowsky, and Gibson. Time-optimal control of robotic manipulators along specified paths. International Journal of Robotics Research, 4(3):3-17, Fall 1985. -- or -- Shin and McKay. Minimum-time control of robotic manipulators with geometric path constraints. IEEE Transactions on Automatic Control, 30(6):531-541, June 1985. [SLIDES from David DeVon]
• Bobrow. Optimal robot path planning using the minimum-time criterion. IEEE Journal of Robotics and Automation, 4(4):443-450, August 1988. [SLIDES from Heather Arneson]

• Sep 14. Kinodynamic motion planning: sample-based
• Lavalle and Kuffner. Randomized kinodynamic planning. International Journal of Robotics Research, 20(5):378-400, May 2001. [SLIDES from Andres Ortiz]
• Hsu, Kindel, Latombe, and Rock. Randomized kinodynamic motion planning with moving obstacles. International Journal of Robotics Research, 21(3):233-255, March 2002. [SLIDES from Ian Kaufman]

• Sep 19. Kinodynamic motion planning: applications to aerospace
• Phillips, Kavraki, and Bedrossian. Spacecraft rendezvous and docking with real-time, randomized optimization. Proc. AIAA Guidance, Navigation, and Control Conference and Exhibit, 2003. [SLIDES from Heather Arneson]
• Cheng, Shen, and Lavalle. RRT-based trajectory design for autonomous automobiles and spacecraft. In Archives of Control Sciences, 11(3-4):167-194, 2001. (Detailed description of the application, if curious: Lu and Hanson. Entry guidance for the X-33 vehicle. Journal of Spacecraft and Rockets, 35(3):342-349, 1998.) [SLIDES from Miles Johnson]

• Sep 21. Computer lab day, 2-5pm.

• Sep 26. No class.

• (Kinodynamic motion planning using geometric control)

• Sep 28. Geometric control (basics of differential geometry)

• Oct 3. No class.

• Oct 5. Geometric control (nonholonomic systems) [SLIDES from Tim Bretl]

• Oct 10. Computer lab day, 2-5pm. [PRE-LAB] [M-FILE: twb_test.m] [M-FILE: twb_isfeasible_obst.m]

• Oct 12. Kinodynamic motion planning: controllability (Ian and David)
• Laumond, Jacobs, Taix, and Murray. A Motion Planner for a Nonholonomic Mobile Robot. IEEE Transactions on Automatic Control, 10(5):577-593, October 1994. [SLIDES from Ian Kaufman]
• Lynch. Controllability of a planar body with unilateral thrusters. IEEE Transactions on Automatic Control, 44(6):1206-1211, 1999. [SLIDES from David DeVon]

• Oct 17. Unmanned aerial vehicles: differential flatness and maneuvers (Tim and Miles)
• Nieuwstadt and Murray. Real time trajectory generation for differentially flat systems. International Journal of Robust and Nonlinear Control 18(11):995-1020, 1998.
• Frazzoli, Dahleh, and Feron. Real-time motion planning for agile autonomous vehicles. Journal of Guidance, Control, and Dynamics, 25(1):116-129, 2002. [SLIDES from Miles Johnson]

• (Multiple vehicles)

• Oct 19. No class.

• Oct 24. Computer lab day, 2-5pm. [PRE-LAB] [M-FILE: twb_makemovie.m]

• Oct 26. Multiple vehicles: classical techniques (coordination diagrams, de-/centralized planning) (Ian and David)
• O'Donnell and Lozano-Perez. Deadlock-Free and Collision-Free Coordination of Two Robot Manipulators. Proc. IEEE International Conference on Robotics and Automation, p484-489, 1989. [SLIDES from David DeVon]
• Clark. Probabilistic Road Map sampling strategies for multi-robot motion planning. Robotics and Autonomous Systems 53(3-4):244-264, December 2005. [SLIDES from Ian Kaufman]

• Oct 31. Multiple vehicles: optimization and air traffic control (Tim and Miles)
• Schouwenaars, Valenti, Feron, and How. Implementation and Flight Test Results of MILP-based UAV Guidance Aerospace, IEEE Aerospace Conference, 2005. -- and -- Frazzoli, Mao, Oh, and Feron. Resolution of Conflicts Involving Many Aircraft via Semidefinite Programming, Journal of Guidance, Control, and Dynamics, 24(1):79-86, 2001.
• Tomlin, Pappas, and Sastry. Conflict resolution for air traffic management: a study in multiagent hybrid systems. IEEE Transactions on Automatic Control, 43(4):509-521, April 1998. [SLIDES from Miles Johnson]

• (Legged vehicles)

• Nov 2. Legged vehicles: quasi-static motion planning
• Bretl. Motion planning of multi-limbed robots subject to equilibrium constraints: the free-climbing robot problem. International Journal of Robotics Research, 25(4):317-342, 2006.
• Hauser, Bretl, Latombe, and Wilcox. Motion planning for a six-legged lunar robot. WAFR 2006.

• Nov 7. Computer lab day, 2-5pm. [PRE-LAB] [M-FILE: twb_shortpath.m]

• (Sensing and other practical considerations)

• Nov 9. Recursive state estimation.

• Nov 14. Probabilistic localization and mapping.
• Thrun. Robotic mapping: a survey. In Lakemeyer and Nebel, editors, Exploring Aritificial Intelligence in the New Millenium, Morgan Kaufmann, 2002.

• Nov 16. Integrated sensing. (Ian and David)
• J. Langelaan and S. Rock. Towards Autonomous UAV Flight in Forests, AIAA Guidance, Navigation, and Control Conference and Exhibit, San Francisco, California, Aug. 15-18, 2005. [SLIDES from Ian Kaufman]
• Anthony Stentz. Optimal and Efficient Path Planning for Partially-Known Environments. Proc. IEEE International Conference on Robotics and Automation, 1994. -- and -- Anthony Stentz. The Focussed D* Algorithm for Real-Time Replanning. Proc. International Joint Conference on Artificial Intelligence, 1995. [SLIDES from David DeVon]

• Nov 21, 23. No class. (Happy Thanksgiving!)

• Nov 28. Mars rovers (Tim and Miles)
• Biesiadecki, Leger, and Maimone. Tradeoffs between directed and autonomous driving on the Mars Exploration Rovers. Proc. Int. Symp. of Robotics Research, 2005.
• J. Biesiadecki, et al. Mars Exploration Rover Surface Operations: Driving Opportunity at Meridiani Planum. Proc. IEEE Systems, Man, and Cybernetics, 2005. -- and -- C. Leger, et al, Mars Exploration Rover Surface Operations: Driving Spirit at Gusev Crater, Proc. IEEE Systems, Man, and Cybernetics, 2005. [SLIDES from Miles Johnson]

• Nov 30. DARPA grand challenge (Ian and David)
• Stentz et al. Toward Reliable Off Road Autonomous Vehicles Operating in Challenging Environments. International Journal of Robotics Research, 25(5-6):449-483, May-June 2006. [SLIDES from David DeVon]
• Thrun et al. Winning the DARPA Grand Challenge, Journal of field Robotics, 2006, to appear. [SLIDES from Ian Kaufman]

• Dec 5-7. Final project presentations (in class).