On-line motion planning

Candidate: Cox,James L.

Abstract

In this thesis we investigate the area of online or exploratory motion planning. In this thesis we develop algorithms for planning the motion of a planar rod or ladder and a three link planar arm moving amidst an environment containing obstacles bounded by simple, closed polygons. The exact shape, number and location of the obstacles is assumed unknown to the planning algorithm, which can only obtain information about the obstacles by detecting points of contact with the obstacles. The ability to detect contact with obstacles is formalized by move primitives that we call guarded moves. We call ours the online motion planning problem as opposed to the usual offline version. This is a significant departure form the usual setting for motion planning problems, in which the algorithm is given an explicit description of the scene as part of its input. What we demonstrate is that the retraction method can be applied, although new issues arise that have no counterparts in the usual setting. For the rod we are able to obtain an algorithm with path complexity ($O(m) = O(n\sp2)$ guarded moves, where $n$ is the number of obstacle walls, and $m$ the number of pairs of obstacle walls and corners of distance less than or equal to the length of the ladder) that matches the known lower bound (Ork85). This lower bound holds for both the online and offline (where the environment is explicitly given) versions of the problem. The computational complexity of the algorithm $O(m$ log $n)$ matches the best known algorithm (SfS) for the offline version. For the arm we are able to obtain an algorithm with path complexity that is $O(m) = O(n\sp3)$ where $n$ is the number of obstacle walls and $m$ is the number of pairs of obstacle features that the linkage can simultaneously contact. The computational complexity is $O(n\sp3$log $n$). Also our constraint based approach can be extended to obtain algorithms for $k > 3$ link arms that are polynomial for each $k$. That is, if $k$ is fixed the complexity is proportional to $n\sp{k}$.