This page contains, code, domain challenge problems, and experimental results for ongoing work on PPLAN, a best-first search planner for planning with rich user preferences that was developed at the University of Toronto.

Contributors

Meghyn Bienvenu
Sheila McIlraith
Shirin Sohrabi Araghi
Christian Fritz

Overview

PPLAN is a provably optimal best-first search planner for planning with non-Markovian qualitative preferences.

Work on PPLAN was first reported in the paper Specifying and Generating Preferred Plans, by Bienvenu and McIlraith. More recent citations are included below. Contributions include:

• A first-order language for specifying non-Markovian qualitative (user) preferences over possible plans, and
• A best-first search planner together with theoretical results on the correctness and optimality of the algorithm.

PPLAN is an optimal best-first forward-chaining planner that generates a plan that not only achieves a user-defined goal, but that also conforms, where possible, to a user's preferences. PPLAN uses progression to more efficiently evaluate preference formulae.

PPLAN takes as input, an action theory, a specification of the initial state of the system, a preference formula, and a goal.

Language Syntax

To specify preferences for planning, we appeal to a first-order preference language defined in Planning with Qualitative Temporal Preferences. Details of the syntax of the language can be found in this paper.

Implementation

PPLAN is implemented in Prolog. Users must provide a plan horizon (length bound). PPLAN evaluates partial plans optimistically. As such it uses an admissible evaluation function with best-first search.

You can find code, test cases and experimentals results by clicking on the relevant link that follows.

• pplan.pl: This is the main PPLAN interpreter. This files uses computeWeights.pl.
• computeWeights.pl: This module calculates the weights and progressions of preferences.

Test Cases

As an example we provide the dinner domain, specified in the following Prolog (e.g. XSB) files:

• dinner.pl

PPLAN has been tested on 60 instances of the dinner domain:

• Test cases for the dinner example

Experimental Results

We have proved that our algorithm will find the plan that optimizes the user's preferences. To evaluate the effectiveness of our heuristic in pruning search, we compared the number of nodes expanded or considered by PPLAN to the equivalent breadth-first planner. The results are given here:

• Results for the dinner domain

• bfs.pl: This is the main BFS implementation file. This files uses computeWeightsBFS.pl.
• computeWeightsBFS.pl: This module assigns weights to partial plans in a way that emulates breadth-first search.

References

The principle references for PPLAN are the following:

[1] M. Bienvenu and S. McIlraith. Specifying and Generating Preferred Plans. Working Notes of the Seventh International Symposium on Logical Formalizations of Commonsense Reasoning, May 2005, Kerkyra, Greece.

[2] M. Bienvenu and S. McIlraith. Qualitative Dynamical Preferences in the Situation Calculus. Proceedings of the IJCAI-05 Multidisciplinary Workshop on Advances in Preference Handling, July 31, 2005.

[3] M. Bienvenu and C. Fritz and S. McIlraith Planning with Qualitative Temporal Preferences. Proceedings of the 10th International Conference on Principles of Knowledge Representation and Reasoning (KR06), June 2006, Lake District, UK

[4] M. Bienvenu and C. Fritz and S. McIlraith Specifying and Computing Preferred Plans. Artificial Intelligence, 175(7-8): 1308-1345. 2011.

The closest related work is that of Son and Pontelli:

[5] T. Son and E. Pontelli. Planning with preferences using logic programming. In Proc. LPNMR 2004, pages 247-260. 2004.

Code and examples for Son and Pontelli's planner can be found here.

[6] C. Fritz and S. McIlraith. Decision-Theoretic GOLOG with Qualitative Preferences. Proceedings of the 10th International Conference on Principles of Knowledge Representation and Reasoning (KR06), June 2006, Lake District, UK