We describe a method called Visible Decomposition for computing collision-free paths in real time through a planar environment with a large number of obstacles. This method divides space into local visibility graphs, ensuring that all operations are local. The search time is kept low since the number of regions is proved to be small. We analyze the computational demands of the algorithm and the quality of the paths it produces. In addition, we show test results on a large simulation testbed.
Identifer | oai:union.ndltd.org:MIT/oai:dspace.mit.edu:1721.1/5935 |
Date | 01 June 1998 |
Creators | Maron, Oded, Lozano-Perez, Tomas |
Source Sets | M.I.T. Theses and Dissertation |
Language | en_US |
Detected Language | English |
Format | 17 p., 689951 bytes, 641831 bytes, application/postscript, application/pdf |
Relation | AIM-1638 |
Page generated in 0.0014 seconds