A meta-CSP model for optimal planning

Peter Gregory; Derek Long; Maria Fox; W. Ruml; I. Miguel

A meta-CSP model for optimal planning

Peter Gregory, Derek Long, Maria Fox, W. Ruml (Editor), I. Miguel (Editor)

Computer And Information Sciences

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

5 Citations (Scopus)

22 Downloads (Pure)

Abstract

One approach to optimal planning is to first start with a sub-optimal solution as a seed plan, and then iteratively search for shorter plans. This approach inevitably leads to an increase in the size of the model to be solved.We introduce a reformulation of the planning problem in which the problem is described as a meta-CSP, which controls the search of an underlying SAT solver. Our results show that this approach solves a greater number of problems than both Maxplan and Blackbox, and our analysis discusses the advantages and disadvantages of searching in the backwards direction.

Original language	English
Pages	200-214
Number of pages	14
Publication status	Published - 2007
Event	Seventh Symposium on Abstraction, Reformulation and Approximation (SARA) - Whistler, Canada Duration: 18 Jul 2007 → 21 Jul 2007

Conference

Conference	Seventh Symposium on Abstraction, Reformulation and Approximation (SARA)
City	Whistler, Canada
Period	18/07/07 → 21/07/07

Keywords

meta-CSP
optimal planning
maxplan
blackbox

Access to Document

strathprints003423Accepted author manuscript, 272 KB

Cite this

@conference{6d73c38c482548bebf3127f7a8bb60ae,

title = "A meta-CSP model for optimal planning",

abstract = "One approach to optimal planning is to first start with a sub-optimal solution as a seed plan, and then iteratively search for shorter plans. This approach inevitably leads to an increase in the size of the model to be solved.We introduce a reformulation of the planning problem in which the problem is described as a meta-CSP, which controls the search of an underlying SAT solver. Our results show that this approach solves a greater number of problems than both Maxplan and Blackbox, and our analysis discusses the advantages and disadvantages of searching in the backwards direction.",

keywords = "meta-CSP, optimal planning, maxplan, blackbox",

author = "Peter Gregory and Derek Long and Maria Fox and W. Ruml and I. Miguel",

year = "2007",

language = "English",

pages = "200--214",

note = "Seventh Symposium on Abstraction, Reformulation and Approximation (SARA) ; Conference date: 18-07-2007 Through 21-07-2007",

}

TY - CONF

T1 - A meta-CSP model for optimal planning

AU - Gregory, Peter

AU - Long, Derek

AU - Fox, Maria

A2 - Ruml, W.

A2 - Miguel, I.

PY - 2007

Y1 - 2007

N2 - One approach to optimal planning is to first start with a sub-optimal solution as a seed plan, and then iteratively search for shorter plans. This approach inevitably leads to an increase in the size of the model to be solved.We introduce a reformulation of the planning problem in which the problem is described as a meta-CSP, which controls the search of an underlying SAT solver. Our results show that this approach solves a greater number of problems than both Maxplan and Blackbox, and our analysis discusses the advantages and disadvantages of searching in the backwards direction.

AB - One approach to optimal planning is to first start with a sub-optimal solution as a seed plan, and then iteratively search for shorter plans. This approach inevitably leads to an increase in the size of the model to be solved.We introduce a reformulation of the planning problem in which the problem is described as a meta-CSP, which controls the search of an underlying SAT solver. Our results show that this approach solves a greater number of problems than both Maxplan and Blackbox, and our analysis discusses the advantages and disadvantages of searching in the backwards direction.

KW - meta-CSP

KW - optimal planning

KW - maxplan

KW - blackbox

UR - https://ianm.host.cs.st-andrews.ac.uk/SARA2007.html

M3 - Paper

SP - 200

EP - 214

T2 - Seventh Symposium on Abstraction, Reformulation and Approximation (SARA)

Y2 - 18 July 2007 through 21 July 2007

ER -

A meta-CSP model for optimal planning

Abstract

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this