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

Alfredo Gabaldon

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.

Subjects: 1.11 Planning; 11. Knowledge Representation

Submitted: Jan 26, 2007

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.