A Spreading Activation Mechanism for Decision-Theoretic Planning

Abstract

When performing tasks with imperfect and incomplete knowledge, actions do not always provide the expected results. Consider a fairly simple task where a robot has to pick up a spoon from a table. Many things can and do go wrong. The object being grasped may have been misclassified as a spoon. The position and orientation of the spoon may not be accurately determined by the recognition system. The table may get disturbed during the grasp operation. The spoon may be outside the robot’s workspace. Traditional planners handle these situations as special cases by monitoring the environment as the pre-planned actions execute, and replanning when an unexpected state is detected [14]. The possibility of error is not considered during planning, but postponed until the execution of the plan. At the other extreme, stimulus-response systems [2] have no internal expectations of the world as they generate responses to observed stimuli. Since a predicted model of the world is not maintained, situations never arise. Reactive planners attempt to combine the two approaches into one by generating new plans at execution time as a reaction to the unexpected [1, 9, 6, 4, 5]. Our interest is in reactive planners that are embedded in the task execution system and handle error situations implicitly. Given a task and a particular state of the environment the system uses decision-theoretic methods to select and execute the action most likely to achieve a state closest to the goal state. This selection is based not only upon what the effects of an action are, but ~lso on the chances that the action will succeed in achieving those effects [4]. Consider for example, the task of picking up some food for feeding a person. A spoon or a fork can be used. When there is uncertainty associated with the food pickup operation, the planner should consider the chance of success when using the spoon or the fork, and make a choice on the basis of this knowledge. The planner described in this paper selects actions based on their expected utility (defined .as the product of the action’s desirability and its probability of success, given the existing state of the domain) in achieving the desirable effects [12]. As this action selection process continues, the goals of the task are achieved and thereafter, maintained. If an action does not produce the expected environment (the promise of which made the action desirable), the action with the next highest utility is attempted. This may correspond to an alternate plan which was considered less likely to succeed. When such alternatives are absent (or have a very low chance of working) the same action will be retried. This process of action selection not only handles errors, but also serendipitous situations, where a highly desirable action that was unexecutable till then, suddenly finds itself executable due an unexpected change in the environment. The obvious drawback of mixing planning with execution is that backtracking is not possible. However, unlike reactive systems, the planner can anticipate and avoid potential conflicts between actions by predicting how actions affect future states. In our framework, uncertainty in the domain is represented by extending the definition of classical STRIPS operators to have probability values associated with the preconditions and effects of actions. The planning framework that incorporates these probabilities is introduced in Section 2. Section 3 develops and provides a formal description of a planning algorithm which considers the probability of a plan’s success. Examples of planning behavior are shown in Section 5. It is also important for real-world planning algorithms to include mechanisms that combat the computational complexity inherent in search. Connectionist systems have shown how a multitude of simple processing nodes can tackle this problem in parallel [11]. The planning algorithm described here lends itself well to implementation as a connectionist system. Actions and proposi