IIT Madras researchers develop motion planning algorithms that can think like humans

New Delhi, Dec 19

Researchers at the Indian Institute of Technology (IIT), Madras have developed a class of fast and efficient “motion planning” algorithms which can think like human beings and enable autonomous aerial, ground or surface vehicles to navigate obstacle-cluttered environments.

According to the team, the algorithms have been developed on a novel notion of ‘Generalised Shape Expansion’ (GSE) that enables planning for a safe and dynamically feasible trajectory for autonomous vehicles.

These approaches have been found to yield superior results compared to many of the existing seminal and state-of-the-art motion planning algorithms.

Because of its novel calculation of “safe” region, it provides a crucial advance during time-sensitive planning scenarios arising in applications like self-driving cars, disaster response, ISR operations, aerial drone delivery and planetary exploration, among others, the team claimed.

Unmanned Aerial Vehicles (UAVs) are often deployed to survey affected regions and scan debris for search and rescue missions. Since in such applications, UAV paths need to be planned in advance in a time-critical manner, these algorithms can play a key role, they said.

The research led by Satadal Ghosh, Assistant Professor, Department of Aerospace Engineering, IIT Madras, has published several research papers in internationally reputed peer-reviewed journals like AIAA Journal of Guidance, Control, and Dynamics, and IEEE Control Systems Letters, and top-tier conferences like IEEE Conference on Decision and Control (CDC), American Control Conference (ACC) and AIAA SciTech.

The team included IIT Madras alumni Vrushabh Zinage, a doctoral research scholar at University of Texas Austin (USA), Adhvaith Ramkumar, a graduate student at Warsaw University of Technology, Poland and Nikhil P, an analyst at Goldman Sachs.

“The GSE-based algorithms function by calculating a ‘safe’ region consisting of large ‘visible’ areas in the environment, customised to ensure navigability,” Zinage said.

“Following this, the algorithms select a random point in this ‘visible’ region and connect it through a safe ‘edge’ to the safely reachable regions discovered so far. Eventually, the algorithms can almost always connect any two points in any environment, which satisfies certain basic criteria,” Zinage said.

The researcher explained that the GSE-based algorithms’ main advantage lies in the significant improvement of computational efficiency over several other well-established motion planning algorithms.

This naturally leads to strong applicability of the GSE-based algorithms in applications, where planning is time-sensitive.

“Instead of using computationally heavy dedicated collision checking modules, these algorithms leverage the novel notion of ‘generalised shape’, which gives a maximal representation of the free-space that is reachable from a point in the environment, which is almost similar to updating of human perception about the ‘safe’ space to move through surrounding him or her,” said Adhvaith Rajkumar.

This, in essence, significantly improves rapidity of exploration of the environment leading to the necessity of only very few iterations of a GSE-based algorithm to connect the initial and goal regions.

Explaining the applications of the “motion planning” algorithms, Satadal Ghosh, Assistant Professor, Department of Aerospace Engineering, IIT Madras, said, “Drones equipped with our algorithms can be of major use during disaster management and response scenarios.” “In the wake of a disaster event such as an earthquake, UAVs are often deployed to survey affected regions and scan debris for search and rescue missions. Since in such applications UAV paths need to be planned in advance in a time-critical manner, our algorithms can play a key role,” he said.

“Broadly speaking, the class of GSE-based algorithms has promising potential in autonomous applications ranging over warehouse material movement, inspection of project commissioning, drone delivery, disaster management, self-driving cars, and so on. For strategising coordinated motion in a multi-vehicle set-up also these algorithms could be leveraged,” he said.

The current status of this research, according to the team, is limited to theoretical development and improvement of the GSE-based algorithms and extensive realistic simulation-based validation of the same.

The researchers are further planning to implement these algorithms on unmanned aerial and ground vehicles in the near future.

“In dynamic environments, where knowledge of the environment is limited to information from on-board sensors or when mission commands intervene in the movement of vehicles because of dynamically evolving mission-critical requirements, for example intelligence, surveillance and reconnaissance (ISR) operations or planetary exploration using rovers, frequent time-critical re-planning of motion is usually called for,” Ghosh said.

“Even in such cases also, our present study suggests that on-the-go motion planning becomes significantly easier by our GSE-based algorithms because of the unique nature of the visible regions calculated by these algorithms at different points in the environment,” Ghosh said. PTI