Bounded Uncertainty Roadmaps

Abstract

In this thesis, we give algorithms to plan the motion of the robot when the position and shapes of the obstacles are not known precisely, as well as these obstacles can change dynamically over time. These changes could be to the number of obstacles, their shape, as well as to their position.

The Robot Motion Planning problem is: Find a valid sequence of actions of the robot, taking it to the given goal configuration, while avoiding collisions with obstacles. Probabilistic Roadmaps (PRMs) are state-of-art motion planners solving many hard problems. PRMs make a graph (roadmap) in the free-space of the robot, and then search for the shortest path in the roadmap from source to goal. However classical PRMs assume that the environment is known with perfect accuracy, and does not change over time. These assumptions are not true in practice.

We first give the Bounded Uncertainty Roadmap (BURM), extending PRMs to the case when the environment is not known with perfect accuracy: The coordinates of obstacle vertices are now specified via probability distributions, <em>f(v)</em>. The novelty in BURM is that we do not compute the exact probabilities of collision at robot configurations, but only maintain rough bounds on them. Bounds are refined to different degrees of resolution in different parts of the configuration space of the robot, depending on their relevance in finding the best path through the roadmap. This makes BURM quite efficient. Part of these refinements are performed by a hierarchical subdivision of the geometry of the robot and obstacles, and computing probabilities of collision over these subdomains; while part of it is achieved using Monte Carlo Integration.

We extend BURM to give the Dynamic BURM (DBURM). Now the environment can change dynamically, which we model by changing <em>f(v)</em>. After every change, a certain `local consistency condition? may be violated at some nodes in the roadmap. DBURM identifies the non-consistent nodes and iteratively makes them consistent. Once all nodes are consistent, the shortest path is easy to compute. DBURM is shown to be more efficient than re-running BURM after every change. Similar re-planning algorithms existed before, but not for the case when edges in the roadmap are annotated by cost bounds. This is different and more challenging.

Suppose the expected costs of edges, <em>c(e)</em>, in a graph are unknown. We can not always compute definite bounds on <em>c(e)</em> as above, but by sampling the costs we can compute an interval that contains <em>c(e)</em> with a high probability. In such a case we can only return a path that is optimal with a high probability. We give the Probably Approximately Correct BURM (PACBURM) that makes a further small sacrifice while making a large gain in efficiency: PACBURM returns a path that with a high probability is <em>close in cost</em> to the optimal path. Hence PACBURM returns a <em>probably approximately optimal</em> path. We do not know of any other graph algorithm in AI literature that computes a probably approximately optimal path in such a setting.