A newly minted Vanderbilt University computer science Ph.D. combined characteristics of ant colonies and superheated metals to break a decades-old coding problem.
Sayan Sen’s results have potential applications in a field that is grabbing the tech world’s attention: swarm robotics, or the idea that large numbers of robots can work together to complete tasks.
Sen’s work was under the guidance of Julie A. Adams, associate professor of computer science and computer engineering. Adams and her students are researching speedy and effective ways to create human-robot teams for dangerous tasks, such as responding to natural disasters or other mass-casualty events.
Two of Adams’ former students, Lovekesh Vig and Travis Service, created algorithms for use in that process, called coalition formation. Sen compiled those algorithms — plus others already written — and developed code that looks at the task to be performed and all the available algorithms. It selects the best ones to apply to the problem based on the constraints.
Another of Adams’ students, Electa Baker, is creating a system that allows those results to be used in assigning specific human workers and robots to the task.
The Haiti earthquake of 2010 provides a real-world example of where coalition formation could help, Adams said. The system can be used to create teams of humans and air, land and underwater robots to find victims, assess the structural integrity of buildings and triage patients. Longer term, it can aid in delivering supplies and in recovery efforts.
A significant portion of Sen’s research centered on an algorithm type called an ant colony optimization, which was developed in the early 1990s based on the way ants travel. That’s randomly – at first – to find food sources and return to the nest. Eventually, they use repeated application of pheromones to mark the fastest route.
The problem with the ant algorithm approach is that, during the search phase, it can stagnate in the local minima or local maxima — getting stuck in peaks and valleys of potential solutions and stalling out before finding the best ones available.
“Since the ants search probabilistically, you can become stuck in a narrow set of solutions,” Sen said. “Once you get stuck, you’re not able to get out of these local optimas. If you run one hour or 10 hours, you always get the same poor solutions.”
Sen used simulating annealing to overcome that problem. His code follows the pattern of metal molecules excited by heat, finding the broadest array of possible results, and then cooling down slowly, aligning until the best solutions are found. Abbreviated to sA-ANT, his code avoids those troubling peaks and valleys that keep the search for a solution from moving forward.
Sen submitted his paper to the journal Swarm Intelligence and is making revisions, Adams said.
“He’s demonstrated some phenomenal results,” she said.
The next step for Adams’ team is seeing whether or not the system works when it is decentralized from one computer and distributed among robots in the field. That’s vital, she said, because breaks in communication from a central computer can compromise missions.
Contact
Heidi Hall, (615) 322-6614
Heidi.Hall@Vanderbilt.edu
On Twitter @VUEngineering