This paper describes a hierarchial system for dynamic planning and scheduling among a field of moving obstacles. The solution is directly applicable to many autonomous scenarios, such as movement on a manufacturing floor, navigation of surface/subsurface ships or coordination of air traffic. The overall system is discussed in terms of global/local perception and generative planning/reactive control. The development and implementation of the generative planner portion of the existing system are described in detail. In terms of real-time system performance, the multi-dimensional search problem is made tractable by applying two dependent 2D techniques in series. First, the shortest distance, obstacle-avoiding path to the goal is calculated, then for that path, the time to the goal is optimized. In this space-time representation of the domain, time requirements can be imposed upon the goal(s) and therefore scheduling can also be accomplished.

Date Published: 8 January 1999
PDF: 8 pages
Proc. SPIE 3525, Mobile Robots XIII and Intelligent Transportation Systems, (8 January 1999); doi: 10.1117/12.335699

Published in SPIE Proceedings Vol. 3525:
Mobile Robots XIII and Intelligent Transportation Systems
Howie M. Choset; Pushkin Kachroo; Mikhail A. Kourjanski; Douglas W. Gage; Pushkin Kachroo; Marten J. de Vries; Mikhail A. Kourjanski; Marten J. de Vries, Editor(s)