This thesis addresses path planning in changeable environments. In contrast to traditional path planning that deals with static environments, in changeable environments objects are allowed to change their configurations over time. In many cases, path planning algorithms must facilitate quick answers to queries in order to be useful. For example, an opponent in a training simulation needs to respond to the actions of the user without any significant delay. To achieve such performance, path planning methods usually use a preprocessing phase in which the environment is explored. As much computation time as possible is moved to this preprocessing phase such that at query time only little time is needed to solve an actual path planning query. This approach has led to many successful methods that are applicable to a broad range of problems.
Because of the nature of preprocessing, existing methods have difficulty to cope with unanticipated changes that occur in the environment in a later stage. Often existing solutions are computationally expensive and may fail if no local solution exists.
This thesis presents novel results for path planning in changeable environments. It is divided in three parts. The first part deals with the class of problems in which obstacles can change their configuration between the time the roadmap was created and the query. Examples of such obstacles are doors, chairs and boxes. We provide an algorithm that is able to deal with such changes in the environment while keeping the planning process efficient.
The second part deals with environments in which robots have the ability to manipulate obstacles that block their path. Imagine, for example a simulation in which a firefighter commander is trained. The commander gives his (virtual) firefighters higher level commands (e.g. ``walk around the building and enter it at the back''). For a realistic training, the firefighters should be able to move away obstacles that block their paths in order to, for example, clear the door. The algorithms in this part describe a novel way to deal with this type of problems by imitating human behavior.
Finally, the third part deals with the problem of a robot pushing a disk in a polygonal environment. Pushing an object by a robot is often easier or more applicable than pulling since it does not involve grasping the object. A robot arm can push an object using a single finger while pulling involves more complicated behavior. Unfortunately in addition to the usual sensor errors, pushing is also sensitive to another type of uncertainty; if the object's center of mass is not exactly known then pushing an object leads to erratic behavior leading to unstable pushes. We provide solutions that are robust against sensor errors and therefore are more suited to be used in practical problems.