Parallelized energy minimization for real-time Markov random field terrain classification in natural environments

Regarding collision avoidance, precise track following, a robust and fast obstacle detection, and surface information extraction, terrain classification in unstructured natural environments is a complex and challenging task. In our scenario, an autonomous ground robot has to explore rough terrain without any knowledge of underlying road networks, as they could be available in form of a given map. Therefore, the robot has to detect surface conditions and obstacles by itself in real-time. Our robot uses the data of a 3D Laser range finder to perceive the environment. Due to the movement of the robot over rough terrain or sensor noise, the perceived information may be disturbed or erroneous. Markov random fields allow an incorporation of neighborhood information to improve robustness against such influences. Our previously published terrain classification algorithm achieves recall ratios of about 90% for detecting obstacles and drivable areas. The system operates in realtime at distances of up to 20 m. In order to further increase the processible area and therefore enable safe navigation at higher speeds, we seek to optimize the system performance using multicore CPU and GPGPU hardware. In this paper, we extend our previous terrain classification approach and present runtime optimizations for our Markov random field energy minimization via Gibbs sampling. Besides memory optimizations, we present a solution to parallelize the terrain energy minimization using multiple CPU threads. Further, we introduce a parallelization performed on the graphics card. While maintaining the aforementioned high recall ratios, we are able to accelerate energy minimization by a factor 10 which allows us to process a 2.5 times larger area in real-time.