Document Type

Technical Report

Department

Computer Science and Engineering

Publication Date

2008-01-01

Filename

wucse-2008-14.pdf

DOI:

10.7936/K7P26WBN

Technical Report Number

WUCSE-2008-14

Abstract

Traditional AI search methods, such as BFS, DFS, and A*, look for a path from a starting state to the goal in a state space most typically modelled as a directed graph. Prohibitively large sizes of the state space graphs make optimal search difficult. A key observation, as manifested by the SAS+ formalism for planning, is that most commonly a state-space graph is well structured as the Cartesian product of several small subgraphs. This paper proposes novel search algorithms that exploit such structure. The results reveal that standard search algorithms may explore many redundant paths. Our algorithms provide an automatic and mechanical way to remove such redundancy. Theoretically we prove the optimality and complexity reduction of the proposed algorithms. We further show that the proposed framework can accommodate classical planning. Finally, we evaluate our algorithms on various planning domains and report significant complexity reduction.

Comments

Permanent URL: http://dx.doi.org/10.7936/K7P26WBN

Download

Share

COinS