Path planning in changeable environments

摘要

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