Motion Planning Under Uncertainty
Related Projects:   
Current Contributors: Nancy Amato
Project Alumni: Ali Agha-mohammadi, Aditya Mahadevan, Jory Denny, Suman Chakravorty (Aerospace Engineering, TAMU)
Interns and undergrad students: Saurav Agarwal, Daniel Tomkins

Supported By: NSF

some text

The objective of our research is to present feedback-based information roadmap (FIRM), a multi-query approach for planning under uncertainty which is a belief-space variant of probabilistic roadmap methods. The crucial feature of FIRM is that the costs associated with the edges are independent of each other, and in this sense it is the first method that generates a graph in belief space that preserves the optimal substructure property. From a practical point of view, FIRM is a robust and reliable planning framework. It is robust since the solution is a feedback and there is no need for expensive replanning. It is reliable because accurate collision probabilities can be computed along the edges. In addition, FIRM is a scalable framework, where the complexity of planning with FIRM is a constant multiplier of the complexity of planning with PRM. FIRM is developed as an abstract framework. As a concrete instantiation of FIRM, we can adopt different belief stabilizers. For example, utilising stationary linear quadratic Gaussian (SLQG) controllers as belief stabilizers, we introduce the so-called SLQG-FIRM.

Feedback-based Information Roadmap


FIRM is a method for motion planning under uncertainty where nodes are belief space centers and edges are local-controllers. The power of this representation is that different edges of the roadmap are independent of each other.

Method overview

Key Properties
  • Abstract framework that is adaptable to different representations of uncertainty
  • Framework transforms the motion planning under uncertainty, which traditionally, equates to solving a partially observable Markov decision process to solving a Markov decision process on the FIRM graph
  • The graph is multi-query in the belief space
  • This medthod does not suffer from the curse of history

Robust Online Planning with FIRM


This section describes how to address the physical issues that arise when trying to conduct motion planning under uncertainty with FIRM.

Method overview

Proposed
Robust motion planning under uncertainty with FIRM is done with a dynamic replanning scheme. FIRM replans using receding horizon control in the belief space until the goal is found.
  • FIRM solves an optimization problem to find the optimal policy from a given node to the goal node.
  • Firm finds and applies the control which corresponds to the optimal policy at its given belief state<\li>
  • Observe the new observation
  • Compute the new belief
Notably, the optimal policy is recomputed at each iteration. Lazy Feedback Evaluation in Changing Environments To address changing environments, an online planner can use lazy evaluation. The basic idea is that at every node the robot re-evaluates only the next edge that it needs to take or a limited set of edges in the vicinity of the robot. By re-evaluation, we mean re-compute the collision probabilities along the edges. If needed, the dynamic programming problem is re-solved and a new feedback tree is computed. Handling the kidnapped robot problem To address this problem, a robot must be able to detect a kidnapped situation, localize itself, and replan. These issues can be handled respectively as follows:
  • A robot running firm can have an internal record of the relative ranges and bearings of the robot to landsmarks, noticing it has been kidnapped if a threshold is met
  • The robot enters an information gathering mode with a large covariance matrix
  • The robot need only traverse to the nearest node, since the FIRM graph is a multi-query graph