Optimal Path Planning Applied to Ant Foraging

University Degree Mathematical and Computer Sciences

Microsystems and Machine Vision Laboratory

Materials and Engineering Research Institute

Sheffield Hallam University,

Keywords: Robotics, artificial intelligence, path planning, ant foraging, swarm intelligence.

Introduction

The development of swarm technologies has become prevalent due to future applications in a variety of domains: medical, bioinformatics, military/defence, surveillance, even internet television broadcasting. Future space missions will exploit such technologies to enable spacecraft to be sent to places previously inaccessible, to ensure greater protection of space assets, and to increase the likelihood of mission success [1].

Social insect societies consist of individuals with simple behaviour, yet at the collective level the societies are capable of solving complex tasks. Although the capabilities of a single ant in an ant colony are limited, ants can collectively find the shortest path from the nest to the source of food. Ants are generally very efficient in finding food and building a nest just by using simple rules. Ants make use of pheromones, a chemical substance to mark a trail. They roam randomly until they pick up the scent of the pheromone, at which point of time they will decide to either follow the trail or continue to roam randomly. Using these techniques, ants are capable of finding the shortest possible path to the food source quickly. The results of self organisation are global in nature, but come about from interactions based entirely on local information [2]. To achieve this, self-organisation relies on several components: positive feedback, negative feedback, amplification of fluctuations, and multiple interactions [3].

In this paper we propose combining the pheromone approach with path finding techniques to increase performance of simple mobile robots. By introducing path-planning, the time required to locate the food sources can be reduced due to the removal of the random exploration stage of the standard ant foraging technique. This new technique can be used in a number of environments, e.g. in the case of assembling systems with parts located in multiple locations or in the case of equipment provision to workers in a dynamic industrial environment. In the latter situation, the workers will not have a fixed position, and ...

This is a preview of the whole essay

Background

Previous work in the area of ant foraging involved ants finding the food sources through the random exploration of the environment. This is followed-up by carrying small amounts of food back to the nest [1]. In the past, an approach using a single pheromone trail has been developed. In this situation the ants have to rely on some external means to transport the food back to the nest. Another approach is the double pheromone trail approach where the ants lay a nest-pheromone trail in addition to a food-pheromone trail. In this paper, in order to increase the efficiency of the agents (ants), we introduce path planning to decrease the time required for the initial exploration phase.

We have previously proposed an improved A* algorithm [4] for standard path planning and so we will adapt this technique to make it more suitable to an industrial environment where the location of the workers keep varying over time. In [5] the ants use the double pheromone approach and have 8 possible orientations: N, NE, E, SE, S, SW, W, NW. When deciding where to move, the ants first examine three nearby locations. If it does not find any pheromones in these locations, it would look into the other 5 locations. We shall simulate a similar approach using the Netlogo tool [6] and compare the performance of this with our hybridised approach.

Implementation

In this paper one ant is given the responsibility of finding an optimal path and depositing pheromones. Since the task of path finding is computationally intensive only one ant is entrusted with this task. The other ants roam randomly until they sense a pheromone trail. This ant keeps traversing to and fro between the food source and the home location depositing pheromones.

When it finds that the food location has changed it goes back to the home location where it gets the knowledge of the new food source location. The previous pheromone trail it had established evaporates with time. It finds the optimal path between the new food source and home location and then starts forming a double pheromone trail to guide the other ants. A comparison of the ant foraging without path planning as in [5] with ant foraging using path planning as in this paper is done through simulations in Netlogo.

The path finding ant lays food pheromones when travelling towards the food source and drops home pheromones when travelling towards the home location. An ant which comes across a pheromone when it is carrying food or is located in the food source follows the home pheromone to reach the home location. An ant which comes across a pheromone when it is not carrying a food source or is located in the home location follows the food pheromone to reach the food source.

Figure 1: Ants transporting food from food source to the nest in Netlogo [6].

In the case of applying the hybridised method to a real-world problem, consider the situation where systems that have to be assembled or built by a swarm of mobile agents. Components for the complete system may be located in a number of places.

The agents will first need to discover the location of these components and then bring it back to the “home” position for assembly. By introducing path-planning, the random exploration stage can be removed and the time required to locate the components can be reduced. Virtual pheromones can be implemented using simple message passing methods.

Conclusion

In this abstract we have discussed the introduction of a new hybridised approach to improving the performance of the ant foraging technique. In the full paper we shall describe the stages required for developing such a system. We shall also provide a comparative study of the ant foraging technique with and without path planning. This will better establish the performance of both approaches in a given arena. We will further discuss how such a system can be applied to solving real-world scenarios.

References

[1] M.G. Hinchey, C.A. Rouff, J.L. Rash, W.F. Truszkowski, “Requirements of an Integrated Formal Method for Intelligent Swarms”, Proceedings of the 10th International Workshop on Formal Methods for Industrial Critical Systems FMICS, Lisbon, pp. 125–133, September 2005.

[2] P. Tarasewich, P.R. McMullen, “Swarm intelligence: power in numbers”, Communications of the ACM, vol 45, no. 8, pp. 62-67, August 2002

[3] E. Bonabeau, M. Dorigo, and G. Theraulaz, “Swarm Intelligence: From Natural to Artificial Systems”, Oxford University Press, New York, 1999.

[4] A. Veeraswamy and B.P. Amavasai, “Optimal path planning using an improved A* algorithm for homeland security robots”, 24th IASTED International Multi-Conference on Artificial Intelligence and Applications, Innsbruck, pp. 50-55, February 2006.

[5] Liviu A. Panait and Sean Luke, “Ant Foraging revisited”, Ninth International Conference on the Simulation and Synthesis of Living Systems, Boston, pp. 569-574, September 2004.

[6] U. Wilensky, NetLogo, http://ccl.northwestern.edu/ netlogo/. Centre for Connected Learning and Computer-Based Modelling, Northwestern University. Evanston, IL, 1999.