The Limits of Learning and Planning: Minimal Sufficient Information Transition Systems

Basak Sakcak; Vadim Weinstein; Steven M. LaValle

doi:10.1007/978-3-031-21090-7_16

The Limits of Learning and Planning: Minimal Sufficient Information Transition Systems

Basak Sakcak, Vadim Weinstein, Steven M. LaValle

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

In this paper, we view a policy or plan as a transition system over a space of information states that reflect a robot’s or other observer’s perspective based on limited sensing, memory, computation, and actuation. Regardless of whether policies are obtained by learning algorithms, planning algorithms, or human insight, we want to know the limits of feasibility for given robot hardware and tasks. Toward the quest to find the best policies, we establish in a general setting that minimal information transition systems (ITSs) exist up to reasonable equivalence assumptions, and are unique under some general conditions. We then apply the theory to generate new insights into several problems, including optimal sensor fusion/filtering, solving basic planning tasks, and finding minimal representations for feasible policies.

Original language	English (US)
Title of host publication	Algorithmic Foundations of Robotics XV - Proceedings of the Fifteenth Workshop on the Algorithmic Foundations of Robotics
Editors	Steven M. LaValle, Jason M. O’Kane, Michael Otte, Dorsa Sadigh, Pratap Tokekar
Publisher	Springer
Pages	256-272
Number of pages	17
ISBN (Print)	9783031210891
DOIs	https://doi.org/10.1007/978-3-031-21090-7_16
State	Published - 2023
Externally published	Yes
Event	15th Workshop on the Algorithmic Foundations of Robotics, WAFR 2022 - College Park, United States Duration: Jun 22 2022 → Jun 24 2022

Publication series

Name	Springer Proceedings in Advanced Robotics
Volume	25 SPAR
ISSN (Print)	2511-1256
ISSN (Electronic)	2511-1264

Conference

Conference	15th Workshop on the Algorithmic Foundations of Robotics, WAFR 2022
Country/Territory	United States
City	College Park
Period	6/22/22 → 6/24/22

Keywords

Information spaces
Planning
Sensing uncertainty
Theoretical foundations

ASJC Scopus subject areas

Control and Systems Engineering
Electrical and Electronic Engineering
Mechanical Engineering
Engineering (miscellaneous)
Artificial Intelligence
Computer Science Applications
Applied Mathematics

Online availability

10.1007/978-3-031-21090-7_16

Library availability

Discover UIUC Full Text

Cite this

Sakcak, B., Weinstein, V., & LaValle, S. M. (2023). The Limits of Learning and Planning: Minimal Sufficient Information Transition Systems. In S. M. LaValle, J. M. O’Kane, M. Otte, D. Sadigh, & P. Tokekar (Eds.), Algorithmic Foundations of Robotics XV - Proceedings of the Fifteenth Workshop on the Algorithmic Foundations of Robotics (pp. 256-272). (Springer Proceedings in Advanced Robotics; Vol. 25 SPAR). Springer. https://doi.org/10.1007/978-3-031-21090-7_16

The Limits of Learning and Planning: Minimal Sufficient Information Transition Systems. / Sakcak, Basak; Weinstein, Vadim; LaValle, Steven M.
Algorithmic Foundations of Robotics XV - Proceedings of the Fifteenth Workshop on the Algorithmic Foundations of Robotics. ed. / Steven M. LaValle; Jason M. O’Kane; Michael Otte; Dorsa Sadigh; Pratap Tokekar. Springer, 2023. p. 256-272 (Springer Proceedings in Advanced Robotics; Vol. 25 SPAR).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Sakcak, B, Weinstein, V & LaValle, SM 2023, The Limits of Learning and Planning: Minimal Sufficient Information Transition Systems. in SM LaValle, JM O’Kane, M Otte, D Sadigh & P Tokekar (eds), Algorithmic Foundations of Robotics XV - Proceedings of the Fifteenth Workshop on the Algorithmic Foundations of Robotics. Springer Proceedings in Advanced Robotics, vol. 25 SPAR, Springer, pp. 256-272, 15th Workshop on the Algorithmic Foundations of Robotics, WAFR 2022, College Park, United States, 6/22/22. https://doi.org/10.1007/978-3-031-21090-7_16

Sakcak B, Weinstein V, LaValle SM. The Limits of Learning and Planning: Minimal Sufficient Information Transition Systems. In LaValle SM, O’Kane JM, Otte M, Sadigh D, Tokekar P, editors, Algorithmic Foundations of Robotics XV - Proceedings of the Fifteenth Workshop on the Algorithmic Foundations of Robotics. Springer. 2023. p. 256-272. (Springer Proceedings in Advanced Robotics). doi: 10.1007/978-3-031-21090-7_16

Sakcak, Basak ; Weinstein, Vadim ; LaValle, Steven M. / The Limits of Learning and Planning : Minimal Sufficient Information Transition Systems. Algorithmic Foundations of Robotics XV - Proceedings of the Fifteenth Workshop on the Algorithmic Foundations of Robotics. editor / Steven M. LaValle ; Jason M. O’Kane ; Michael Otte ; Dorsa Sadigh ; Pratap Tokekar. Springer, 2023. pp. 256-272 (Springer Proceedings in Advanced Robotics).

@inproceedings{9dd4a7d0620749ef8eb6b52c3625e864,

title = "The Limits of Learning and Planning: Minimal Sufficient Information Transition Systems",

abstract = "In this paper, we view a policy or plan as a transition system over a space of information states that reflect a robot{\textquoteright}s or other observer{\textquoteright}s perspective based on limited sensing, memory, computation, and actuation. Regardless of whether policies are obtained by learning algorithms, planning algorithms, or human insight, we want to know the limits of feasibility for given robot hardware and tasks. Toward the quest to find the best policies, we establish in a general setting that minimal information transition systems (ITSs) exist up to reasonable equivalence assumptions, and are unique under some general conditions. We then apply the theory to generate new insights into several problems, including optimal sensor fusion/filtering, solving basic planning tasks, and finding minimal representations for feasible policies.",

keywords = "Information spaces, Planning, Sensing uncertainty, Theoretical foundations",

author = "Basak Sakcak and Vadim Weinstein and LaValle, {Steven M.}",

note = "Publisher Copyright: {\textcopyright} 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.; 15th Workshop on the Algorithmic Foundations of Robotics, WAFR 2022 ; Conference date: 22-06-2022 Through 24-06-2022",

year = "2023",

doi = "10.1007/978-3-031-21090-7_16",

language = "English (US)",

isbn = "9783031210891",

series = "Springer Proceedings in Advanced Robotics",

publisher = "Springer",

pages = "256--272",

editor = "LaValle, {Steven M.} and O{\textquoteright}Kane, {Jason M.} and Michael Otte and Dorsa Sadigh and Pratap Tokekar",

booktitle = "Algorithmic Foundations of Robotics XV - Proceedings of the Fifteenth Workshop on the Algorithmic Foundations of Robotics",

address = "Germany",

}

TY - GEN

T1 - The Limits of Learning and Planning

T2 - 15th Workshop on the Algorithmic Foundations of Robotics, WAFR 2022

AU - Sakcak, Basak

AU - Weinstein, Vadim

AU - LaValle, Steven M.

PY - 2023

Y1 - 2023

N2 - In this paper, we view a policy or plan as a transition system over a space of information states that reflect a robot’s or other observer’s perspective based on limited sensing, memory, computation, and actuation. Regardless of whether policies are obtained by learning algorithms, planning algorithms, or human insight, we want to know the limits of feasibility for given robot hardware and tasks. Toward the quest to find the best policies, we establish in a general setting that minimal information transition systems (ITSs) exist up to reasonable equivalence assumptions, and are unique under some general conditions. We then apply the theory to generate new insights into several problems, including optimal sensor fusion/filtering, solving basic planning tasks, and finding minimal representations for feasible policies.

AB - In this paper, we view a policy or plan as a transition system over a space of information states that reflect a robot’s or other observer’s perspective based on limited sensing, memory, computation, and actuation. Regardless of whether policies are obtained by learning algorithms, planning algorithms, or human insight, we want to know the limits of feasibility for given robot hardware and tasks. Toward the quest to find the best policies, we establish in a general setting that minimal information transition systems (ITSs) exist up to reasonable equivalence assumptions, and are unique under some general conditions. We then apply the theory to generate new insights into several problems, including optimal sensor fusion/filtering, solving basic planning tasks, and finding minimal representations for feasible policies.

KW - Information spaces

KW - Planning

KW - Sensing uncertainty

KW - Theoretical foundations

UR - http://www.scopus.com/inward/record.url?scp=85145192114&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85145192114&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-21090-7_16

DO - 10.1007/978-3-031-21090-7_16

M3 - Conference contribution

AN - SCOPUS:85145192114

SN - 9783031210891

T3 - Springer Proceedings in Advanced Robotics

SP - 256

EP - 272

BT - Algorithmic Foundations of Robotics XV - Proceedings of the Fifteenth Workshop on the Algorithmic Foundations of Robotics

A2 - LaValle, Steven M.

A2 - O’Kane, Jason M.

A2 - Otte, Michael

A2 - Sadigh, Dorsa

A2 - Tokekar, Pratap

PB - Springer

Y2 - 22 June 2022 through 24 June 2022

ER -