A decentralized trajectory generation algorithm for multi-robot systems

JANUARY 15, 2019 by Ingrid Fadelli , Tech Xplore

**A decentralized trajectory generation algorithm for multi-robot systems
Snapshots while the robots are navigating across different unknown environments using the algorithm proposed in this work. Credit: Govind Aadithya R et al.

Researchers at the SRM Institute of Science and Technology in India have recently developed a decentralized trajectory generation algorithm for multi-agent systems. Their algorithm, presented in a paper pre-published on arXiv, can generate collision-free trajectories for robots when provided with an initial state and desired end pose.

“Govind and his team ambitiously approached me seeking my suggestion for their bachelor’s project,” Sivanathan K, senior researcher who supervised the study, told TechXplore. “Knowing their mathematical ability, I felt that they should be assigned a challenging problem that the future is waiting to solve. As the world is moving toward autonomous cars, I suggested developing a decentralized algorithm for autonomous vehicles to navigate intersections. We felt that the performance of the algorithm was not up to standards, so we extended the work to developing an algorithm that could enable autonomous vehicles to navigate through an unknown environment, avoiding collision with other robots/obstacles.”

Multi-robot systems involve a number of robotic agents or autonomous vehicles collaborating on a variety of tasks. These systems could have interesting applications in a number of areas, including transportation, entertainment, security and space exploration.

When several robots are working together on a given task, their trajectories require careful planning to make sure that the robots do not collide with one another and that their dynamic limits are not violated. So far, most approaches for trajectory generation have been centralized, which means that they generate trajectories beforehand and then transmit them to individual robots.

While centralized approaches work well in known environments and with a limited number of robots, they are very difficult to apply on a larger scale. In recent years, therefore, researchers have been working on decentralized approaches that can continuously re-plan trajectories, responding to unexpected changes or obstacles in the environment.

**A decentralized trajectory generation algorithm for multi-robot systems
The system overview of an individual agent. The orange arrows represent raw data,red represent data from external sources and black represent processed data and flow side. The focus of this work is the shaded portion. Credit: Govind Aadithya R et al.

The team of researchers at SRM Institute developed a new decentralized algorithm for trajectory generation of multi-agent systems. Their approach follows a two step process, generating collision-free convex regions that a robot will be constrained in, by predicting other robots’ positions.

“Our approach has two sub-objectives. The first is the Identification of the environment, which includes map generation for the self and trajectory prediction for others in the environment to identify the ego’s (from the point of view of the vehicle of interest) safe region,” Govind Aadithya R, one of the researchers who carried out the study, Told TechXplore. “After that comes the objective of navigation within the safe region in order to reach the desired destination, for which we generate the ego’s trajectory with the available information and re-plan it on a regular basis to account for changes happening around the ego. To ensure that the ego is moving along the specified path, the states are tracked using a trajectory tracker.”

Govind and his colleagues employed a simple method for obstacle detection, using local shape-based maps to formulate safe regions for individual agents. Based on this data, their algorithm predicts trajectories for other robots and incorporates these into the model to avoid collisions by re-sizing the regions in which a robot can navigate without colliding.

“For me, one of the most meaningful takeaways from this work is that continuous time collision checking is of prime importance for safe collision-free navigation,” Shravan Krishnan, another researcher involved in the study, told TechXplore. “Also, for collision avoidance, we found that complex mapping techniques are not of paramount importance but are still a necessity when dealing with optimum usage of space. This implies that for conservative maneuvers, the obstacle representations based on simple geometry suffice but for dynamic and aggressive maneuvers that utilize full space, complex geometries are a necessity.”

The researchers evaluated their approach in simulations on the Gazebo platform, using ROS with flat aerial robots and non-holonomic wheeled robots; in both intersection-like and unstructured environments. Their algorithm was able to effectively generate smooth trajectories in constrained environments, avoiding collisions between robots.

“Taking this forward, we would like to extend the algorithm in 3-D, adding one more dimension,” Vijay Arvindh B, one of the researchers who carried out the study, told TechXplore. “We are currently working on the flaws that need to be fixed in order to evaluate the algorithm in 3-D.”

More information: Online decentralized receding horizon trajectory optimization for multi-robot systems. arXiv:1812.11135 [cs.RO]. arxiv.org/abs/1812.11135

Collected at: https://techxplore.com/news/2019-01-decentralized-trajectory-algorithm-multi-robot.html?utm_source=nwletter&utm_medium=email&utm_campaign=daily-nwletter