Efficient path planning in changing environments

This paper addresses the problem of path planning in environments in which some of the obstacles can change their positions. It uses the popular PRM method for navigating a robot through an environment. One of the key features of PRM is that it moves the major part of the calculations involved in the path planning process to the preprocessing phase. After that, paths can be extracted very quickly (in a query phase) usually without any noticeable delay. While very successful in many applications, doing most of the work in a preprocessing phase restricts the environment to be static i. e. obstacles are not allowed to change their configurations after the preprocessing phase. In this paper we describe and evaluate an algorithm based on PRM that does allow obstacles to change their configuration after preprocessing while still allowing for a quick query phase.

Authors

• Dennis Nieuwenhuisen
• Jur van den Berg
• Mark H. Overmars

Keywords

• Path planning
• Robustness
• Sampling methods
• Intelligent robots
• USA Councils
• Navigation
• Delay
• Road accidents
• Boolean functions
• Environmental Changes
• Environmental Planning
• Preprocessing Phase
• Running Time
• Free Space
• Computationally Intractable
• Boolean Logic
• Straightforward Method
• Collision Detection
• Fast Phase
• Simple Environment
• Query Time
• Static Obstacles
• Rapidly-exploring Random Tree