Allocating Planning Effort when Actions Expire

Shahaf Shperberg; Andrew Ian Coles; Bence Cserna; Erez Karpas; Wheeler Ruml; Solomon Shimony

Allocating Planning Effort when Actions Expire

Shahaf Shperberg, Andrew Ian Coles, Bence Cserna, Erez Karpas, Wheeler Ruml, Solomon Shimony

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › peer-review

11 Citations (Scopus)

71 Downloads (Pure)

Abstract

Making plans that depend on external events can be tricky. For example, an agent considering a partial plan that involves taking a bus must recognize that this partial plan is only viable if completed and selected for execution in time for the agent to arrive at the bus stop. This setting raises the thorny problem of allocating the agent's planning effort across multiple open search nodes, each of which has an expiration time and an expected completion effort in addition to the usual estimated plan cost. This paper formalizes this metareasoning problem, studies its theoretical properties, and presents several algorithms for solving it. Our theoretical results include a surprising connection to job scheduling, as well as to deliberation scheduling in time-dependent planning. Our empirical results indicate that our algorithms are effective in practice. This work advances our understanding of how heuristic search planners might address realistic problem settings.

Original language	English
Title of host publication	Proceedings of the Thirty Third AAAI Conference on Artificial Intelligence
Publisher	AAAI Press
Publication status	Published - 27 Jan 2019

Access to Document

allocating-planning-effortAccepted author manuscript, 208 KB

European Robotic Goal-Oriented autonomous controller : ERGO
Coles, A., Coles, A. & Long, D.
EC European Commission
1/11/2016 → 31/01/2019
Project: Research

Cite this

@inbook{98fdf5a9f5b74f5290fa14b669af4940,

title = "Allocating Planning Effort when Actions Expire",

abstract = "Making plans that depend on external events can be tricky. For example, an agent considering a partial plan that involves taking a bus must recognize that this partial plan is only viable if completed and selected for execution in time for the agent to arrive at the bus stop. This setting raises the thorny problem of allocating the agent's planning effort across multiple open search nodes, each of which has an expiration time and an expected completion effort in addition to the usual estimated plan cost. This paper formalizes this metareasoning problem, studies its theoretical properties, and presents several algorithms for solving it. Our theoretical results include a surprising connection to job scheduling, as well as to deliberation scheduling in time-dependent planning. Our empirical results indicate that our algorithms are effective in practice. This work advances our understanding of how heuristic search planners might address realistic problem settings.",

author = "Shahaf Shperberg and Coles, {Andrew Ian} and Bence Cserna and Erez Karpas and Wheeler Ruml and Solomon Shimony",

year = "2019",

month = jan,

day = "27",

language = "English",

booktitle = "Proceedings of the Thirty Third AAAI Conference on Artificial Intelligence",

publisher = "AAAI Press",

}

TY - CHAP

T1 - Allocating Planning Effort when Actions Expire

AU - Shperberg, Shahaf

AU - Coles, Andrew Ian

AU - Cserna, Bence

AU - Karpas, Erez

AU - Ruml, Wheeler

AU - Shimony, Solomon

PY - 2019/1/27

Y1 - 2019/1/27

N2 - Making plans that depend on external events can be tricky. For example, an agent considering a partial plan that involves taking a bus must recognize that this partial plan is only viable if completed and selected for execution in time for the agent to arrive at the bus stop. This setting raises the thorny problem of allocating the agent's planning effort across multiple open search nodes, each of which has an expiration time and an expected completion effort in addition to the usual estimated plan cost. This paper formalizes this metareasoning problem, studies its theoretical properties, and presents several algorithms for solving it. Our theoretical results include a surprising connection to job scheduling, as well as to deliberation scheduling in time-dependent planning. Our empirical results indicate that our algorithms are effective in practice. This work advances our understanding of how heuristic search planners might address realistic problem settings.

AB - Making plans that depend on external events can be tricky. For example, an agent considering a partial plan that involves taking a bus must recognize that this partial plan is only viable if completed and selected for execution in time for the agent to arrive at the bus stop. This setting raises the thorny problem of allocating the agent's planning effort across multiple open search nodes, each of which has an expiration time and an expected completion effort in addition to the usual estimated plan cost. This paper formalizes this metareasoning problem, studies its theoretical properties, and presents several algorithms for solving it. Our theoretical results include a surprising connection to job scheduling, as well as to deliberation scheduling in time-dependent planning. Our empirical results indicate that our algorithms are effective in practice. This work advances our understanding of how heuristic search planners might address realistic problem settings.

M3 - Conference paper

BT - Proceedings of the Thirty Third AAAI Conference on Artificial Intelligence

PB - AAAI Press

ER -

Allocating Planning Effort when Actions Expire

Abstract

Access to Document

Fingerprint

Projects

European Robotic Goal-Oriented autonomous controller : ERGO

Cite this