Global Motion Planning under Uncertain Motion, Sensing, and Environment Map

Our motivation is to enable efficient navigation with active sensing for marine robots operating in cluttered marine environment, such as around Kelongs (traditional fishing farms), sea-caves, offshore oil-rigs, and harbours. In these scenarios, a motion planner must take into account all three sources of uncertainty, i.e., motion, sensing, and environment map uncertainty. Water currents and wakes substantially aggravates the robots's control error. Noise from snapping shrimp can significantly aggravate sensing error of sonars. For many marine structures, e.g., Kelongs and sea-caves, the environment map can only be generated using sensors mounted on marine vehicles, which are subject to various substantial errors. Furthermore, these environment are often GPS-denied, as GPS signal is blocked by the structures. Therefore, our robots rely on laser or sonar for localization. Sonar disturbs marine life, and hence scanning should be done only when needed. Our goal is to develop motion planners that takes into account motion, sensing, and environment map uncertainty, to decide where should the robot move, and where and when should the robot scans the environment, so that the goal configuration is reached as fast as possible with minimum movement, sensing, and collision cost.

General POMDP planners can conceptually solve the above problem. But, even the best POMDP planner today perform poorly in problems with imperfect environment map, due to the high dimensionality of the state space and the long planning horizon. When both the environment map and robot configuration are not perfectly known, the POMDP state space S is a joint product between the configuration space and the space of possible environment maps, resulting in an extremely high dimensional state space. This dimensionality issue is aggravated in POMDPs, as their planning space is doubly exponential in dim(S). Furthermore, in most motion planning tasks, a robot needs to take many actions to reach the goal, resulting in a long planning horizon. And the complexity of planning often grows exponentially with the planning horizon.

To alleviate the above problems, we have developed a new point-based POMDP algorithm that takes into account uncertainty in motion, sensing, and environment map, for active sensing robots, called Guided Cluster Sampling (GCS). GCS alleviates the high dimensional state space issue by finding a small representative set of much smaller sub-spaces of the belief space, and using a sampled representation of these sub-spaces for planning. It alleviates the long planning horizon issue by constructing actions sequences to reduce the effective planning horizon.

We have applied GCS in simulations of several instances of navigation with active sensing for marine robots operating around Kelongs. The results indicate that GCS can generate reasonable strategies for problems that are unsolvable by the best POMDP solver today, and can substantially outperforms current practice (reactive greedy method) in marine robot operation.

A parking simulation around Kelongs. Orange: the particles representing the robot's belief over its environment. Green: The actual environment with circles marking the goal regions (the goal region is defined relative to the position of the structures). Yellow: the robot path. Red circle: sensing position. In the left picture, the robot starts from the bottom right, moving towards the red circle. At the position marked by the red circle, the robot takes a scan. However, due to sensing error, the robot does not receive any reading. The robot then updates its belief about the environment. Taking into account that the probability the robot does not perceive a feature when the feature is within the range limit of the sensor is much less than when the feature is outside the range limit of the sensor, the robot beliefs more that the structures lie towards the upper right corner. Therefore, it moves to the upper right corner to take another scan of the environment (middle picture). This time, the scan is a success. Although the robot still does not know the exact position of the structures, it knows enough to reach the goal region without collision despite its control error. Hence, without additional scanning, the robot directly moves into the goal region (right picture).

Same legend and scenario as above. But this time, the robot is able to perceive the features at the first scan and infer the position of the structures to the level sufficient for reaching the goal region without collision. Therefore, it does not perform the second scan, instead it moves directly to the goal region.


H. Kurniawati, T. Bandyopadhyay, and N.M. Patrikalakis. Global motion planning under uncertain motion, sensing, and environment map. In Proc. Robotics: Science & Systems, 2011.
bib |.pdf ]

H. Kurniawati, T. Bandyopadhyay, and N.M. Patrikalakis. Global motion planning under uncertain motion, sensing, and environment map. Submitted to Autonomous Robots special issue on selected papers from RSS 2011.
bib |.pdf ]

Last updated: 29 October 2011