Coordinating Multi Robot Systems through Environment Partitioning for Adaptive Informative Sampling - adigoswami/MiniProject1 GitHub Wiki
By Nicholas Fung, John Rogers, Carlos Nieto, Henrik I. Christensen, Stephanie Kemna, and Gaurav Sukhatme
In exploration tasks that are time-sensitive, it becomes crucial to minimize the repetition of work and reduce the interference of working agents. The more robots are doing the same task, the more likely it becomes that these robots will have overlapping paths and collide with each other. This introduces another open-ended challenge commonly faced in path planning for robots. Minimizing the repetition of work and reducing interference of robots. In the case of an unmapped environment, spatial modeling of the environment is useful. One effective technique to create spatial modeling of the environment is by using Gaussian Process regression. When the information from each robot is used in addition to the Gaussian Process (GP) model’s prediction, it is called informative sampling.
When Informative sampling locations are determined after the model has been created, it is known as off-line informative sampling, on the other hand when the robot samples the data while creating the model, it is referred to as online or adaptive informative sampling. This paper presents a multi-robot coordination approach for adaptive informative sampling in a structured environment. It includes:
- Identifying high priority points of interest according to an information gain rate-adaptive metric.
- An efficient partitioning of the environment.
- A strategy for over segmenting a region to more deliberately coordinate multiple robots
- An implementation and experimental evaluation of these strategies.
The approach involves tasking the robots to model RSSI signals for an established environment using prior knowledge of the environment but without knowing RSSI topology. The robots have to traverse the area and measure the environment according to expected information gain per distance traveled. Utilizing a high-level approach for coordination in which the central tasking unit separates the robots by directing to different areas of the environment. This whole process is divided into three parts:
- Signal modeling by GP regression. In this module, the GP approximates measurements at different locations with Gaussian functions based on prior mean and covariance function. Thus for each sampling location, the GP has a predictive mean and predictive variance. Variance and length scale become GP’s hyperparameters. The first GP model is created from real-world RSSI data in a controlled environment. The RSSI readings are collected and GP regression is used to create the RSSI model from the sensor data. This becomes the ground truth for evaluation. For real-world experimentation, there is no ground truth model and instead, performance was evaluated based on the overall entropy of the environmental model.
- Information Gain Utility. Since the RSSI is modeled as a Gaussian process, the differential entropy of a normal distribution is used which is independent of the mean of normal distribution. Using the differential entropy for each point of interest, the system seeks to minimize the entropy the map by tasking robots to points of high entropy.
- Multi-robot coordination and task allocation. Partitioning of the sampling space into distinct regions and assign a robot to each partition. For partitioning, a graph structure is formed representing the points of interest within the environment. Then with the help of the Floyd-Warshall algorithm, the shortest graph distance between each vertex is found. These values are stored in a distance matrix. This approach requires creating a number of partitions equal to the number of robots (equal partitioning). Then a task assignment procedure is used to assign a partition to each robot.
It's nearly impossible to efficiently produce an equal partitioning. Under-partitioning is undesirable because it lead to idle robots left without a task. Hence over-partitioning (over-segmenting) is by far the most likely outcome. In this case all robots are assigned a partition to explore but some partitions do not get a robot assigned to them. In order to make sure that all partitions are explored according to their entropy, robots will periodically be reassigned to the least explored partitions (i.e. of the highest entropy).
The simulation results in this paper show that the information rate-adaptive approach performed better than the nearest neighbor baseline approach in all instances. The evaluation was done using root-mean-squared error (RMSE) between ground truth (GP model of real-world data) and the GP model was created through sensor measurements by the simulated robot. These results showcase their achievement of increased rate of information gain by effectively decreasing entropy.