Path planning in dynamic environments

Path planning plays an important role in various fields of application, such as CAD design, computer games and virtual environments, molecular biology, and robotics. In its most general form, the path planning problem is formulated as finding a collision-free path for a moving entity between a start and a goal configuration in an environment containing obstacles. This problem has extensively been studied in the past decades. Most of the effort has been spent on path planning in static environments. Those are environments in which all obstacles are stationary and do not move, and in which the positions and geometry of the obstacles are assumed to be known. Less attention has been given to path planning in dynamic environments, which contain moving obstacles in addition to stationary ones. Path planning in dynamic environments is the major topic of this thesis. We discuss several variants of the problem, including the cases in which we know the trajectories of the moving obstacles beforehand, and in which this information has to be acquired online, for instance by means of sensors