Artificial Intelligence and Swarm intelligence
BMT is in charge of creating intelligence for the fish. This will involve both an intelligence for each individual fish and the development of a swarm AI. The fish will have to be able to manage multiple problems; avoiding obstacles, knowing where to monitor pollution, finding the source of a pollution, maintaining communication distance from the other fish, recharging themselves at the charging station and many more. Each individual robotic fish will have an array of sensors and external information that will allow it to navigate the environment
Current research into swarm robotics concentrates on emergent behaviour developing from biologically inspired algorithms. These can be based on movement and behaviour of insects, flocks of birds, shoals of fish or other groups. These techniques concentrate on using local information and simple rules to establish a complex group behaviour as a whole in order to achieve predetermined goals. Two examples of swarm intelligence algorithms will be utilized in SHOAL.
Particle Swarm Optimisation (PSO) has been used in a range of fields since its inception and has been adapted for a range of uses. The algorithms have been tested in a wide variety of applications. In particular an evolution of this algorithm, DPSO (Discrete Particle Swarm Optimisation) has been applied to NP-hard problems such as the Capacitated Vehicle Routing Problem in a hybrid form using simulated annealing in order to overcome being trapped in local optima. An adapted form of this algorithm will be used for the basic search algorithm of the robotic swarm in SHOAL. An additional consideration will be made for the propagation of information within the swarm. Building on research which has shown that propagation of information throughout a swarm may function more effectively in decision making than simply local information, we will ensure that communication is possible between any robot and its neighbours. The swarm will work to prevent isolated groups so that information can be distributed to the whole swarm at any one time allowing all robots to take advantage of information on global optima. This will also serve to prevent any of the robots becoming “lost” by moving out of the range of their communications devices.
One of the problems to be overcome in SHOAL is that the swarm must adapt quickly to a rapidly changing environment. This is analogous to the problem that foraging ants must overcome when searching for food near their nest. For this reason ant colony optimisation techniques will be incorporated into the solution for these swarming robots. Ant Colony Optimisation (ACO) has been applied to a number of fields since its inception. In particular it has found repeated use in two major fields: combinatorial problems (particularly NP-hard problems) and swarm robotics. One major reason for the popularity of this approach in robotics is that it is an algorithm that automatically adapts to changes in the environment. This makes it ideal for exploratory robotics such as searching for pollution and in fact it has been used in robot navigation problems on many occasions.
SHOAL will use swarm intelligence techniques in order to control each robot, individually acting on information available locally and communicated between neighbouring robots. In particular the algorithms which will be used will be a combination of particle swarm optimisation, ant colony optimisation and flocking algorithms. These algorithms will be used to build a decision making mechanism for the robots. They will use information available locally and combine this through underwater communications with the information available to other robots in the swarm. The PSO and ACO algorithms will then be applied to this information (stored locally in each robot in the form of a 3D map overlaid with additional information which will drive the algorithms) in order to determine the optimal course of action for each individual robot. The parameters involved in these algorithms will be tested using the simulation software to be developed by BMT. Once the algorithms have been tested and tuned, the software will be integrated into each robot allowing them to act autonomously on the information available to them.
The maps which the Fish use will be 3D vector maps of the port. These will be initialised using electronic charts of the port which provide depth and feature information. The fish will augment these maps with the location and concentrations of chemicals detected. Pheromone maps will be built on top of these maps and will be set to decay over time. The maps will also be used for obstacle avoidance including in the same reference frame the paths of vessels supplied by an Automatic Identification System (AIS). AI is a system used by ships and Vessel Traffic Services (VTS) principally for identification and locating vessels. AIS provides a means for ships to electronically exchange ship data including: identification, position, course, and speed, with other nearby ships and VTS stations
SHOAL will use a hybrid search algorithm in order to determine the optimal way to find areas of contamination in a port. A recent paper shows how combining the two aforementioned approaches can be successfully applied to the field of swarm robotics. This study demonstrated “the robustness, scalability, and individual simplicity of the proposed control architecture in a swarm robot system with real-world constraints”. SHOAL will build upon the advances made in this study, further focusing on how virtual pheromone trails used in this method could be affected in real-time by shifting currents. The aim of this is to develop a more robust method of simulating pheromone trails so that reinforcement can still occur in spite of the fact that the underlying target of the trail (i.e. the pollution) will be dispersed and shifted by the water conditions in the port. SHOAL will also investigate how best to combine PSO and ACO algorithms with flocking behaviour in order to optimise the time taken to accurately develop a pollution map of a port and how best to maintain this map over time following the initial sampling period where the layout of pollution is determined.
Swarm intelligence relies on the assumption that small entities working together produce an intelligent behaviour from simple rules. In our case the robot fish will become aware of the presence and extent of pollution. They will do this through algorithms we develop based on ACO and PSO algorithms and Pheromone maps. Pollution is in its nature transient, dispersing over time. As our fish will use algorithms based on ACO, the pollution becomes analogous to food sought by foraging ants and our system will adapt in the same way the ants do firstly directing other fish to the location of the pollution (food) and later resuming foraging behaviour when the pollution has dispersed.