EWHA's Research Power for Science & Engineering
February, 2016
EWHA's Research Power for Humanities, Arts & Social Sciences


Massively Parallel Robot Motion Planning Algorithms under Uncertainty using Partially-Observable Markov Decision Process





by Prof. Young J. Kim (kimy@ewha.ac.kr)

Department of Computer Science and Engineering




Motion planning is an important problem in robotics, intelligent systems, computer animation, game artificial intelligence, robotic surgery, computer-aided design, and manufacturing systems. Motion planning focuses on determination of a safe path or series of actions that enable robots to reach a target while minimizing resources. Many approaches have been proposed to solve motion planning problems, but these approaches are used to solve general motion planning problems under the assumption that the information about a robot and its surrounding environment are known. Also, they assume that the robot controllers and sensors are precise in terms of their functionalities. However, a robot in the real world encounters many uncertainties caused by inaccurate sensors, imprecise controls, and unexpected changes in and imperfections of information about the real-world environment. These inaccuracies can lead the robot to make wrong motions and seriously risk the reliability of robot motion planning.

Figure 1 Various motion planning benchmarks under uncertainties. Robots need to find a collision-free path from their initial positions to the destinations without precise information about their environment.

A general framework to address uncertainties arising in different parts of motion planning is the partially observable Markov decision process (POMDP)-based planner. In principle, this method addresses all uncertainties with its stochastic planning process; for instance, a robot’s state is defined as a belief represented by a probability distribution over a state space. Even though the POMDP model can deal with a wide range of uncertainties, it is notoriously challenging to precisely evaluate, in particular, continuous-state POMDPs are computationally intractable.


A recent research article written by Prof. Young J. Kim and his colleague proposed the use of the massive parallelism of graphics processing units (GPUs) to accelerate POMDP computation for robot motion planning. They also presented a CPU-GPU hybrid method for solving more complicated POMDP planning problems. Their algorithm is regarded as the first massively parallel algorithm that efficiently executes POMDP. In their experiments, their algorithms outperform the existing CPU-based algorithm by a factor of 75–99 based on the chosen benchmark.

This work was published in the international journal of robotics research 2015, which is ranked as the top research journal in robotics area according to 2014 journal citation reports by Thomson Reuters.



Figure 2 Our GPU-based method (red) performs 10,000 simulations per second on average irrespective of the problem size, while an earlier CPU-based method does only 100~200 simulations in the same amount of time.



* Related article and site
Massively parallel motion planning algorithms under uncertainty using POMDP
August 21, 2015, International Journal of Robotics Research

Project web site: http://graphics.ewha.ac.kr/gpomdp/

52, Ewhayeodae-gil, Seodaemun-gu, Seoul 120-750 Korea
Tel +82-2-3277-2114  Fax +82-2-393-5903
Mobile View