State Space Abstraction in Artificial Intelligence and Operations Research

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.