Visible Decomposition: Real-Time Path Planning in Large Planar Environments

Abstract

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. 1 Introduction There is rapidly growing interest in the area of large-scale distributed simulations of physical systems. These simulations have many applications in planning, testing and training. In many cases, these simulations involve simulated agents that interact with human users. Producing these simulated agents requires solving many of the classic problems of artificial intelligence and robotics in environments that are more predictable than the "real world" but which are often very complex...