Verity: Minimizing Delta-V when planning under uncertainty

Verity is the term suggested by David Vose, in his book Risk Analysis to describe the combination of the natural variability of an environment and the lack of complete knowledge (uncertainty) of the observer. He notes that these two components are responsible for the inability to completely predict future events, and that they are often combined into a single term, however there can be benefits from keeping them separate.

The concept I'm exploring in this model is this: Can a planner make better decisions by reasoning about the underlying structural variabiity, which prevents predictability of individual events, and by modeling the uncertainty that results from not knowing what the current state of the world is?

The Verity model is a world state transformation model. A plan is viewed as a change in the state of the world, from an initial world description to a terminal world description or goal state. The use of verity attempts to capture the belief in the likelihhod of the terminal world description. Since the observer should have a higher confidence in the initial world description, the plan that results in the minimum decrease in belief is preferred. Thus planning should attempt to minimize the delta-Verity (or Delta-V) of the system while achieving the terminal world description.

By explicitly modeling the planning process from an 'lack of knowledge' perspective, the planner accepts that the application of an operator to the world decreases the ability to say "the world will be in state X", and under certain conditions, this decrease is transitive (e.g., if event {E1} has a Delta-V of 0.9 and {E2} has a Delta-V of 0.8, and these two operators can be coupled into {E1,E2}, can the planner reason about the Delta-V of the new, operator? If so, it becomes possible to approach planning from a 'constructionist' model rather than a search model.

Planning as Search

One traditional view of planning is that it is a search problem. (For an older, but excellent review of Planning through the late 80's, see A Review of AI Planning Techniques Given the space of all possible plans, find the best, or find any one that works, or determine that no such plan exists. Given a set of operators of size K, there are K plans of length 1, K^2 plans of length 2, etc. However, most of these plans are not only infeasible (they do not achieve the goals) they are non-operational. For example, in a blocks world domain, there are many plans which have an operator (stack X Y), which must be preceded by a (pickup X). However, in the space of all possible plans which do not fulfill the necessary preconditions. So, if we could avoid looking at these non-operational plans, the search space would be much smaller, and the planning problem would be simpler. Hence, planning is the process of limiting the search.

So, there are three main approaches to limiting this space.

Backward chaining search
Forward chaining search with search control rules
Constraint Propogation techniques

Backward Chaining Search

Forward Chaining Search

Constraint Propogation Techniques

World

The Verity model uses an open world hypothesis. The absence of a specifier means that nothing is known. This is in contrast to the closed world hypothesis with states that anything not explicitly defined as true is false.

The world is made up of objects, and these objects can be affected by events. More formal definitions of these terms is presented below, however, at a high level, objects are the things that exist in the world, and the state of those things, and events cause changes in the state of the objects.

Objects

Objects populate a world, and have characteristics. For example, in the blocks world domain blocks are objects, and the have the characteristic supported-by. Each characteristic has a enumerated set of values that it can take on, and must be in one of those states. However, the observer may not know which of the states associated with any characteristic an object may be in.

For example, in a simple version of the blocks world domain, a block has a single characteristic: supported-by. This characteristic has the following value set: {table, another block X, gripper}. Each block in the world has exactly one value for supported-by at any time.

An object is defined as a n-tuple, with a specific value for each of its characteristics. Since different types of objects will have different characteristics, the degree of the n-tuple for any two objects may differ.

Events

Events come in two flavors, those caused by the application of an operator, and exogenous events. During the course of planning, the planner needs to change the world description from some undesired state to a state that is more acceptable. It attempts this change by applying an operator. However, it is also possible that events external to the planner will also cause changes to the world state. These are exeogenous events.

Operators are described by three terms, a description of the conditions that are necessary for the operator to be applied, the description of the effect that the operator has on the world, and the Delta-V associated with the operator. Continuing with the blocks-world example, the stack operator might have:

initial world description {(Object X {Block {gripper, clear}), (Object Y {Block {table, clear})},
terminal world description {(Object X {Block {On Y, clear}), (Object Y {Block {table, not clear})}
Delta-V = 0.9.

References:

Tate, A, Hendler, J., and Drummond, M. A Review of AI Planning Techniques in Readings in Planning, Chapt. 1, Kaufman, 1990

Vose, D. Risk Analysis 2nd Ed., Chapt. 2. John Wiley and Sons, 2000

Send any comments to

J. P. Gunderson

Last modified: Wed Jan 17 13:28:47 2001