Ants on Deck helps autonomous boats find the way
Polaris Consulting, part of the TP Group,is developing Ants on Deck, a pioneering software system that automatically generates the optimal routes for autonomous surface vehicles based on the way ant colonies search for food. Berenice baker finds out how it could transform the way the Royal Navy uses autonomous vessels, saving fuel and avoiding collisions.
A prototype unmanned surface vessel developed for the UK MOD. Image: Crown Copyright / MOD
The definition of the ‘best’ route between any two locations for an autonomous surface vehicle (ASV) can involve any number of user-driven parameters, including covering the distance in the fastest time, achieving maximum fuel efficiency or minimising exposure to risk. The environmental factors that could affect these – wave height, weather, obstacles and enemy presence, for example – can change at any time necessitating a change of route.
In November 2018 the UK Ministry of Defence (MOD) awarded Polaris Consulting £1m to develop a demonstrator of its Ants on Deck solution to this challenge over two years. Like its namesake, it is a powerful partnership, not between two cheeky Geordies, but between a route-finding algorithm, user-driven parameters and response to environmental factors.
“Ants on Deck is an optimiser,” says Polaris Consulting head of technology and innovation John Shimell. “Autonomy has advanced fairly rapidly. Historically, it was more about finding a path from A to B. As it’s moved on, we’re not just interested in getting there, but getting there effectively using route optimisation. We’ve examined all the opportunities and this is the best.”
Ant colony optimisation: finding the best route inspired by nature
The quirky name – originally Polaris’ in-house shorthand to avoid the usual awkward acronym – is a combination of the type of route-finding algorithm at its heart, ant colony optimisation (ACO), and its initial intended maritime platform.
“ACO is a computational intelligence algorithm based in a stylised form of the way ants behave in a natural environment,” explains University of Exeter associate professor in computer science Professor Ed Keedwell.
It is modelled on the way ants are thought to search for and find the shortest path, for example, from the nest to a food source. When ants explore a landscape they drop pheromone so the shorter that path, the more pheromone remains. Other ants can sense that increase in the volume of pheromone on that trail and are more likely to take the same path. When many ants participate, it leads to what is known as an auto-catalytic process, where the shortest path naturally becomes more attractive and more ants take that particular route.
“If we have 10,000 ants explore the environment, we usually get 10,000 routes that work – every ant got to the goal in the end - so we’ve got 10,000 ways to get from A to B.”
“From an algorithmic point of view, it enables us to find paths,” Keedwell continues.
“The ants are agents within a system. They construct paths within a particular problem and they’re able to search out new paths but they’re also more likely to follow more promising areas of exploration previous ants have followed. “
In the case of Ants on Deck, the agents represent the ASV and multiple virtual iterations act like members of a colony.
“We make 1,000 or 10,000 or 100,000 agents and plop them down where the vessel is in a 3D environment that we’ve mapped, simulating the world, weather and waves and all that,” says Shimell. “Each ant individually doesn’t know about the other ants, and says what am I going to do for this step? Am I going to move forward or am I going to turn a bit? And it’s a very randomised choice they make within the constraints of what they’re capable of doing.”
The constraints include the speed the vessel is capable of and environmental factors that affect it, such as driving into a head-wind.
“If we have 10,000 ants explore the environment, we usually get 10,000 routes that work – every ant got to the goal in the end - so we’ve got 10,000 ways to get from A to B. Then we select the best of those by looking at the cost that particular ant incurred; the risk it took, how long it took to get there, how much fuel it used. Then we use those factors to judge what’s best,” explains Shimell.
Building a demonstrator with MOD funding
The work the MOD contracted Polaris to do through the funding will deliver a major pilot with an MOD stakeholder, in this case, Royal Navy Fleet Robotics Officer Sean Trevathan, and the Defence Equipment and Support (D&ES) mine countermeasures and hydrographic office.
“Our initial work is building up to a demonstration of autonomously leaving the harbour, transiting to a mission area that needs surveying to seek mines, doing the survey, and autonomously returning,” says Shimell. “We’re aiming for September 2020.”
The project works on a co-fund model, with the MOD providing £1m and Polaris having to co-fund the same amount through partnerships and internal funding. Thales is providing most of that and is partnering with Polaris to target Project Wilton, an upcoming acquisition project from D&ES to deliver an autonomous mine countermeasure capability.
“They call it peace-time marine survey,” explains Shimell. “It’s surveying the UK ports and harbours to ensure they’re safe for use, and they have to do that every year. Currently, it’s done with live, operational mine-hunting vessels, and they want to do that fully autonomously and release those operational vessels to go elsewhere.”
The future: dodging enemy fire and beyond
Importantly for more combative military applications, Ants on Deck could help dodge enemy fire or efficiently get a target within firing range.
“If you were trying to tackle an enemy craft, and you had a model of that enemy craft such that you could map out its arcs of fire, we could produce routes that minimise your exposure to them,” Shimell explains. “The counterpoint to that is that if you’re on a warship and you’ve got incoming craft, we could produce a route that maximises your arcs of fire, for example, to counter up-and-coming swarms.”
Polaris is already planning beyond the demonstration to develop future capabilities and applications. Ants on Deck could examine wave patterns to try and make a route less impactful and vibrating, which could be of value to the offshore energy industry, arguably be the biggest user of autonomy beyond defence. Planning a route to transport technicians to a wind farm that might be slightly longer but avoids the worst waves could mean they arrive less seasick.
“The ability of Ants on Deck to balance different factors is hugely extensible,” concludes Shimell.