Integrating preception with problem solving

Hsiang-Lung Wu, Alec Cameron, Leo Dorst, Madeleine Rosar, Paul Benjamin
SIGART, vol.2, no.4, 1991, pp.41-45.

Problem solving is a process to convert the world from an initial state to a goal state. This paper describes an approach that interleaves perception with action in problem solving. We presume that an intelligent agent starts this process with uncertain knowledge about the initial state of the world, a specified goal state, a given set of permissible actions to alter the world state, and a given set of sensors to observe the partially understood world state. The task is to generate and execute a plan to reach a state in which the agent knows that it has reached the goal.

Given a problem described by all feasible sequences of actions and perceptions applicable to converting any given state to the goal state, we demonstrate how to construct plans that can guide both action and perception by achieving a sequence of subgoals and show it is equivalent to decomposing the representation of the problem into components corresponding to achieving subgoals. We first show that feasible sequences of actions can be decompoed into components, independent of perception, for instance through a principal series (in the case of a group, a subnormal series). This leads to subgoals with which certain observables can be associated. On the other hand, the perceptive problem can be decomposed by switching on sensors in series and performing actions that make the perceived state indistinguishable from the goal sate. Finally, we show how perception can be integrated with problem solving; we use perception to guide actions; hence to reduce the overall cost of problem solving. The ideas are illustrated with problems taken from subgroups of Rubik's Cube; we are currently extending them to arbitrary semi-groups.

home ------