Mini Project 1 - adigoswami/MiniProject1 GitHub Wiki

Authors

• Aditya Goswami
• Lambros Mertzanis

Introduction

This page is a summary of five papers about path planning from the ICRA conference of 2019.

All these papers involve multiple robots (also known as agents) working together for a common goal. Such a goal could be:

• Inspecting infrastructure such as a water dam for damage due to corrosion.
• Monitoring a large farm for spots where pesticide needs to be applied.
• Detecting the source of a wildfire.
• Rescuing a skier trapped in the snow.
• Searching for survivors after an earthquake.
• Moving objects freely around a factory without being limited to fixed assembly line positions.

In the case of a single robot, these problems are either solved or their solution depends on advancement in other research areas such as computer vision and kinematics. The multi-robot case suffers from the curse of dimensionality which mandates a need for novel creative solutions. In terms of time complexity, most of these problems are NP-hard. This implies that optimal solutions can be found in a timely manner only when utilizing a very small amount of robots, typically less than 10. Alternatively, one can resort to approximate solutions that are attractive when tight approximation bounds can be proved. The specialization can break the curse of dimensionality. Many NP-hard problems have specific subcases that have optimal polynomial solutions. The interesting research challenge is to set the right assumptions and build a model that generates polynomial algorithmic problems that answer important practical questions.

A vital sub-area of path planning that strongly relates to the papers summarised here is coverage. Robots are equipped with sensors. These sensors have a limited range and hence at any given moment they can only collect data from a small area in their vicinity. But the robots need to cover a much larger area. How can the robots coordinate their movements in order to cover the entire area as fast as possible? This is the fundamental decision making question that connects the papers included in this summary. Arguably, none of these papers is truly groundbreaking. Nonetheless, they all are noteworthy because each of them adds a unique flair to the problem of coverage by offering a meaningful improvement to a different aspect of the problem.

Covered papers

(Click on each paper to see its summary.)

• "Turn-minimizing multirobot coverage." by Isaac Vandermeulen, Roderich Groß, and Andreas Kolling
• "PRIMAL: Pathfinding via reinforcement and imitation multi-agent learning." by Guillaume Sartoretti, Justin Kerr, Yunfei Shi, Glenn Wagner, TK Satish Kumar, Sven Koenig, and Howie Choset
• "Coordinating multi-robot systems through environment partitioning for adaptive informative sampling." by Nicholas Fung, John Rogers, Carlos Nieto, Henrik I. Christensen, Stephanie Kemna, and Gaurav Sukhatme
• "Multi-robot informative path planning with continuous connectivity constraints." by Ayan Dutta, Anirban Ghosh, and O. Patrick Kreidl
• "Coverage of an Environment Using Energy-Constrained Unmanned Aerial Vehicles." by Kevin Yu, Jason M. O’Kane, and Pratap Tokekar

Conclusion

Robots can't turn instantly. So the number of turns can affect the coverage time more significatly than previously thought. That is why Paper 1 tries to minimize time by minimizing the number of turns. Despite only having access to local information.

Paper 2 combines reinforcement and imitation learning to compute multiple individual collision-free paths.

Paper 3, attempts to maximize the expected information gained per travelled distance. Their purpose is efficiently to coordinate robots that provide coverage in structured environments.

Paper 4 offers a solution to the multi-robot informative path planning (MIPP) problem under continuous connectivity constraints. Their ideas stem from graph-theoretic concepts. Firstly, they use bipartite graph matching for guiding the robots along maximally informative paths that remain collision-free. Secondly, the use minimal vertex separators in order to enforce their connectivity constraints.

Every autonomous robot needs a battery to operate. Nevertheless, batteries are notorious for their low energy density in comparison to fossil fuels. In paper 5, this issue is acknowledged. They propose an algorithm for optimal coverage of boustrophedon cells by a UAV that relies on a UGV. The UGV follows the UAV around and serves it as a charging station. Without this support, the UAV would not be able to carry through its coverage mission.

Planning and Decision-making are critical components of autonomy in robotic systems. These components are responsible for making decisions that range from path planning and motion planning to coverage and task planning to take actions that help robots understand the world around them better. All these papers have dealt with problems pertaining to coverage, exploration, path planning, coordination etc. Their one common objective is to achieve autonomy which further enriches decision-making in complex scenarios where the situation can be time-sensitive or limited under austere constraints.