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

Pavel Surynek

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.

Subjects: 1.11 Planning; 15.2 Constraint Satisfaction

Submitted: Feb 24, 2008

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.