Technical reports

Planning with preferences using maximum satisfiability

Richard A. Russell

October 2012, 160 pages

This technical report is based on a dissertation submitted September 2011 by the author for the degree of Doctor of Philosophy to the University of Cambridge, Gonville and Caius College.

DOI: 10.48456/tr-822

Abstract

The objective of automated planning is to synthesise a plan that achieves a set of goals specified by the user. When achieving every goal is not feasible, the planning system must decide which ones to plan for and find the lowest cost plan. The system should take as input a description of the user’s preferences and the costs incurred through executing actions. Goal utility dependencies arise when the utility of achieving a goal depends on the other goals that are achieved with it. This complicates the planning procedure because achieving a new goal can alter the utilities of all the other goals currently achieved.

In this dissertation we present methods for solving planning problems with goal utility dependencies by compiling them to a variant of satisfiability known as weighted partial maximum satisfiability (WPMax-SAT). An optimal solution to the encoding is found using a general-purpose solver. The encoding is constructed such that its optimal solution can be used to construct a plan that is most preferred amongst other plans of length that fit within a prespecified horizon. We evaluate this approach against an integer programming based system using benchmark problems taken from past international planning competitions.

We study how a WPMax-SAT solver might benefit from incorporating a procedure known as survey propagation. This is a message passing algorithm that estimates the probability that a variable is constrained to be a particular value in a randomly selected satisfying assignment. These estimates are used to influence variable/value decisions during search for a solution. Survey propagation is usually presented with respect to the satisfiability problem, and its generalisation, SP(y), with respect to the maximum satisfiability problem. We extend the argument that underpins these two algorithms to derive a new set of message passing equations for application to WPMax-SAT problems. We evaluate the success of this method by applying it to our encodings of planning problems with goal utility dependencies.

Our results indicate that planning with preferences using WPMax-SAT is competitive and sometimes more successful than an integer programming approach – solving two to three times more subproblems in some domains, while being outperformed by a smaller margin in others. In some domains, we also find that using information provided by survey propagation in a WPMax-SAT solver to select variable/value pairs for the earliest decisions can, on average, direct search to lower cost solutions than a uniform sampling strategy combined with a popular heuristic.

Full text

PDF (2.0 MB)

BibTeX record

@TechReport{UCAM-CL-TR-822,
  author =	 {Russell, Richard A.},
  title = 	 {{Planning with preferences using maximum satisfiability}},
  year = 	 2012,
  month = 	 oct,
  url = 	 {https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-822.pdf},
  institution =  {University of Cambridge, Computer Laboratory},
  doi = 	 {10.48456/tr-822},
  number = 	 {UCAM-CL-TR-822}
}