A global motion-planning approach based on local experiences

April 2, 2019 by Ingrid Fadelli, Phys.org
An illustration of the proposed framework in a planar manipulator. Credit: Chamzas, Shrivastava & Kavraki.

While humans can execute motions naturally and instantaneously, robots require advanced motion planning strategies in order to navigate their surroundings. Motion planning is thus a key area of robotics research, aimed at developing tools and techniques that allow robots to operate autonomously in a variety of environments.

While past studies have introduced a variety of techniques, most notably sampling-based algorithms, most of them do not perform optimally in all environments. A key limitation of many of these approaches is that they approximate the connectivity of high-dimensional spaces with a small number of samples, which hinders their performance in scenarios where areas necessary for the connectivity of the space have a low probability of being sampled. This is commonly referred to as the "narrow passages problem."

To address the limitations of existing planning methods, researchers at Rice University, in Texas, have developed a new approach that decomposes the workspace into local primitives, memorizing their local experiences in the form of local samplers and storing these in a database. Their method, outlined in a paper pre-published on arXiv, is mainly a proof of concept, as it has so far only been tested in a rather simplified geometric setting. Nonetheless, the work of these researchers has the potential of solving some key challenges encountered in motion planning research.

"Our study focused solely on the geometric motion planning problem," Constantinos Chamzas, one of the researchers who carried out the study, told TechXplore. "In a nutshell, you have a and some obstacles and you want to find a path to move your robot from point A to point B without colliding with the obstacles."

In addition to these general motion planning capabilities, in real-life scenarios (e.g. while performing house chores) a robot should also solve continuously repeating motion planning queries. Most existing motion planning approaches force robots to complete real-life tasks by resolving new queries from scratch, even if a fresh query resembles one that was successfully completed in the past.

Example of a robot picking up cylinders from a bookcase, which is a task with repetitive motion planning queries. Credit: Chamzas, Shrivastava & Kavraki.

Researchers are hence trying to develop new techniques that use the solutions to previous motion plans to inform the search for a solution to a fresh similar motion planning query. The approach devised by Chamzas and his colleagues achieves this by using prior environment-related knowledge that specifically targets previously encountered narrow passages to adapt its sampling strategy for the problem at hand.

"During training, the proposed method breaks up the given problem into easier sub-problems, solving each one individually, and then stores these sub-solutions into a database in the form of sampling distributions," Chamzas explained. "When a new planning problem arises, the global problem is decomposed into local ones again, and our method retrieves the relevant sampling distributions that correspond to the local ones to create a global sampling distribution that guides the search much more informatively."

Essentially, the motion planning approach devised by Chamzas and his colleagues breaks up a problem into sub-problems, combining traditional database methods with informed sampling. This distinguishes it from existing approaches, which typically use a database with pre-computed solutions that are repaired at runtime or use models that try to infer a good sampling distribution for a given environment.

"The two main contributions of our study are that certain problems, which were previously practically impossible to solve with traditional methods, can be solved by being decomposed and that using this combination of databases/sampling is more effective in certain cases than other methods," Chamzas said.

So far, the researchers have evaluated their method in preliminary tests with simple geometric primitives. The results are promising, as their method allowed them to solve that previous approaches were either unable to solve or solved very poorly.

In the future, the approach proposed by Chamzas and his colleagues could help to overcome some of the limitations of existing motion planning approaches, allowing robots to transfer previously acquired knowledge to different environments and thus enhancing their performance. The researchers are now planning to apply the same approach in more complicated geometric environments. They would also like to explore ways in which their method could learn sampling distributions, rather than fitting them to older solutions.

More information: Using local experiences for global motion planning. arXiv:1903.08693v1 [cs.RO]. arxiv.org/abs/1903.08693

© 2019 Science X Network