Defensive Future Studies

Defensive Future Studies

Application of linguistic geometry Algorithm in solving Pursuit-evasion problem on graph by adding real conditions of war game environment

Document Type : Original Article

Authors
Ahmad Allahyari 1
Ellips Masehian 2
1 PhD student in Industrial Engineering, Faculty of Industrial Engineering, Islamic Azad University, South Tehran Branch
2 Assistant professor at the Industrial and Manufacturing Engineering Department at California State Polytechnic University, Pomona.
10.22034/dfsr.2020.125375.1384
Abstract
Nowadays, the diversity and expansions of problems in various branches of science has greatly increased and finding the answer to such problems in a short period of time is considered as a very essential challenge. Using artificial intelligence can significantly accelerate the solving process for complex problems and considerably reduce the response time. The pursuit-evasion problem is one of the problems that can have a high level of complexity due to the nature of the factors involved. Factors causing complexity include the number of factors involved, the range of member’s vision and barriers exist on the playground. Various algorithms have been proposed to solve the pursuit-evasion problem so far, each has its own strengths and weaknesses. In this paper, the pursuit-evasion game is examined by using the linguistic geometry algorithm specifically in a problem with 9×9 playground dimensions and to examine the generalization of the algorithm's performance in problems with different dimensions. It has been shown that this approach can improve the response speed by more than 90%. In this work, the factors affecting the realism of the pursuit-evasion game are examined more carefully in linguistic geometry and finally the problem is solved by simplifying the problem space to a number of subspaces in which the movement paths of each element of the game are clear. We show that, despite the problem space became more complex, the linguistic geometry algorithm creates about 91% improvement over the other algorithms.
Keywords
Pursuit-evasion problem
Linguistic geometry
Cop and robber problem
Search algorithm
Alpha-Beta pruning
  • Aigner, M. &. (1984). A game of cops and robbers. Discrete Mathematics, 8(1), 1-12.
  • Allis, L. V. (1994). Proof Number search. Artificial Intelligence, 66(1), 91-124.
  • Alspach, B. (2004). Searching and sweeping graphs: a brief survey. Le Matematiche, 59(1-2), 5-37.
  • Bal, D, Bonato. A, Kinnersley. W. B, Pralat. P. (2015). Lazy Cops and Robbers on hypercubes. Cambridge University Press.
  • Bhattacharya, G. P. (2010). A cops and robber game in multidimensional grid. Discrete Mathematics.
  • Bonato, P. G. (2009). The Capture time of a graph. Discrete Mathematics.
  • Bonato, P. G. (2009). The capture of time graph. Discrete mathematics, 5588-5595.
  • Chung, T. (2011). Search and pursuit-evasion in mobile robotics. Robots, 299-316.
  • Deo, C. R., & Ali, M. (2020). Modeling wheat yield with data-intelligent algorithms: artificial neural network versus genetic programming and minimax probability machine regression. In Hnadbook of Probbabillistic Models (pp. 37-87). Butterworth-Heinmann.
  • Fomin, F. V. (2008). An annotated bibliography on guaranteed graph searching. Theoritical Computer Scienece, 399(3), 236-245.
  • GAMMETER, S. (2013). LINGUISTIC GEOMETRY (LG) AND ITS APPLICATION TO HISTORICAL CONFLICTS. mathesis, University of Colorado at Denver, University of Colorado at Denver.
  • Gerkey, B. T. (2006). Visibility based pursuit with limited field of view. International Journal of Robotics Research, 25(4), 20-27.
  • Hahn, G. (2007). Cops, robbers and graphs. Tatra Mt. Math. Paul, 163-176.
  • Isaacs, R. (1965). Differential Games, A mathematical theory with applications warfare and pursuit. New York: Wiley.
  • Lucci, S., & Kopec, D. (2016). ArtificiAl Intelligence in the 21st Century A Living Introduction (2 ed.). Dulles: Mercury learning And information.
  • Maddahi, A. (2012). Solving pursuit and evasion problem in multi-agent systems through a linguistics geometry approach. mathesis.
  • Maddahi, A., & Masehian, E. (2017). Linguistic Geometry approach for solving cops and robber problem in grid environments. Information Sciences.
  • Moldenhauer, C. (2009). Game tree search algorithms for the game of Cops and Robber. University of Alberta: School of Computing Science.
  • Stuart. R, Norvig. P. (2009) Artificial Intelligence: A Modern Approach. Prentice Hall.
  • Sabin, P. (2014). Simulating War: Studying Cnflict through Simulation Games. Bloomsbury.
  • Stilman, B. (1994). Translations of network languages. Int. J. Computers and Mathematics with Applications, 27(2), 65-98.
  • Stilman, B. (1995). Linguistc geometry: methodology and techniques. Cybernetics and Systems, an International Journal, 26(5), 535-597.
  • Stilman, B. (1997). Managing search complexity in linguistic geometry. IEEE Transactions and Systems, 27(6), 978-998.
  • Stilman, B. (2000). Linguistic Geometry: From Search to Construction. Springer.
  • Stilman, B. (2010). Linguistics Geometry Tools with Demo DVD, LG-PACKAGE.
  • Stilman, B. (2010). Linguistic geometry: The age of maturity. Journal of Advanced Computational Intelligence Informatics, 14(6), 684-699.
  • Stilman, B., Yakhnis, V., & Umansky, O. (2010). Discovering Role of Linguistic Geometry. Berlin, Heidelberg: Springer.
  • Suzuki, I. &. (1992). Searching for a mobile intruder in a polygonal region. SIAM Journal on Computing, 21(5), 863-888.
  • Vieira, M. A. (2009). Scalable and practical pursuit and evasion robots. Intelligent Service Robotics, 2(4), 247-263.
  • Washburn, A., & Kress, M. (2009). Combat Modeling-International Series in Operations Research & Management Science. Springer.
  • Winkler, R. N. (1983). Vertext to vertex pursuit in a graph. Discrete Mathematics.
  • Yakhnis, V., & Stilman, B. (2002). Knowledge acquisition and strategy generation with LG wargaming tools. International journal of computational intelligence and applications, 2(4), 385-410.

(2020, Jun 11). Retrieved from https://www.RAND.com/