A chance constrained motion planning system for high-dimensional robots

November 20, 2018 by Ingrid Fadelli, Phys.org
Simulation environment for a robot in which the researchers tested their algorithm. Credit: Dai et al.

Researchers at MIT's Computer Science and Artificial Intelligence Laboratory have recently developed a chance-constrained motion planning system that can be applied to high degree-of-freedom (DOF) robots under motion uncertainty and in cases of imperfect state information. Their approach, outlined in a paper pre-published on arXiv, can find feasible trajectories that satisfy a user-specified bound over the probability of collision.

"The main inspiration of this work is the limitation of existing chance-constrained planners," Siyu Dai, one of the researchers that carried out the study, told TechXplore. "I found out that many state-of-the-art motion planners require formulating obstacles into convex shapes, which is infeasible for planning in high-dimensional domains, for example manipulator motion planning. Other mainstream chance-constrained motion planners are based on rapidly-exploring random tree (RRT) methods, of which the speed in high-dimensional planning task is very concerning."

To address the limitations of existing motion planning systems, Dai and her colleagues set out to develop a fast-reactive and chance-constrained motion planner. Such a motion planner would be particularly useful for robots completing tasks that are subject to severe disturbances and limited observations, such as underwater manipulation.

Probabilistic Chekov (p-Chekov), the system they created, is based on their previous work in deterministic motion planning, which integrated trajectory optimization into a sparse roadmap framework. P-Chekov uses a linear-quadratic Gaussian motion planning approach to estimate a robot's state probability distribution. It then applies quadrature theories to waypoint risk estimations and adapts risk allocation approaches to assign allowable probabilities of failure to waypoints.

"The chance-constrained motion planning system developed in our paper includes a deterministic planning component and a risk assessment component," Dai explained. "The deterministic component first constructs a roadmap consisting of feasible, collision free edges based on the environment information. In the online planning tasks, it then searches for a feasible trajectory from the roadmap and smoothens it with a trajectory optimizer. This trajectory is then passed onto the risk assessment component, which evaluates the risk of collision based on the estimation of noises."

Simulation environment for a robot in which the researchers tested their algorithm. Credit: Dai et al.

If the risk of collision calculated by P-Chekov's risk assessment component violates the predefined chance constraint, the trajectory is returned to the deterministic planner and new constraints are added, in order to find a trajectory with lower risk. If the risk of collision satisfies the chance constraint, the system simply executes the proposed trajectory.

Contrarily to existing risk-aware motion planners, P-Chekov can be applied to high-DOF robotic planning tasks, without having to formulate obstacles into convex shapes. In simulation tests, the system effectively reduced the risks of collision and satisfied user-specified chance constraints in real-world planning scenarios commonly encountered by high-dimensional robots.

"We established a chance-constraint motion planning system that can incorporate high-dimensional motion planning tasks," Dai said. "This means that chance-constrained motion planning is no longer restricted to driving-type tasks, but can now be applied to mobile robots with arms, for example human support robots and underwater manipulators, which can make plans based on different requirement of risk level."

In the future, P-Chekov could be applied to a variety of high-dimensional robots, improving their motion planning under uncertainty. Despite its promising results, the outcomes of the system's planning phase can sometimes be overly conservative, due to suboptimal risk allocations and a limited number of quadrature nodes.

In preliminary tests, the researchers have already started evaluating techniques that could enhance the system's utility. Meanwhile, they are also planning to improve P-Chekov's collision probability estimation algorithm, to further boost its ability to avoid conflicts.

"The main direction of our next studies will be improving the risk assessment algorithm in order to speed up the whole motion planning process and make the fast-reactive," Dai said.

More information: Chance constrained motion planning for high-dimensional robots. arXiv:1811.03073 [cs.RO]. arxiv.org/abs/1811.03073

© 2018 Science X Network