On-Line Computation Distribution Architecture

Stanford University

Research Goal

The ultimate goal of our investigation, concerning the two problem domains mentioned above, is to both provide real-time controllers with on-line motion reactive planning capabilities and build experimental robotic systems demonstrating such capabilities. Moreover, in accomplishing this goal, we expect to elaborate general guidelines for embedding a capability requiring provably complex computations into a real-time framework.

People

• Jean-Claude Latombe, Professor (latombe@cs.stanford.edu)
• Tsai-Yen Li, PhD Student (li@flamingo.stanford.edu)
• Yotto Koga, PhD Student (yotto@flamingo.stanford.edu)
• Lydia Kavraki, PhD Student (kavraki@flamingo.stanford.edu)
• Craig Becker, PhD Student (cdb@cs.stanford.edu)
• Joaquin Salas, Visiting Scholar (salas@flamingo.stanford.edu)
• Ken Tokusei, MSCS Student (tokusei@cs.stanford.edu)
• Mark Yim, PhD Student (mark@flamingo.stanford.edu)
• Anthony Lazanas, PhD Graduate (lazanas@flamingo.stanford.edu)
• David Zhu, Post-Doc (zhu@cs.stanford.edu)

Subtopics

• Distribution of Path Planning, (Tsai-Yen Li)
• Parallelization of Path Planning, (Lydia Kavraki)
• New Methods for Fast Path Planning, (Tsai-Yen Li)
• Multi-Arm Manipulation Planning, (Yotto Koga)
• Experiments in Manipulation Planning, (Tsai-Yen Li)
• Landmark-Based Navigation (A. Lazanas, K. Tokusei)
• Mobile Robot Navigation Toolkits, (Craig Becker, Mark Yim and David Zhu)
• Multi-Mobile Robot Simulator, (Craig Becker and David Zhu)

Summary of Main Results Obtained So Far

• Identification of several axes for distributing path planning software in an on-line architecture.
• A documented Randomized Path Planner package has been made available to other research institution on the computer network. Several organizations are using it.
• Implementation of parallel versions of RPP on a Silicon Graphics 4D/240 multiprocessor machine and on a local-area network of UNIX-based workstations.
• Definition of a new, FFT-based method to compute obstacles in configuration space.
• Definition and implementation of a new path planning method (the vector-based planner) to generate paths for robots with many degrees of freedom.
• Integration of several path planners (RPP, vector-based planner with/with out potential fields) in a package distributed over a network of UNIX-based workstations.
• Design and implementation of an optimal-time motion planner for closed-loop kinematic chains.
• Preliminary implementation of a randomized three-arm manipulation planner for manipulating an elongated object in a cluttered environment.
• Design and implementation of a new landmark-based mobile robot planning method. Extension of this planner to deal with controllable uncertainty.
• Definition of the layout of a software toolkit to efficiently develop new navigation systems. Implementation of several toolkits.
• Partial development of a powerful multi-mobile-robot simulator to facilitate the development and debugging of programs for multiple interacting mobile robots .

Publications:

• Y. Koga and J.C. Latombe, "Experiments in Dual-Arm Manipulation Planning," Proc. of the IEEE Int. Conf. on Robotics and Automation, Nice, May 1992, pp. 2238--2245.
• Y. Koga, T. Lastennet, J.C. Latombe, and T.Y. Li, "Multi-Arm Manipulation Planning," Proc. of the 9th Int. Symp. on Automation and Robotics in Construction, Tokyo, June 1992.
• A. Lazanas and J.C. Latombe, Landmark-Based Robot Navigation, Rep. No. STAN-CS-92-1428, Dept. of Computer Science, Stanford U., May 1992.
• A. Lazanas and J.C. Latombe, "Landmark-Based Robot Navigation," Proc. of the 10th Nat. Conf. on Artificial Intelligence, AAAI-92, San Jose, July 1992, pp. 816--822.
• A. Lazanas and J.C. Latombe, "Landmark-Based Robot Motion Planning," Proc. of the AAAI Fall Symp., Boston, MA. October 1992, pp. 98-103.
• L. Kavraki, Computation of Configuration-Space Obstacles Using the Fast Fourier Transform, Technical Report, STAN-CS-92-1425, 1992.

Acknowledgment: