Resolving Non-Determinism in Programs for Complex Task Planning with Search Control

Logical Formalizations of Commonsense Reasoning

Volume

Papers from the 2007 AAAI Spring Symposium

Contents

We consider the problem of planning in complex domains where actions are stochastic, non-instantaneous, may occur concurrently, and time is represented explicitly. Our approach is based on the situation calculus based language Golog. Instead of general search for a sequence of actions, as in classical planning, we consider the problem of computing a deterministic, sequential program (with stochastic actions as primitives) from an underspecified, non-deterministic, concurrent program. Similar to the search for a plan, the process of obtaining a deterministic program from a non-deterministic one is carried out offline, with the deterministic program obtained by this process then being available for online execution. We then describe a form of domain-dependent search control that can be used to provide some degree of goal-directedness to the search for solutions in this setting, and also show how a simple programming construct for probabilistic tests can be used for further pruning of the search space.