Using probabilistic roadmaps in changing environments

ABSTRACT In this paper, we examine how a path planning problem can be solved in changing environments using probabilistic roadmap planners. A probabilistic roadmap is built in static environment where all obstacles are known in advance, but we show that a roadmap can be built in such a way that it works well even when new obstacles are added to the workspace. However, our experiments show that the roadmap graph must be built carefully. We compare three different methods that are used to decide which edges are added to the roadmap graph to connect the nodes. One of these is a distance‐based method, which we present in this paper. In the tests, we built a roadmap by using only the static obstacles. Then, we added additional obstacles to the environment and tested how well the roadmap still worked. The tests showed that our distance‐based method worked quickly and that it produced roadmaps, which could be used to find a path amid additional obstacles with a high success rate.Copyright © 2013 John Wiley & Sons, Ltd.