A branch of multi-robot systems called swarm robotic (SR) systems investigates algorithms and problem-solving techniques inspired by insects like bees, ants, and termites. SR systems consist of large numbers of robots that do not have any centralized control, and do not try to compute optimal solutions. Instead, they rely on heuristic, “best-guess” decision making by individual robots to allocate tasks to achieve the overall system goal. An example would be a swarm of mail-delivery robots that would communicate amongst themselves, not through a central post office, to determine the most efficient routes.
John Harwell, a PhD student in the Department of Computer Science and Engineering and a member of the research group of MSI PI Professor Maria Gini, is studying the “foraging problem,” in which swarms gather objects and bring them to a central location. Part of his research received a 2020-21 University of Minnesota Informatics Institute MnDRIVE PhD Graduate Assistantship. Results from this part of the research include:
- Quantitative measurements for the four SR system properties: scalability, emergent self-organization, flexibility, and robustness. Measuring these properties precisely is required in order to develop more sophisticated models.
- Predictive model of foraging behavior using differential equations and the theory of random walks. The model allows prediction of swarm performance, scalability, and emergent self-organization without the need to run experiments.
Some visualizations from this research appear on Mr. Harwell’s webpage. He also presented a poster on this topic at the 2021 MSI Research Exhibition.
The computational complexity of the experiments from this research heavily leveraged the computational resources at MSI. Simulating over 8,000 robots in parallel with realistic physics in a reasonable amount of time requires cutting edge computational capabilities.
The UMII MnDRIVE Graduate Assistantship program supports UMN PhD candidates pursuing research at the intersection of informatics and any of the five MnDRIVE areas:
- Robotics, Sensors and Advanced Manufacturing
- Global Food Ventures
- Advancing Industry, Conserving Our Environment
- Discoveries and Treatments for Brain Conditions
- Cancer Clinical Trials
This project is part of the Robotics, Sensors and Advanced Manufacturing MnDRIVE area. An interview with Mr. Harwell is featured on the Department of Computer Science and Engineering website: CSpotlight: Swarming Towards Robotics.
Image description: Foraging task allocation. Left: Task allocation graph. Solid edges indicate task decomposition, dashed edges indicate task dependencies. Red and blue tasks correspond to a scheme in which robots can allocate a whole task or 1/2 task; red, blue, and green tasks correspond to a scheme in which robots can allocate a whole task, 1/2 task, or 1/4 task. Right: Foraging diagram showing the mapping of blue tasks from the left image into the physical world, where the cache acts as a task interface.
posted on January 18, 2022