Capturing an Unknown Moving Target in Unknown Territory using Vision and Coordination

Authors: Kiran Ijaz, Umar Manzoor, Arshad Ali Shahid

Abstract:

In this paper we present an extension to Vision Based LRTA* (VLRTA*) known as Vision Based Moving Target Search (VMTS) for capturing unknown moving target in unknown territory with randomly generated obstacles. Target position is unknown to the agents and they cannot predict its position using any probability method. Agents have omni directional vision but can see in one direction at some point in time. Agent-s vision will be blocked by the obstacles in the search space so agent can not see through the obstacles. Proposed algorithm is evaluated on large number of scenarios. Scenarios include grids of sizes from 10x10 to 100x100. Grids had obstacles randomly placed, occupying 0% to 50%, in increments of 10%, of the search space. Experiments used 2 to 9 agents for each randomly generated maze with same obstacle ratio. Observed results suggests that VMTS is effective in locate target time, solution quality and virtual target. In addition, VMTS becomes more efficient if the number of agents is increased with proportion to obstacle ratio.

Keywords: Vision, MTS, Unknown Target, Coordination, VMTS, Multi-Agent.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1329589

References:

[1] Umar Manzoor and Kiran Ijaz, "Using Vision and Coordination to find Unknown Target", 10th WSEAS CSCC Multiconference on Computers, Communications, Systems and Circuits, Vouliagmeni Beach, Athens, Greece, July 10-15, 2006.
[2] Chimura and M. Tokoro, The Trailblazer Search: "A New Method for Searching and Capturing Moving Targets", AAAI-94, pp. 1347-1352, 1994.
[3] T. Ishida and M. Shimbo, "Improving the Learning Efficiencies of Real- Time Search", AAAI-96, pp. 305-310, 1996.
[4] E. Korf, Real-Time Heuristic Search," Artificial Intelligence, Vol. 42, No. 2-3,pp. 189-211. 1990..
[5] Muaz Niazi, Umar Manzoor and Kiran Ijaz, "C3LRTA*, Color Code Coordinated LRTA* Algorithm", International Conference on Computational Intelligence, Man-Machine Systems and Cybernetics, Miami, USA, Nov. 2005.
[6] T. Ishida and R. E. Korf, "Moving Target Search", IJCAI-91, pp. 204- 210, 1991.
[7] T. Ishida, "Moving Target Search with Intelligence", AAAI-92, pp. 525- 532, 1992.
[8] M. Goldenberg, A. Kovarksy, X. Wu, and J. Schaeffer. Multiple agents moving target search. In Proceedings of the International Joint Conference on Artificial Intelligence, pages 1538--1538, 2003.
[9] Florin Leon, Mihai Horia Zaharia, Dan G├ólea, "A new Approach in Agent Path-Finding using State Mark Gradient" Computer Science Journal of Moldova, Chi┼ƒinâu, 2004.
[10] D'idac Busquets, Carles Sierra and Ramon Lo' pez Dema` ntaras. A multiagent Approach to qualitative Landmark-Based Navigation, Autonomous Robots 15, 129-154, 2003.
[11] M.Tan. Maulti-Agent Reinforcement Learning: Independent vs. Cooperative agents. In Proceeding of the 10th International Conference on Machine Learning, 330-337, 1993.
[12] Y. Kitamura, K. Teranishi and S. Tatsumi, Organizational Strategies for Multi-agent Real-Time Search," International Conference on Multi- Agent Systems (ICMAS-96), pp. 150-156, 1996.
[13] M. Yokoo and Y. Kitamura, Multiagent Real-Time A* with Selection: Introducing Competition in Cooperative Search," International Conference on Multi-Agent Systems (ICMAS-96), pp. 409-416, 1996.
[14] Armagan Cakir and Faruk Polat, "Coordination of Intelligent Agents in real-time Search" 2002.