Motion planning with uncertainty: on the preimage backchaining approach

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.