The SBR planner is the core of the SBR system. It takes as input an initial scene, and a goal represented by a sub-scene. It returns a number of plans represented by HTN tasks, together with confidence scores. The authors assume that the SBR planner will nearly always operate on task with predefined decompositions and known confidence scores. The process of learning new decompositions is explained further below.
The SBR planner uses task decompositions similar to Hierarchical Task Networks (HTNs), but modified in several ways:
- Spatio-temporal planning language: The SBR planner operates on Scenes to represent the 3D state of the world instead of FOL formulas.
- Probabilistic planning: SBR tasks ("operators") may in general have multiple outcomes.
- Timeline planning: SBR tasks take a certain time to complete. Each object follows its own timeline.
- Multi-agent planning: The planner will use the prediction subsystem to predict the behavior of Agents and movable objects while time passes.
- Resource-bound operations: The planner will work incrementally starting with the plans that take the least time to develop and propose additional plans if time is available.
Dealing with Complexity
As of today, planning with these characteristics is only partially understood, and the authors have not found any reference to practical systems combining stochastic planning and HTNs for more than toy domains. In the face of this situation, the authors sketch below a new approach that relies on "active tasks", "worst-case analysis" and "abstract physics simulation" in order to cope with the dramatically increased branching factor.
An "active task" or "SBR task" is a planner task with a known decomposition, together with statistics about past executions of the task (stored in the episodic memory), along the lines of PRODIGY [Veloso et al., 1995] and PELA [Jiménez 2011]. Past execution may have included re-planning or escalation processes in order to deal with local failures, which have an impact on the cost of the action and its duration. The resulting building block is frequently labeled as a "verb" by the language subsystem. For example, the "preparing dinner" building block may include some last-minute purchase of missing ingredients, or dealing with partially burned food. The statistics of past executions of active tasks can be analyzed with respect to the influencing factors in order to determine a certainty measure that the Agent will be able to successfully execute the action again in a given scene. This certainty measure can be a complex function of environment parameters and historical performance recorded in the episodic memory. Once this measure approaches 100%, active tasks can be considered as a primitive tasks by the planner.
Worst Case Analysis
To complement this active tasks approach, we propose a "worst-case analysis" of the finished plan. For this purpose, undesired outcomes from the various active tasks are treated individually, as opposed to calculating probability distributions over "histories" (Ghallab, Nau, Traverso 2004). Combined with the cost of executing the plan and the impact of a failed plan, the SBR planner can calculate a risk compensation and decide whether to pursue this path, develop a better plan or to choose non-action. Finally, the "abstract physics simulation" has been defined in the prediction subsystem and is used to calculate the approximate impact of actions, capturing the default behavior of objects in a scene. The default behavior of objects (for example a plate in the dinner scene) usually has a low degree of freedom, and is therefore highly deterministic and can be calculated with a very low branching factor.
Planning With Scenes
In contrast to "classical" planners that operate on propositional or first-order logic formulas, the SBR planner operates on scenes and scripts:
- Task conditions: SBR uses sub-scene to describe task conditions and effects. As a result, the planning language is limited to conjunctions of constraints on objects' attributes and object relationships. Negative or disjunctive conditions are not supported.
- Final state of each task is also described using a sub-scene.
The lack of negative or disjunctive information allows SBR to use statistical or connectionist algorithms in order to speed up the retrieval of matching plans from the "episodic memory" (defined further below). The authors believe that this corresponds to the way neurons process information in biological systems. The lack of expressivity in the planning language is compensated in SBR by two factors:
- The restriction to positive information allows for more efficient information retrieval in the episodic memory subsystem, that can use efficient indexing algorithms using the types of objects and specific attributes.
- The logical reasoning subsystem provides the additional means of incorporating negation and disjunctions in the reasoning process.
However, the authors are not sure if this approach will yield truly practical results in real-world applications. In this case further research might be required to modify the expressiveness of the HTN planning language and to adapt the indexing techniques applied in the episodic memory. In addition to HTN tasks modifying the state of the world, the SBR planner can employ the Prediction Sub-system in order to simulate the behavior of objects and Agents. This adds to SBR the ability to modify a plan in order to take into account an Agent's reaction to SBR actions. This also adds the ability to execute pre-planned plans in a kind of "sandbox" by simulating the behavior of the outer world.
TinyCog is designed to allow for "pluggable" planners, and to work with multiple planners in parallel. We will add more sophisticated planners in the future.
Simple Deterministic Planner
TinyCog 0.0.1 includes a [simple deterministic planner] without task decompositions and without the simulation of other Agents. However, this planner is already integrated with the Description Logics subsystem and operates on scenes. The DL integration allows to add new Beliefs during the planning process, enabling what-if analysis on Beliefs.