Many robotic systems deal with uncertainty by performing a sequence of information gathering actions. In this work, we focus on the problem of efficiently constructing such a sequence by drawing an explicit connection to submodularity. Ideally, we would like a method that finds the optimal sequence, taking the minimum amount of time while providing sufficient information. Finding this sequence, however, is generally intractable. As a result, many well-established methods select actions greedily. Surprisingly, this often performs well. Our work first explains this high performance -- we note a commonly used metric, reduction of Shannon entropy, is submodular under certain assumptions, rendering the greedy solution comparable to the optimal plan in the offline setting. However, reacting online to observations can increase performance. Recently developed notions of adaptive submodularity provide guarantees for a greedy algorithm in this online setting. In this work, we develop new methods based on adaptive submodularity for selecting a sequence of information gathering actions online. In addition to providing guarantees, we can capitalize on submodularity to attain additional computational speedups. We demonstrate the effectiveness of these methods in simulation and on a robot.
@cite_28 @cite_3 select a sequence of uncertainty reducing tactile actions through forward search in a POMDP. Possible actions consist of pre-specified world-relative trajectories @cite_28 , motions based on the current highest probability state. Actions are selected using either information gain or probability of success as a metric @cite_29 , with a forward search depth of up to three actions. Aggressive pruning and clustering of observations makes online selection tractable. While Hsiao considers a small, focused set of actions (typically ) at a greater depth, we consider a broad set of actions (typically ) at a search depth of one action.
@cite_28 @cite_29 @cite_3
37733164 2226137842
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. 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.