Generation of Sensory-Based Motion Strategies in the Presence of Uncertainty

TitleGeneration of Sensory-Based Motion Strategies in the Presence of Uncertainty
Publication TypeTechnical Report
AuthorsLatombe, J. - C.
NumberTR006
Date Published06/1988
Abstract

This paper addresses the problem of planning robot motions in the presence of uncertainty. It explores an approach to this problem, known as the preimage backchaining approach. Basically, a preimage is a region in space, such that if the robot executes a certain motion command from within this region, it is guaranteed to attain a target and to terminate into it. Preimage backchaining consists of reasoning backward from a given goal region, by computing preimages of the goal, and then recursively preimages of the preimages, until some preimages include the initial region where it is known at planning time that the robot will be before executing the motion plan. In the paper, we first give a rigorous formalization of the problem of planning motions in the presence of uncertainty; such a formalization is necessary because in many regards reasoning with uncertainty is not reducible to straightforward intuition. Then, we investigate in detail the theory of the preimage backchaining approach; we give a new presentation of preimages, we explore the notion of maximal preimages, and we extend the framework to the generation of conditional motion strategies. Finally, we describe a complete set of algorithms that makes it possible implementing the approach in a simplified two-dimensional world, which we call the mini-world. The restrictions imposed on the mini-world are essentially aimed at reducing the conceptual and computational complexity of the geometric computations required by the preimage backchaining approach. Nevertheless, the mini·world is still appropriate to handle realistic navigation problems with omni-directional mobile robots.

KeywordsMotion Planning, Planning in the Presence of Uncertainty, Preimage Backchaining, Robot Planning, Spatial Reasoning
Year of Publication1988
AttachmentSize
TR006.pdf3.5 MB

Last modified Tue, 29 Mar, 2011 at 14:20