Description

In this work, we present several ideas for planning under uncertainty. Our intention is to apply these ideas to recycle electromechanical devices with a robotic arm. This domain presents two challenges: (1) since is not possible to guarantee the desired action outcomes due to limited precision and exogenous factors, the transition model is probabilistic; and (2) it is impossible to know the whole configuration of the device that is being disassembled at once due to occlusions. We opt to formulate the problem as a goal-based MDP (Markov Decision Process) or, equivalently, an SSPP (Stochastic Shortest Path Problem).
In general, MDPs’ solutions consist in policies (i.e. a mapping from states to actions) rather than action sequences. Some of the most well-known algorithms to deal with MDPs are Value Iteration and Policy Iteration. However, these algorithms compute full policies and scale badly when the state consists of a large number of variables. Due to the curse of dimensionality, the state space grows too large. In addition, the computational effort invested in obtaining full policies for solving the MDP is wasted when new objects and, consequently, new state variables, are discovered. This renders the previous policy invalid because of the specification of the state and the goal changes.
Therefore, we explore the effectiveness of an on-line planning method based on determinization followed by classical planning. We take advantage of the well-performing and state-of-the-art systems such as Fast Downward, or the older but still widely used Fast Forward. We consider the following determinization methods, each presenting different strengths and drawbacks: All-Outcome, Single-Outcome, α-Cost-Transition-Likelihood and Hindsight Optimization. Another exploitable feature of our particular domain is that there are strong precedence relations between the components. This allows us to plan hierarchically, bounding the planning horizon and, thus, reducing the computational effort, especially if replanning is necessary.
We have hand-crafted a testbed of disassembly problems to test these approaches. In addition, the determinization techniques are tested against domains from past IPPCs (International Probabilistic Planning Competitions) to see how suitable they are under different circumstances.

The work is under the scope of the following projects:

• IMAGINE: Robots understanding their actions by imagining their effects (web)
• HuMoUR: Markerless 3D human motion understanding for adaptive robot behavior (web)