Considers the issues involved in writing path planners that can work well with complex geometric models of robots and workspaces, and outline the authors' work in implementing a solution. The authors' claim that many path planning problems can be solved by a mixture of global and local planning. In turn, local planning can be usefully supported by the provision of efficient distance computations, and the authors describe a variation on the algorithm of Gilbert, Johnson and Keerthi (1988), that they have packaged together with a hierarchical decomposition of objects for added efficiency. Global planning requires more domain-dependent techniques, but the authors have been experimenting with approximations to the generalised Voronoi diagram, and results for this system are shown using a path planner based on the authors' method of virtual springs.
展开▼