text: This work addresses the challenge of a robot using real-time feedback from contact sensors to reliably manipulate a movable object on a cluttered tabletop. We formulate contact manipulation as a partially observable Markov decision process (POMDP) in the joint space of robot configurations and object poses. The POMDP formulation enables the robot to actively gather information and reduce the uncertainty on the object pose. Further, it incorporates all major constraints for robot manipulation: kinematic reachability, self-collision, and collision with obstacles. To solve the POMDP, we apply DESPOT, a state-of-the-art online POMDP algorithm. Our approach leverages two key ideas for computational efficiency. First, it performs lazy construction of a configuration-space lattice by interleaving construction of the lattice and online POMDP planning. Second, it combines online and offline POMDP planning by solving relaxed POMDP offline and using the solution to guide the online search algorithm. We evaluated the proposed approach on a seven degree-of-freedom robot arm in simulation environments. It significantly outperforms several existing algorithms, including some commonly used heuristics for contact manipulation under uncertainty.
  @cite_30: 
  @cite_38: This paper formulates the optimal control problem for a class of mathematical models in which the system to be controlled is characterized by a finite-state discrete-time Markov process. The states of this internal process are not directly observable by the controller; rather, he has available a set of observable outputs that are only probabilistically related to the internal state of the system. The formulation is illustrated by a simple machine-maintenance example, and other specific application areas are also discussed. The paper demonstrates that, if there are only a finite number of control intervals remaining, then the optimal payoff function is a piecewise-linear, convex function of the current state probabilities of the internal Markov process. In addition, an algorithm for utilizing this property to calculate the optimal control policy and payoff function for any finite horizon is outlined. These results are illustrated by a numerical example for the machine-maintenance problem.
  @cite_9: Humans are capable of manipulating objects based solely on the sense of touch. For robots to achieve the same feat in unstructured environments, global localization of objects via touch is required. Bayesian approaches provide the means to cope with uncertainties of the real world, but the estimation of the Bayesian posterior for the full six degrees of freedom (6-DOF) global localization problem is computationally prohibitive. We propose an efficient Bayesian approach termed Scaling Series. It is capable of solving the full problem reliably in real time. This is a Monte Carlo approach that performs a series of successive refinements coupled with annealing. We also propose an analytical measurement model, which can be computed efficiently at run time for any object represented as a polygonal mesh. Extensive empirical evaluation shows that Scaling Series drastically outperforms prior approaches. We demonstrate general applicability of the approach on five common solid objects, which are rigidly fixed during the experiments. We also consider 6-DOF localization and tracking of free-standing objects that can move during tactile exploration.
  @cite_24: In this paper, we bring techniques from operations research to bear on the problem of choosing optimal actions in partially observable stochastic domains. We begin by introducing the theory of Markov decision processes (mdps) and partially observable MDPs (pomdps). We then outline a novel algorithm for solving pomdps off line and show how, in some cases, a finite-memory controller can be extracted from the solution to a POMDP. We conclude with a discussion of how our approach relates to previous work, the complexity of finding exact solutions to pomdps, and of some possibilities for finding approximate solutions.
  @cite_15: 
  @cite_16: This paper introduces a tactile or contact method whereby an autonomous robot equipped with suitable sensors can choose the next sensing action involving touch in order to accurately localize an object in its environment. The method uses an information gain metric based on the uncertainty of the object's pose to determine the next best touching action. Intuitively, the optimal action is the one that is the most informative. The action is then carried out and the state of the object's pose is updated using an estimator. The method is further extended to choose the most informative action to simultaneously localize and estimate the object's model parameter or model class. Results are presented both in simulation and in experiment on the DARPA Autonomous Robotic Manipulation Software (ARM-S) robot.
  @cite_25: We describe a simple approach for executing manipulation programs in the presence of significant, but bounded, uncertainty. The key idea is to maintain a belief-state (a probability distribution over world states) and to execute fixed trajectories relative to the most-likely state of the world. These world-relative trajectories, as well as the transition and observation models needed for belief update, are all constructed off-line, so the approach does not require any on-line motion planning.
  @cite_11: In this paper, we present an approach for robustly grasping objects under positional uncertainty. We maintain a belief state (a probability distribution over world states), model the problem as a partially observable Markov decision process (POMDP), and select actions with a receding horizon using forward search through the belief space. Our actions are world-relative trajectories, or fixed trajectories expressed relative to the most-likely state of the world. We localize the object, ensure its reachability, and robustly grasp it at a goal position by using information-gathering, reorientation, and goal actions. We choose among candidate actions in a tractable way online by computing and storing the observation models needed for belief update offline. This framework is used to successfully grasp objects (including a powerdrill and a Brita pitcher) despite significant uncertainty, both in simulation and with an actual robot arm.
summary: One common approach is to plan a sequence of move-until-touch actions that localize an object, then execute an open-loop trajectory to complete the task @cite_9 @cite_16 @cite_15 . Other approaches, like our own, formulate the problem as a POMDP @cite_38 @cite_24 and find a policy that only takes information-gathering actions when they are necessary to achieve the goal @cite_30 @cite_25 @cite_11 .