Discrete models for robot path planning
Shermane Annette Austin · 1993
Our purpose in this work is to investigate the applications of discrete models for a restricted class of robot-planning problems. A high-level planner is formulated that uses the structural characteristics of workcell configurations as a basis for path-planning. The planner also provides a logical framework for representing and reasoning about positional information with procedural interfaces for processing descriptions of objects and robots in the workcell, and the low-level details of motion control. We begin with a discussion of domain-independent planners and explore some of the special requirements for robot planning. Following this discussion, we develop and formulate a poset-based model. Motivated by investigations undertaken by Thuk-Air et al of k-directional relations, we use restricted directional posets to capture the underlying properties of objects in workcell configurations. We extend Thuk-Air's formulation of bi-directional relations by showing how arbitrary finite posets can be expanded to obtain bi-directional relations. We then further define and characterize a restricted class of directional posets, $k\sb2$ and $quad\sb2$, to better approximate motion-planning in a high-level planner. We also formulate a class of posets, goal posets, as a basis for goal-directed path-planning analysis. This analysis together with the directed relation induced by a given configuration allows us to determine whether or not the objects can be moved in a straight line to their goal locations. Finally, a directional logic is defined, using the directional posets as a basis for control. We illustrate its implementation with separability problems involving restricted direction assignments. Concurrent planning is also discussed and explored in these examples.