Using SAT and Logic Programming to Design Polynomial-Time Algorithms for Planning in Non-Deterministic Domains

Chitta Baral, Thomas Eiter, Jicheng Zhao

We show that a Horn SAT and logic programming approach to obtain polynomial time algorithms for problem solving can be fruitfully applied to finding plans for various kinds of goals in a non-deterministic domain. We particularly focus on finding weak, strong, and strong cyclic plans for planning problems, as they are the most studied ones in the literature. We describe new algorithms for these problems and show how non-monotonic logic programming can be used to declaratively compute strong cyclic plans. As a further benefit, preferred plans among alternative candidate plans may be singled out this way. We give complexity results for weak, strong, and strong cyclic planning. Finally, we briefly discuss some of the kinds of goals in non-deterministic domains for which the approach in the paper can be used.

Content Area: 10. Knowledge Representation & Reasoning

Subjects: 11. Knowledge Representation; 1.11 Planning

Submitted: May 10, 2005

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.