Motion planning under uncertainty for an autonomous system can be formulated as a Markov Decision Process. In this paper, we propose a solution to this decision theoretic planning problem using a continuous approximation of the underlying discrete value function and leveraging finite element methods. This approach allows us to obtain an accurate and continuous form of value function even with a small number of states from a very low resolution of state space. We achieve this by taking advantage of the second order Taylor expansion to approximate the value function, where the value function is modeled as a boundary-conditioned partial differential equation which can be naturally solved using a finite element method. We have validated our approach via extensive simulations, and the evaluations reveal that our solution provides continuous value functions, leading to better path results in terms of path smoothness, travel distance and time costs, even with a smaller state space.
The ability of mobile robots to generate feasible trajectories online is an important requirement for their autonomous operation in unstructured environments. Many path generation techniques focus on generation of time- or distance-optimal paths while obeying dynamic constraints, and often assume precise knowledge of robot and or environmental (i.e. terrain) properties. In uneven terrain, it is essential that the robot mobility over the terrain be explicitly considered in the planning process. Further, since significant uncertainty is often associated with robot and or terrain parameter knowledge, this should also be accounted for in a path generation algorithm. Here, extensions to the rapidly exploring random tree (RRT) algorithm are presented that explicitly consider robot mobility and robot parameter uncertainty based on the stochastic response surface method (SRSM). Simulation results suggest that the proposed approach can be used for generating safe paths on uncertain, uneven terrain. In this paper we present LQG-MP (linear-quadratic Gaussian motion planning), a new approach to robot motion planning that takes into account the sensors and the controller that will be used during the execution of the robotâs path. LQG-MP is based on the linear-quadratic controller with Gaussian models of uncertainty, and explicitly characterizes in advance (i.e. before execution) the a priori probability distributions of the state of the robot along its path. These distributions can be used to assess the quality of the path, for instance by computing the probability of avoiding collisions. Many methods can be used to generate the required ensemble of candidate paths from which the best path is selected; in this paper we report results using rapidly exploring random trees (RRT). We study the performance of LQG-MP with simulation experiments in three scenarios: (A) a kinodynamic car-like robot, (B) multi-robot planning with differential-drive robots, and (C) a 6-DOF serial manipulator. We also present a method that applies Kalman smoothing to make paths Ck-continuous and apply LQG-MP to precomputed roadmaps using a variant of Dijkstraâs algorithm to efficiently find high-quality paths.