Cost-optimal planning using weighted MaxSAT

Nathan Robinson; Charles Gretton; Duc Nghia Pham; Abdul Sattar

Cost-optimal planning using weighted MaxSAT

Nathan Robinson^*, Charles Gretton, Duc Nghia Pham, Abdul Sattar

^*Corresponding author for this work

Research output: Contribution to conference › Paper › peer-review

4 Citations (Scopus)

Abstract

We consider the problem of computing optimal plans for propositional planning problems with action costs. In the spirit of leveraging advances in general-purpose automated reasoning for that setting, we develop an approach that operates by solving a sequence of partial weighted MaxSAT problems, each of which corresponds to a step-bounded variant of the problem at hand. Our approach is the first SAT-based system in which a proof of cost optimality is obtained using a MaxSAT procedure. It is also the first system of this kind to incorporate an admissible planning heuristic. We perform a detailed empirical evaluation of our work using benchmarks from a number of International Planning Competitions.

Original language	English
Pages	14-22
Number of pages	9
Publication status	Published - 2010
Externally published	Yes
Event	Workshop on Constraint Satisfaction Techniques for Planning and Scheduling Problems, COPLAS 2010 - Toronto, ON, Canada Duration: 12 May 2010 → 12 May 2010

Conference

Conference	Workshop on Constraint Satisfaction Techniques for Planning and Scheduling Problems, COPLAS 2010
Country/Territory	Canada
City	Toronto, ON
Period	12/05/10 → 12/05/10

Cite this

@conference{196a40af952c488a8dac6c1d92e433e1,

title = "Cost-optimal planning using weighted MaxSAT",

abstract = "We consider the problem of computing optimal plans for propositional planning problems with action costs. In the spirit of leveraging advances in general-purpose automated reasoning for that setting, we develop an approach that operates by solving a sequence of partial weighted MaxSAT problems, each of which corresponds to a step-bounded variant of the problem at hand. Our approach is the first SAT-based system in which a proof of cost optimality is obtained using a MaxSAT procedure. It is also the first system of this kind to incorporate an admissible planning heuristic. We perform a detailed empirical evaluation of our work using benchmarks from a number of International Planning Competitions.",

author = "Nathan Robinson and Charles Gretton and Pham, \{Duc Nghia\} and Abdul Sattar",

year = "2010",

language = "English",

pages = "14--22",

note = "Workshop on Constraint Satisfaction Techniques for Planning and Scheduling Problems, COPLAS 2010 ; Conference date: 12-05-2010 Through 12-05-2010",

}

TY - CONF

T1 - Cost-optimal planning using weighted MaxSAT

AU - Robinson, Nathan

AU - Gretton, Charles

AU - Pham, Duc Nghia

AU - Sattar, Abdul

PY - 2010

Y1 - 2010

N2 - We consider the problem of computing optimal plans for propositional planning problems with action costs. In the spirit of leveraging advances in general-purpose automated reasoning for that setting, we develop an approach that operates by solving a sequence of partial weighted MaxSAT problems, each of which corresponds to a step-bounded variant of the problem at hand. Our approach is the first SAT-based system in which a proof of cost optimality is obtained using a MaxSAT procedure. It is also the first system of this kind to incorporate an admissible planning heuristic. We perform a detailed empirical evaluation of our work using benchmarks from a number of International Planning Competitions.

AB - We consider the problem of computing optimal plans for propositional planning problems with action costs. In the spirit of leveraging advances in general-purpose automated reasoning for that setting, we develop an approach that operates by solving a sequence of partial weighted MaxSAT problems, each of which corresponds to a step-bounded variant of the problem at hand. Our approach is the first SAT-based system in which a proof of cost optimality is obtained using a MaxSAT procedure. It is also the first system of this kind to incorporate an admissible planning heuristic. We perform a detailed empirical evaluation of our work using benchmarks from a number of International Planning Competitions.

UR - https://www.scopus.com/pages/publications/84857813165

M3 - Paper

AN - SCOPUS:84857813165

SP - 14

EP - 22

T2 - Workshop on Constraint Satisfaction Techniques for Planning and Scheduling Problems, COPLAS 2010

Y2 - 12 May 2010 through 12 May 2010

ER -

Cost-optimal planning using weighted MaxSAT

Abstract

Conference

Other files and links

Fingerprint

Cite this