Abstract
We demonstrate the applicability of inverted Ant Algorithms (iAA) for target search in a complex unknown indoor environment with obstructed topology, simulated by a maze. The colony of autonomous ants lay repellent pheromones according to the novel local interaction policy designed to speed up exploration of the unknown maze instead of reinforcing presence in already visited areas. The role of a target-collocated beacon emitting a rescue signal within the maze is evaluated in terms of its utility to guide the search. Different models of iAA were developed, with beacon initialization (iAA-B), and with increased sensing ranges (iAA-R with a 2-step far-sightedness) to quantify the most effective one. Initial results with mazes of various sizes and complexity demonstrate our models are capable of localizing the target faster and more efficiently than other open searches reported in the literature, including those that utilized both AA and local path planning. The presented models can be implemented with self-organizing wireless sensor networks carried by autonomous drones or vehicles and can offer life-saving services of localizing victims of natural disasters or during major infrastructure failures.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Ahuja, M.: Fuzzy counter ant algorithm for maze problem. Master’s thesis. University of Cincinnati (2010)
Aljehani, M., Inoue, M.: Communication and autonomous control of multi-UAV system in disaster response tasks. In: Jezic, G., Kusek, M., Chen-Burger, Y.-H.J., Howlett, R.J., Jain, L.C. (eds.) KES-AMSTA 2017. SIST, vol. 74, pp. 123–132. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-59394-4_12
Andryeyev, O., Mitschele-Thiel, A.: Increasing the cellular network capacity using self-organized aerial base stations. In: Proceedings of the 3rd Workshop on Micro Aerial Vehicle Networks, Systems, and Applications, pp. 37–42. ACM (2017)
Aurangzeb, M., Lewis, F.L., Huber, M.: Efficient, swarm-based path finding in unknown graphs using Reinforcement Learning. In: 2013 10th IEEE International Conference on Control and Automation, ICCA, pp. 870–877. IEEE (2013)
Bounini, F., Gingras, D., Pollart, H., Gruyer, D.: Modified Artificial Potential Field method for online path planning applications. In: 2017 IEEE Intelligent Vehicles Symposium, IV, pp. 180–185. IEEE (2017)
Buniyamin, N., Ngah, W., Sariff, N., Mohamad, Z.: A simple local path planning algorithm for autonomous mobile robots. Int. J. Syst. Appl. Eng. Dev. 5(2), 151–159 (2011)
Cao, J.: Robot global path planning based on an Improved Ant Colony Algorithm. J. Comput. Commun. 4(02), 11 (2016)
Engelbrecht, A.P.: Fundamentals of Computational Swarm Intelligence. Wiley, Hoboken (2006)
Fossum, F., Montanier, J.M., Haddow, P.C.: Repellent pheromones for effective swarm robot search in unknown environments. In: 2014 IEEE Symposium on Swarm Intelligence, SIS, pp. 1–8. IEEE (2014)
Krentz, T., Greenhagen, C., Roggow, A., Desmond, D., Khorbotly, S.: A modified Ant Colony Optimization algorithm for implementation on multi-core robots. In: 2015 Swarm/Human Blended Intelligence Workshop, SHBI, pp. 1–6. IEEE (2015)
Lavalle, S.M.: Rapidly-exploring random trees: A new tool for path planning. TR 98–11. Computer Science Deparment, Iowa State University, October 1998
Li, Y., Cai, L.: UAV-assisted dynamic coverage in a heterogeneous cellular system. IEEE Netw. 31(4), 56–61 (2017)
Mac, T.T., Copot, C., Tran, D.T., De Keyser, R.: Heuristic approaches in robot path planning: a survey. Robot. Auton. Syst. 86, 13–28 (2016)
Mainetti, L., Patrono, L., Vilei, A.: Evolution of wireless sensor networks towards the Internet of Things: a survey. In: 2011 19th International Conference on Software, Telecommunications and Computer Networks, SoftCOM, pp. 1–6. IEEE (2011)
Mishra, S., Bande, P.: Maze solving algorithms for micro mouse. In: IEEE International Conference on Signal Image Technology and Internet Based Systems, SITIS 2008, pp. 86–93. IEEE (2008)
Wang, Z.W.: Robot path planning for mobile robot based on Improved Ant Colony Algorithm. Appl. Mech. Mater. 385–386
Rappaport, T.S., et al.: Wireless Communications: Principles and Practice, vol. 2. Prentice Hall PTR, Upper Saddle River (1996)
Ravankar, A., Ravankar, A.A., Kobayashi, Y., Emaru, T.: On a bio-inspired hybrid pheromone signalling for efficient map exploration of multiple mobile service robots. Artif. Life Robot. 21(2), 221–231 (2016)
Rivera, G.: Path planning for general mazes. Master’s thesis. Missouri University of Science and Technology (2012)
Sauter, J.A., Matthews, R., Parunak, H.V.D., Brueckner, S.A.: Performance of digital pheromones for swarming vehicle control. In: Proceedings of the Fourth International Joint Conference on Autonomous Agents and Multiagent Systems, pp. 903–910. ACM (2005)
Shiltagh, N.A., Jalal, L.D.: Optimal path planning for intelligent mobile robot navigation using modified Particle Swarm Optimization. Int. J. Eng. Adv. Technol. 2(4), 260–267 (2013)
Tjiharjadi, S., Setiawan, E.: Design and implementation of a path finding robot using Flood Fill algorithm. Int. J. Mech. Eng. Robot. Res. 5(3), 180–185 (2016)
Wang, H., Yu, Y., Yuan, Q.: Application of Dijkstra algorithm in robot path-planning. In: 2011 Second International Conference on Mechanic Automation and Control Engineering, MACE, pp. 1067–1069. IEEE (2011)
Wilson, R.: Propagation Losses Through Common Building Materials 2.4 GHz vs 5 GHz. Magis Networks Inc., San Diego (2002)
Yi, G., Feng-ting, Q., Fu-jia, S., Wei-ming, H., Peng-ju, Z.: Research on path planning for mobile robot based on ACO. In: 2017 29th Chinese Control and Decision Conference, CCDC, pp. 6738–6743. IEEE (2017)
Zanella, A., Bui, N., Castellani, A., Vangelista, L., Zorzi, M.: Internet of Things for smart cities. IEEE Internet Things J. 1(1), 22–32 (2014)
Acknowledgement
We gratefully acknowledge the support from UAE ICT Fund through the grant “Biologically Inspired Self-organizing Network Services” and Prof. Sami Muhaidat (KUST) for advices with the models of indoor signal propagation.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
1 Electronic supplementary material
Below is the link to the electronic supplementary material.
Rights and permissions
Copyright information
© 2018 Springer Nature Switzerland AG
About this paper
Cite this paper
Husain, Z., Ruta, D., Saffre, F., Al-Hammadi, Y., Isakovic, A.F. (2018). Search in a Maze-Like Environment with Ant Algorithms: Complexity, Size and Energy Study. In: Dorigo, M., Birattari, M., Blum, C., Christensen, A., Reina, A., Trianni, V. (eds) Swarm Intelligence. ANTS 2018. Lecture Notes in Computer Science(), vol 11172. Springer, Cham. https://doi.org/10.1007/978-3-030-00533-7_12
Download citation
DOI: https://doi.org/10.1007/978-3-030-00533-7_12
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-00532-0
Online ISBN: 978-3-030-00533-7
eBook Packages: Computer ScienceComputer Science (R0)