آینده‌پژوهی دفاعی

آینده‌پژوهی دفاعی

کاربرد الگوریتم هندسه زبان‌شناختی در حل مسأله تعقیب و گریز بر روی گراف با اضافه نمودن شرایط واقعی محیط بازی جنگ

نوع مقاله : مقاله علمی- پژوهشی

نویسندگان
1 دانشجوی دکترای مهندسی صنایع دانشکده مهندسی صنایع دانشگاه آزاد اسلامی واحد تهران جنوب
2 استادیار دانشگاه پلی تکنیک کالیفرنیا در پومونا آمریکا
چکیده
امروزه تنوع و گستردگی مسائل در شاخه‌های گوناگون علوم تا حد بسیار زیادی افزایش یافته است و یافتن پاسخ برای چنین مسائلی در مدت زمان کم، چالشی بسیار اساسی محسوب می‌شود. استفاده از هوش مصنوعی می‌تواند فرآیند حل مسائل پیچیده را تا حد قابل قبولی سرعت بخشیده و زمان پاسخ‌دهی را به نحو محسوسی کاهش دهد. مسأله تعقیب و گریز از جمله مسائلی است که می‌تواند دارای سطح بالایی از پیچیدگی باشد. از جمله عوامل ایجاد پیچیدگی می‌توانیم به تعداد عوامل درگیر، برد میدان دید اعضاء و موانع موجود در زمین بازی اشاره کنیم. تاکنون الگوریتم‌های گوناگونی برای حل مسأله تعقیب و گریز ارائه شده که هر یک دارای نقاط ضعف و قوت خود هستند. در این مقاله با استفاده از الگوریتم هندسه زبان‌شناختی، به بررسی بازی تعقیب و گریز بطور خاص در یک مسأله با ابعاد زمین بازی 9×9 و برای بررسی تعمیم کارایی الگوریتم در مسائلی با ابعاد مختلف پرداخته شده است. نشان داده شده که این رهیافت می‌تواند بیش از 90% بهبود در سرعت پاسخ‌یابی ایجاد کند. در این مقاله عوامل مؤثر در واقع‌گرایی بازی تعقیب و گریز با دقت بیشتری در هندسه زبان‌شناختی بررسی می‌شوند و در نهایت با ساده‌سازی فضای مسأله به تعدادی زیر فضا که در آن گشت‌های حرکت هر عامل بازی مشخص است، اقدام به حل مسأله می‌کنیم. نشان می‌دهیم علی‌رغم پیچیده‌تر شدن فضای مسأله، الگوریتم هندسه زبان‌شناختی بهبودی در حدود 91% نسبت به سایر الگوریتم‌ها ایجاد می‌کند.
کلیدواژه‌ها

  • 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/