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
 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.
 Chimura and M. Tokoro, The Trailblazer Search: "A New Method for
Searching and Capturing Moving Targets", AAAI-94, pp. 1347-1352,
 T. Ishida and M. Shimbo, "Improving the Learning Efficiencies of Real-
Time Search", AAAI-96, pp. 305-310, 1996.
 E. Korf, Real-Time Heuristic Search," Artificial Intelligence, Vol. 42,
No. 2-3,pp. 189-211. 1990..
 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.
 T. Ishida and R. E. Korf, "Moving Target Search", IJCAI-91, pp. 204-
 T. Ishida, "Moving Target Search with Intelligence", AAAI-92, pp. 525-
 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.
 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.
 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.
 M.Tan. Maulti-Agent Reinforcement Learning: Independent vs.
Cooperative agents. In Proceeding of the 10th International Conference
on Machine Learning, 330-337, 1993.
 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.
 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.
 Armagan Cakir and Faruk Polat, "Coordination of Intelligent Agents in
real-time Search" 2002.