Representations to Support Planning, Sensing, and Execution under Incomplete Knowledge

Fahiem Bacchus
University of Waterloo


We consider state representations suitable for planning under incomplete knowledge. There are various applications where it is reasonable to assume that the agent has accurate but incomplete knowledge of its environment. For example, software sensing actions in an operating systems environment, like "ls", can be assumed to return accurate information.

In this talk I will describe how an agent's knowledge can be represented by a collection of databases. We can then model sensing and other actions as updates to these databases. Thus we lift the STRIPS representation to the incomplete knowledge situation. Although this approach restricts what can be represented, it has the advantage that now plans can be found by state space search: the states represent the agent's incomplete knowledge at each stage of the plan. This approach also provides a clean separation between plan time and execution time knowledge.

This is joint work with Ron Petrick (now a Ph.D. student at the University of Toronto).

Eyal Amir
Last modified: Mon Apr 19 16:10:44 PDT 1999