Open Collections

The pairwise heuristic : a method for treating uncertainty in planning and robot localization

University of British Columbia

One of the major challenges in the field of Artificial Intelligence is dealing with uncertainty. Finding the optimal solution in the presence of uncertainty is computationally quite costly. This makes it impossible to solve large problems. In this thesis, we propose a new heuristic, named the pairwise heuristic, which efficiently finds a near-optimal solution for such problems. The pairwise heuristic is based on optimal solutions for the pairs of states. For each pair, it solves the problem assuming that the uncertainty exists only between the two states of the pair. A greedy online strategy uses these solutions to solve the main problem. We tested the pairwise heuristic on two problems where uncertainty plays a major role, i.e., localization and planning under uncertainty. Our achievements in connection with both problems are novel in their respective fields. In the field of localization, we have developed an efficient method to localize a robot in any kind of environment in a fully autonomous way. In the field of planning under uncertainty, our method finds a near-optimal solution in a time shorter than the time required by any other current method in the field.

Text

2012-12-21

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/43747

Computer Science

University of British Columbia

UBCV

http://creativecommons.org/licenses/by-nc-nd/4.0/