AAAI Publications, Workshops at the Twenty-Ninth AAAI Conference on Artificial Intelligence

Font Size: 
State Space Abstraction in Artificial Intelligence and Operations Research
Robert C. Holte, Gaojian Fan

Last modified: 2015-04-01


In this paper we compare the abstraction methods used for state space search and planning in Artificial Intelligence with the state space relaxation methods used in Operations Research for various optimization problems such as the Travelling Salesman problem (TSP). Although developed independently, these methods are based on exactly the same general idea: lower bounds on distances in a given state space can be derived by computing exact distances in a ``simplified" state space. Our aim is to describe these methods so that the two communities understand what each other has done and can begin to work together.

Full Text: PDF