Automated Planning and Acting

Table of Contents


Chapter 1: Introduction

1.1.  Purpose and Motivations
1.1.1.  First Intuition
1.1.2.  Motivations
1.1.3.  Focus and Scope
1.2.  Conceptual View of an Actor
1.2.1.  A Simple Architecture
1.2.2.  Hierarchical and Continual Online Deliberation
1.2.3.  Assumptions
1.3.  Deliberation Models and Functions
1.3.1.  Descriptive and Operational Models of Actions
1.3.2.  Description of States for Deliberation
1.3.3.  Planning Versus Acting
1.3.4.  Other Deliberation Functions
1.4.  Illustrative Examples
1.4.1.  A Factotum Service Robot
1.4.2.  A Complex Infrastructure Manager
1.5.  Outline of the book

Chapter 2: Deliberation with Deterministic Models

2.1.  State-Variable Representation
2.1.1.  State-Transition Systems
2.1.2.  Objects and State Variables
2.1.3.  Actions and Action Templates
2.1.4.  Plans and Planning Problems
2.2.  Forward State-Space Search
2.2.1.  Breadth-First Search
2.2.2.  Depth-First Search
2.2.3.  Hill Climbing
2.2.4.  Uniform-Cost Search
2.2.5.  A*
2.2.6.  Depth-First Branch and Bound
2.2.7.  Greedy Best-First Search
2.2.8.  Iterative Deepening
2.2.9.  Choosing a Forward-Search Algorithm
2.3.  Heuristic Functions
2.3.1.  Max-Cost and Additive Cost Heuristics
2.3.2.  Delete-Relaxation Heuristics
2.3.3.  Landmark Heuristics
2.4.  Backward Search
2.5.  Plan-Space Search
2.5.1.  Definitions and Algorithm
2.5.2.  Planning Algorithm
2.5.3.  Search Heuristics
2.6.  Incorporating Planning into an Actor
2.6.1.  Repeated Planning and Replanning
2.6.2.  Online Planning
2.7.  Discussion and Historical Remarks
2.7.1.  Classical Domain Models
2.7.2.  Generalized Domain Models
2.7.3.  Heuristic Search Algorithms
2.7.4.  Planning Graphs
2.7.5.  Converting Planning Problems into Other Problems
2.7.6.  Planning with Abstraction
2.7.7.  HTN Planning
2.7.8.  Temporal Logic
2.7.9.  Domain-Independent Planning Heuristics
•  Delete-Relaxation Heuristics
•  Landmark Heuristics
•  Critical-Path Heuristics
•  Abstraction Heuristics
2.7.10.  Plan-Space Planning
2.7.11.  Online Planning
2.8.  Exercises

Chapter 3: Deliberation with Refinement Methods

3.1.  Operational Models
3.1.1.  Basic ingredients
3.1.2.  Refinement Methods
3.1.3.  Illustrations
3.1.4.  Updates of the Current State
3.2.  A Refinement Acting Engine
3.2.1.  Global View
3.2.2.  Main Algorithms
3.2.3.  Goals in RAE
3.2.4.  Additional Features for RAE
3.3.  Refinement Planning
3.3.1.  Sequential Refinement Planning
3.3.2.  Interleaved Plans
3.4.  Acting and Refinement Planning
3.4.1.  Planning and Acting at Different Levels
3.4.2.  Integrated Acting and Planning
3.5.  Discussion and Historical Remarks
3.5.1.  Refinement Acting
3.5.2.  Refinement Planning
3.5.3.  Translating Among Multiple Domain Models
3.6.  Exercises

Chapter 4: Deliberation with Temporal Models

4.1.  Introduction
4.2.  Temporal Representation
4.2.1.  Assertions and Timelines
4.2.2.  Actions
4.2.3.  Methods and Tasks
4.2.4.  Chronicles
4.3.  Planning with Temporal Refinement Methods
4.3.1.  Temporal Planning Algorithm
4.3.2.  Resolving Non-Refined Tasks
4.3.3.  Resolving Non-Supported Assertions
4.3.4.  Resolving Conflicting Assertions
4.3.5.  Search Space
4.3.6.  Illustration
4.3.7.  Free Versus Task-Dependent Primitives
4.4.  Constraint Management in Temporal Planning
4.4.1.  Consistency of Object Constraints
4.4.2.  Consistency of Temporal Constraints
4.4.3.  Controllability of Temporal Constraints
4.5.  Acting with Temporal Models
4.5.1.  Acting with Atemporal Refinement Methods
4.5.2.  Acting with Temporal Refinement Methods
4.5.3.  Acting and Planning with Temporal Refinement Methods
4.6.  Discussion and Historical Remarks
4.6.1.  Temporal Representation and Reasoning
4.6.2.  Temporal Planning
4.6.3.  Acting with Temporal Models
4.7.  Exercises

Chapter 5: Deliberation with Nondeterministic Models

5.1.  Introduction and Motivation
5.2.  The Planning Problem
5.2.1.  Planning Domains
5.2.2.  Plans as Policies
5.2.3.  Planning Problems and Solutions
5.3.  And/Or Graph Search
5.3.1.  Planning by Forward Search
5.3.2.  Planning by Min Max Search
5.4.  Symbolic Model Checking Techniques
5.4.1.  Symbolic representation of sets of states.
5.4.2.  Symbolic representation of actions and transitions.
5.4.3.  Planning for Safe Solutions
5.4.4.  Planning for Safe Acyclic Solutions
5.4.5.  BDD-based Representation
5.5.  Determinization Techniques
5.5.1.  Guided Planning for Safe Solutions
5.5.2.  Planning for Safe Solutions by Determinization
5.6.  Online approaches
5.6.1.  Lookahead
5.6.2.  Lookahead by determinization
5.6.3.  Lookahead with a bounded number of steps
5.7.  Refinement Methods with Nondeterministic Models
5.7.1.  Tasks in Refinement Methods
5.7.2.  context-dependent plans
5.7.3.  Search Automata
5.7.4.  Planning based on Search Automata
5.8.  Acting with Input/Output Automata
5.8.1.  Input/Output Automata
5.8.2.  Control Automata
5.8.3.  Automated Synthesis of Control Automata
5.8.4.  Synthesis of Control Automata by Planning
5.8.5.  Acting by Interacting with Multiple Automata
•  Synthesis of controllers of multiple automata
5.9.  Discussion and Historical Remarks
5.9.1.  Comparison between different approachess
5.9.2.  Historical Remarks
5.10.  Exercises

Chapter 6: Deliberation with Probabilistic Models

6.1.  Introduction
6.2.  Stochastic Shortest-Path Problems
6.2.1.  Main Definitions
6.2.2.  Safe and Unsafe Policies
6.2.3.  Optimality Principle of Dynamic Programming
6.2.4.  Policy Iteration
6.2.5.  Value Iteration
6.3.  Heuristic Search Algorithms
6.3.1.  A General Heuristic Search Schema
6.3.2.  Best-First Search
6.3.3.  Depth-First Search
6.3.4.  Iterative Deepening Search
6.3.5.  Heuristics and Search Control in Probabilistic Planning
6.4.  Online Probabilistic Approaches
6.4.1.  Lookahead Methods
6.4.2.  Lookahead with Deterministic Search
6.4.3.  Stochastic Simulation Techniques
6.4.4.  Sparse Sampling and Monte Carlo Search
6.5.  Acting with Probabilistic Models
6.5.1.  Using Deterministic Methods to Refine Policy Steps
6.5.2.  Acting with Probabilistic Methods
6.6.  Representations of Probabilistic Models
6.6.1.  Probabilistic Precondition-Effect Operators
6.6.2.  Dynamic Bayesian Networks
6.7.  Domain Modeling and Practical Issues
6.7.1.  Sources of Nondeterminism
6.7.2.  Sparse Probabilistic Domains
6.7.3.  Goals and Objectives
6.7.4.  Domain Decomposition and Hierarchization
6.7.5.  Probabilistic Versus Nondeterministic Approaches
6.7.6.  Practical Considerations
6.8.  Discussion and Historical Remarks
6.8.1.  Foundations
6.8.2.  SSP Models
6.8.3.  Partially Observable Models
6.8.4.  Other Extended MDP Models
6.8.5.  Algorithms and Heuristics
6.8.6.  Factored and Hierarchical MDPs
6.9.  Exercises

Chapter 7: Other Deliberation Functions

7.1.  Perceiving
7.1.1.  Planning and Acting with Information Gathering
7.1.2.  Planning to Perceive
7.1.3.  Symbol Anchoring
7.1.4.  Event and Situation Recognition
7.2.  Monitoring and Goal Reasoning
7.2.1.  Platform Monitoring
7.2.2.  Action and Plan Monitoring
7.2.3.  Goal Reasoning
7.3.  Learning and Model Acquisition
7.3.1.  Reinforcement Learning
7.3.2.  Learning from Demonstrations, Advices and Partial Programs
7.3.3.  Acquiring Descriptive Models and Heuristics
7.4.  Hybrid Models
7.4.1.  Hybrid Automata
7.4.2.  Input/Output Hybrid Automata
7.4.3.  Planning as Model Checking
7.4.4.  Flow Tubes
7.4.5.  Discretization Techniques
7.5.  Ontologies for Planning and Acting
7.5.1.  Ontologies and Description Logic
7.5.2.  Ontologies and Planning
7.5.3.  Planning and Acting based on Description Logic
7.5.4.  Semantic Mapping for Hierarchical Representations

Chapter 8: Concluding Remarks

Appendix A: Search Algorithms

A.1.  Nondeterministic State-Space Search
A.2.  And/Or Search

Appendix B: Strongly Connected Components of a Graph

Bibliography