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

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.

Authors:

• Kiran Ijaz
• Umar Manzoor
• Arshad Ali Shahid

Keywords:

• Vision
• MTS
• Unknown Target
• Coordination
• VMTS
• Multi-Agent.

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.