Tractable Class of a Problem of Goal Satisfaction in Mutual Exclusion Network

All Papers

In this paper we describe a class of a problem of goal satisfaction in mutual exclusion network that can be solved in polynomial time. This problem provides a common basis for reasoning about various tasks known from artificial intelligence. Namely, tasks arising during construction of concurrent solutions for planning problems and Boolean formula satisfaction can be viewed as problems of goal satisfaction. We experimentally compared a solving algorithm which exploits the defined tractable class with backtracking enhanced by maintaining consistencies on random problems and on problems arising in concurrent planning. We obtained significant speedups in both experimental setups.