Abstract

Abstract: Many real-world combinatorial problems exhibit structure in the way in which their variables interact. Such structure can be exploited in the form of 'factors' for representational as well as computational benefits. Factored representations are extensively used in probabilistic reasoning, constraint satisfaction, planning, and decision theory. In this paper, we formulate the factored shortest path problem (FSPP) on a collection of constraints interpreted as factors of a high-dimensional map. We show that the FSPP is not only a generalization of the regular shortest path problem but also particularly relevant to robotics. We develop factored-space heuristics for A* and prove that they are admissible and consistent. We provide experimental results on both random and hand-crafted instances as well as on an example robotics domain to show that A* with factored-space heuristics outperforms A* with the Manhattan Distance heuristic in many cases.

Download the paper in pdf.

Many publishers do not want authors to make their papers available electronically after the papers have been published. Please use the electronic versions provided here only if hardcopies are not yet available. If you have comments on any of these papers, please send me an email! Also, please send me your papers if we have common interests.

This page was automatically created by a bibliography maintenance system that was developed as part of an undergraduate research project, advised by Sven Koenig.