Planning for partial observability by SAT and graph constraints

Jussi Rintanen; Binda Pandey

Planning for partial observability by SAT and graph constraints

Jussi Rintanen
, Binda Pandey

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceedings › Scientific › peer-review

10 Citations (Scopus)

Abstract

Chatterjee et al. have recently shown the utility of SAT in solving a class of planning problems with partial observability. A core component of their logical formulation of planning is constraints expressing s-t-reachability in directed graphs. In this work, we show that the scalability of the approach can be dramatically improved by using dedicated graph constraints, and that a far broader class of important planning problems can be expressed in terms of s-t-reachability and acyclicity constraints.

Original language	English
Title of host publication	Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS)
Editors	Mathijs de Weerdt, Sven Koenig, Gabriele Röger, Matthijs Spaan
Publisher	AAAI Press
Pages	190-198
Number of pages	9
ISBN (Electronic)	978-1-57735-797-1
Publication status	Published - 24 Jun 2018
MoE publication type	A4 Conference publication
Event	International Conference on Automated Planning and Scheduling - Delft, Netherlands Duration: 24 Jun 2018 → 29 Jun 2018 Conference number: 28

Publication series

Name	Proceedings of the International Conference on Automated Planning and Scheduling
Publisher	AAAI PRESS
ISSN (Electronic)	2334-0843

Conference

Conference	International Conference on Automated Planning and Scheduling
Abbreviated title	ICAPS
Country/Territory	Netherlands
City	Delft
Period	24/06/2018 → 29/06/2018

Keywords

SAT
planning
partial observability
graphs
constraints
acyclicity
reachability

Access to Document

https://aaai.org/ocs/index.php/ICAPS/ICAPS18/paper/view/17756

Cite this

Rintanen, J., & Pandey, B. (2018). Planning for partial observability by SAT and graph constraints. In M. de Weerdt, S. Koenig, G. Röger, & M. Spaan (Eds.), Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS) (pp. 190-198). (Proceedings of the International Conference on Automated Planning and Scheduling). AAAI Press. https://aaai.org/ocs/index.php/ICAPS/ICAPS18/paper/view/17756

Rintanen, Jussi ; Pandey, Binda. / Planning for partial observability by SAT and graph constraints. Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS). editor / Mathijs de Weerdt ; Sven Koenig ; Gabriele Röger ; Matthijs Spaan. AAAI Press, 2018. pp. 190-198 (Proceedings of the International Conference on Automated Planning and Scheduling).

@inproceedings{d9e189233df04e38a1f06e00d302d568,

title = "Planning for partial observability by SAT and graph constraints",

abstract = "Chatterjee et al. have recently shown the utility of SAT in solving a class of planning problems with partial observability. A core component of their logical formulation of planning is constraints expressing s-t-reachability in directed graphs. In this work, we show that the scalability of the approach can be dramatically improved by using dedicated graph constraints, and that a far broader class of important planning problems can be expressed in terms of s-t-reachability and acyclicity constraints.",

keywords = "SAT, planning, partial observability, graphs, constraints, acyclicity, reachability",

author = "Jussi Rintanen and Binda Pandey",

year = "2018",

month = jun,

day = "24",

language = "English",

series = "Proceedings of the International Conference on Automated Planning and Scheduling",

publisher = "AAAI Press",

pages = "190--198",

editor = "\{de Weerdt\}, Mathijs and Sven Koenig and Gabriele R{\"o}ger and Matthijs Spaan",

booktitle = "Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS)",

address = "United States",

note = "International Conference on Automated Planning and Scheduling, ICAPS ; Conference date: 24-06-2018 Through 29-06-2018",

}

Rintanen, J & Pandey, B 2018, Planning for partial observability by SAT and graph constraints. in M de Weerdt, S Koenig, G Röger & M Spaan (eds), Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS). Proceedings of the International Conference on Automated Planning and Scheduling, AAAI Press, pp. 190-198, International Conference on Automated Planning and Scheduling, Delft, Netherlands, 24/06/2018. <https://aaai.org/ocs/index.php/ICAPS/ICAPS18/paper/view/17756>

Planning for partial observability by SAT and graph constraints. / Rintanen, Jussi; Pandey, Binda.
Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS). ed. / Mathijs de Weerdt; Sven Koenig; Gabriele Röger; Matthijs Spaan. AAAI Press, 2018. p. 190-198 (Proceedings of the International Conference on Automated Planning and Scheduling).

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceedings › Scientific › peer-review

TY - GEN

T1 - Planning for partial observability by SAT and graph constraints

AU - Rintanen, Jussi

AU - Pandey, Binda

N1 - Conference code: 28

PY - 2018/6/24

Y1 - 2018/6/24

N2 - Chatterjee et al. have recently shown the utility of SAT in solving a class of planning problems with partial observability. A core component of their logical formulation of planning is constraints expressing s-t-reachability in directed graphs. In this work, we show that the scalability of the approach can be dramatically improved by using dedicated graph constraints, and that a far broader class of important planning problems can be expressed in terms of s-t-reachability and acyclicity constraints.

AB - Chatterjee et al. have recently shown the utility of SAT in solving a class of planning problems with partial observability. A core component of their logical formulation of planning is constraints expressing s-t-reachability in directed graphs. In this work, we show that the scalability of the approach can be dramatically improved by using dedicated graph constraints, and that a far broader class of important planning problems can be expressed in terms of s-t-reachability and acyclicity constraints.

KW - SAT

KW - planning

KW - partial observability

KW - graphs

KW - constraints

KW - acyclicity

KW - reachability

M3 - Conference article in proceedings

T3 - Proceedings of the International Conference on Automated Planning and Scheduling

SP - 190

EP - 198

BT - Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS)

A2 - de Weerdt, Mathijs

A2 - Koenig, Sven

A2 - Röger, Gabriele

A2 - Spaan, Matthijs

PB - AAAI Press

T2 - International Conference on Automated Planning and Scheduling

Y2 - 24 June 2018 through 29 June 2018

ER -

Planning for partial observability by SAT and graph constraints

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this