Research: Optimized Swarm Robotics (Java Programming)

Optimized Swarm Robotics

Senior Design Project

Team

Mentor: Richard Lathrop, Professor

Project Manager: Mansi Tyagi, Computer Science & Engineering

Vision Manager: Andrew Sperry, Computer Science & Engineering

Hardware Manager: Nathan Le, Computer Engineering

Software Manager: Steven Chow, Computer Science & Engineering

Project

Name: MANS-i = for (String str : names) projName.append(str.charAt(0)); projName.append("-i");

Systems: MANS-i Maze Complexity Equation, MANS-i Maze Generator, MANS-i Swarm Simulator, MANS-i Data Analyzer

Introduction

Swarm robotics is defined as a field of multi-robotics, where a large number of robots work cohesively in a distributed and decentralized way to solve complex scenarios or tasks. Robots can vary in size, form, and ability, making robot swarms very effective at completing a variety of different tasks in many different fields. Project MANS-i is a virtual swarm robotics simulation system that focuses on optimizing a swarm's robot count to maximize the efficiency of solving mazes.

Project Goal

The goal of Project MANS-i is to formalize the relationship between a maze's given complexity and the optimal size of a robot swarm that can achieve the most efficient completion time. This optimal size would find a balance between under-saturated swarms (those with too few robots and suffer from task build-up) and oversaturated swarms (those with too many robots that frequently deadlock and collide with each other).

Potential Applications

Since Project MANS-i’s current focus is search applications, our technology can aid first-responders who use robot swarms to assist in the traversal of buildings or city-blocks. A phone application can convert the blueprint of a building or city-block into a maze and calculate the complexity of that maze. Then, based on the maze complexity and the input options selected within the application, such as a standardized traversal style, the start node, and various swarm task jobs needed, an optimal robot count is calculated. This optimal count can be used by the first responders to most efficiently execute their search, not only saving the lives of those who may need help, but also the lives of first responders and deployed military members.

Development Tools

MANS-i systems were developed in Java. Adobe Photoshop was used to design early stage graphical user interface (GUI) schematics. Java Window Builder was used to quickly develop the GUIs. Java Swing Worker was used to separate GUI and heavy logic to prevent GUI stalling. Java Concurrency Threads were used to run multiple swarm simulations in parallel to speed up average completion time stabilization over varied swarm counts.

MANS-i Maze Complexity Equation

The MANS-i Maze Complexity Equation uses generic maze attribtues to assign a complexity to a maze. N is the number of active nodes that can be reached. O, D, and L are the number of nodes on the optimal path, the number of dead-ends, and the number of loops respectively. The Summation sums up the number of paths at each intersection b_i.

If there are two node paths that leads back from the end node to a chokepoint intersection, than the equation must only count the longest path when calculating worst-case. This chokepoint intersection alters the equation, seperating it into two parts as shown below. C is the count of the longest path from the end node to the last intersection along the worst-case path.

MANS-i Maze Generator

The MANS-i Maze Generator takes in a maze title, a background grid size, and an active node count. After clicking "Generate Maze", the maze is made available in the selection list. The UI contains invalid input safe guards including selection sliders that automatically adjust their range of values when the other is adjusted. The generator pre-calculates maze values and complexity using the MANS-i Maze Complexity Equation above. Each maze is generated into its own maze file so that the maze files can be used in the MANS-i Swarm Simulator.

MANS-i Swarm Simulator

After generating maze files, the MANS-i Swarm Simulator displays the same list of maze files so that simulations can be run on them. When a maze is selected in the list, the UI rerfeshes and the Robot Count / Simulation Speed sliders become active. Pressing the Start / Resume button starts the simulation with the selected robot count. If 0 is selected, a random robot count is chosen. The simulation speed slider controls the speed of the simulation during run-time. Moving the slider to zero pauses the simulation. The simulation speed works off of a percentage that increments by 50% (0, 50%, 100%, ... 250%) with 100% being real-time speed. Pressing the finish button will instantly complete the current simulation and store the results into the maze file. The maze file results are displayed in the bottom left corner where each red bar is the average of all results for a specific robot count. For instant calculation of all mazes in the list, the "Complete All Maze Statistics" button will instantly loop through each Maze file, running simulations for each robot count until the average completion time stabilizes. The simulation will continue to increase the swarm size until the completion time minimizes and then steadily increases again. This can be seen below in the graph of stabilized averages for each robot count. To stabilize the average for each robot count, hundreds if not thousands of simulations need to be run for each robot count on each maze. To increase the speed of running so many simulations, multi-threading is used to run the simulations in parallel.

MANS-i Data Analysis

After stabilizing averages and finding the optimal robot count for hundreds of mazes, the optimal robot count for each maze was plotted against its given complexity. Linear regression was used to formulate a generalized line equation. In the future, we would like to produce more data and test the usefulness / accuracy of the equation in providing an optimal robot count given a specific complexity. Other future endevours would include testing robots that follow different maze running rules and even mixing these different types of robots into a hybrid swarm.