State space search with prioritised soft constraints

This paper addresses two issues: how to choose between solutions for a prob lem specified by multiple criteria, and how to search for solutions in such situations. We argue against an approach common in decision theory, reduci ng several criteria to a single 'cost' (e.g., using a weighted sum cost fun ction) and instead propose a way of partially ordering solutions satisfying a set of prioritised soft constraints. We describe a generalisation of the A* search algorithm which uses this ordering and prove that under certain reasonable assumptions the algorithm is complete and optimal.