Multi Robot Informative Path Planning with Continuous Connectivity Constraints - adigoswami/MiniProject1 GitHub Wiki
By Ayan Dutta, Anirban Ghosh, and O. Patrick Kreidl
The goal of multi-robot informative path planning (MIPP) is to simultaneously plan paths for multiple robots while avoiding collisions such that the collected information is maximised. In order to make the right decisions, robots need to constantly communicate with each other. One robust way to guarantee communication is continuous connectivity. This is equivalent to constantly maintaining a connected graph where each vertex represents a robot and each edge represents a direct communication link between two robots (both robots are in each other's communication range). In this paper, or robots need to be able to communicate (either directly or indirectly) with a mobile base station, which is a robot with powerful processing and storage capabilities. This is the first piece of work that tries to solve MIPP in the case of continuous connectivity and on top of that their solution is proven to be deadlock and livelock free.
Earlier work includes the use of Gaussian Processes to the model environment and underlying spatial information. Proposals included a branch-and-bound based budgeted path planning technique to solve the problem. Theoretical approximation guarantees for this algorithm are shown by exploiting the submodularity property of mutual information.
In this paper, the bipartite graph matching technique is used to solve MIPP while continuous connectivity constraint is imposed using another graph-theoretic concept – minimal node separators. There are discrete locations that need to be visited by the robots, called points of interest (POI). The main objective is to visit as many of them so that the collected information can be maximised. The central limitation is that there is a strict maximum number of points that each robot is allowed to visit. Entropy maximization is done to find the unvisited POIs in the environment that contain the highest amount of uncertainty so that they can be prioritised when deciding which points to visit next. Robots who refuse to move out of their current location for too long are severely penalised. To achieve maximum informative paths, an instance of the maximum weighted bipartite matching problem is solved.
In the simulation, it appears that the correlation between POIs lessens as the inter-distance increases which means that the entropy estimation becomes less accurate. Another shortcoming that is experimentally observed is that the produced paths are not overlap-free. Finally, it would be interesting to measure how this algorithm fares when the communication links become unreliable and unforeseen obstacles appear in front of robots.