Logo PTI
Polish Information Processing Society
Logo FedCSIS

Annals of Computer Science and Information Systems, Volume 8

Proceedings of the 2016 Federated Conference on Computer Science and Information Systems

Employing Game Theory and Computational Intelligence to Find the Optimal Strategy of an Autonomous Underwater Vehicle against a Submarine

, ,

DOI: http://dx.doi.org/10.15439/2016F53

Citation: Proceedings of the 2016 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 8, pages 31–40 ()

Full text

Abstract. Game theory is a tool that may be used to model a player as an intelligent being - one who seeks to optimize his own performance while taking into account the performance of his opponent. However, it is often challenging to apply the theory in practice. In the naval environment, this approach may be used, for instance, to find the best strategy for an Autonomous Underwater Vehicle (AUV) while considering the intelligence of the submarine opponent. Classic approaches based on Minimax suffer from an explosion of states, and they are difficult to use in real-time. The paper introduces an approach that improves the Minimax algorithm in a complex naval environment. It assumes limited and scalable computational resources. The approach takes advantage of a flexible utility function based on a neural network with parameters tuned by a genetic algorithm.

References

  1. P. Kachroo, Autonomous Underwater Vehicles: Modeling, Control Design and Simulation. CRC Press, 2010. ISBN 978-1-4398-1831-2
  2. G. Griffiths, Ed., Technology and Applications of Autonomous Underwater Vehicles. CRC Press, 2002. ISBN 978-0-415-30154-1
  3. Wikipedia. Blackghost photo. http://en.wikipedia.org/wiki/Autonomous_underwater_vehicle
  4. T. Basar and G. Olsder, Dynamic Noncooperative Game Theory, 2nd ed. Society for Industrial and Applied Mathematics, 1999. ISBN 978- 0898714296
  5. S. Haykin, Neural Networks: A Comprehensive Foundation, 2nd ed. Prentice Hall PTR, 1998. ISBN 0-13-273350-1
  6. D. E. Goldberg, The Design of Innovation: Lessons from and for Competent Genetic Algorithms. Norwell, MA, USA: Kluwer Academic Publishers, 2002. ISBN 1402070985
  7. D. Wagner, W. Mylander, and T. Sanders, Naval Operations Analysis. Naval Institute Press, 1999. ISBN 1-557-50956-5
  8. C. Harrison, “Closed form bistatic reverberation and target echoes with variable bathymetry and sound speed,” Oceanic Engineering, IEEE Journal of, vol. 30, no. 4, pp. 660–675, Oct 2005. http://dx.doi.org/10.1109/JOE.2005.862095
  9. A. Sehgal and D. Cernea, “A multi-auv missions simulation framework for the usarsim robotics simulator,” in Control Automation (MED), 2010 18th Mediterranean Conference on, June 2010. http://dx.doi.org/10.1109/MED.2010.5547632 pp. 1188–1193.
  10. A. Washburn and R. Hohzaki, “The diesel submarine flaming datum problem,” Military Operations Research, vol. 6, no. 4, pp. 19–30, September 2001. http://dx.doi.org/10.5711/morj.6.4.19
  11. C. Strode, “Optimising multistatic sensor locations using path planning and game theory,” in Computational Intelligence for Security and Defense Applications (CISDA), 2011 IEEE Symposium on, April 2011. http://dx.doi.org/10.1109/CISDA.2011.5945938 pp. 9–16.
  12. C. Strode, B. Mourre, and M. Rixen, “Decision support using the Multistatic Tactical Planning Aid (MSTPA),” Ocean Dynamics, vol. 62, no. 1, pp. 161–175, 2012. http://dx.doi.org/10.1007/s10236-011-0483-7
  13. J. Borges de Sousa, K. H. Johansson, A. Speranzon, and J. Silva, “A control architecture for multiple submarines in coordinated search missions,” in Proceedings of the 16th IFAC world congress. IFAC, 2005. doi: 10.1.1.65.3030
  14. A. Antoniades, H. Kim, and S. Sastry, “Pursuit-evasion strategies for teams of multiple agents with incomplete information,” in Decision and Control, 2003. Proceedings. 42nd IEEE Conference on, vol. 1, Dec 2003. http://dx.doi.org/10.1109/CDC.2003.1272656. ISSN 0191-2216 pp. 756–761.
  15. T. H. Chung, G. A. Hollinger, and V. Isler, “Search and pursuit- evasion in mobile robotics,” Auton. Robots, vol. 31, no. 4, pp. 299–316, Nov. 2011. http://dx.doi.org/10.1007/s10514-011-9241-4
  16. R. Vidal, O. Shakernia, H. Kim, D. Shim, and S. Sastry, “Probabilistic pursuit-evasion games: theory, implementation, and experimental evaluation,” Robotics and Automation, IEEE Transactions on, vol. 18, no. 5, pp. 662–669, Oct 2002. http://dx.doi.org/10.1109/TRA.2002.804040
  17. K.-B. Sim, D.-W. Lee, and J.-Y. Kim, “Game theory based coevolutionary algorithm: A new computational coevolutionary approach,” International Journal of Control, Automation, and Systems, vol. 2, pp. 463–474, 2004. doi: 10.1.1.132.3826
  18. H. Sally and M. Rafie, “A survey of game theory using evolutionary algorithms,” in Information Technology (ITSim), 2010 International Symposium in, vol. 3, June 2010. http://dx.doi.org/10.1109/ITSIM.2010.5561648. ISSN 2155-897 pp. 1319–1325.
  19. S. Kemna, M. J. Hamilton, D. T. Hughes, and K. LePage, “Adaptive autonomous underwater vehicles for littoral surveillance: the GLINT10 field trial results,” Intelligent Service Robotics, vol. 4, no. 4, pp. 245–258, 2011. http://dx.doi.org/10.1007/s11370-011-0097-4
  20. R. Isaacs, Differential Games: A Mathematical Theory with Applications to Warfare and Pursuit, Control and Optimization. Courier Dover Publications, 1999. ISBN 0-486-40682-2
  21. J. Pearl, “The solution for the branching factor of the Alpha-beta pruning algorithm and its optimality,” Commun. ACM, vol. 25, no. 8, pp. 559–564, Aug. 1982. http://dx.doi.org/10.1145/358589.358616.
  22. K. Chellapilla and D. Fogel, “Evolution, neural networks, games, and intelligence,” Proceedings of the IEEE, vol. 87, no. 9, pp. 1471–1496, Sep 1999. http://dx.doi.org/10.1109/5.784222
  23. E. Alba and J. M. Troya, “A survey of parallel distributed genetic algorithms,” Complexity, vol. 4, no. 4, pp. 31–52, 1999. http://dx.doi.org/10.1002/(SICI)1099-0526(199903/04)4:4<31::AID-CPLX5>3.0.CO;2-4
  24. J. Sanders. (2010) Introduction to CUDA C. GPU Technology Conference, NVIDIA. [Online]. Available: http://www.nvidia.com/content/GTC-2010/pdfs/2131_GTC2010.pdf
  25. S. Rennich. (2011) CUDA C/C++ streams and concurrency. NVIDIA. [Online]. Available: http://on-demand.gputechconf.com/gtc-express/2011/presentations/StreamsAndConcurrencyWebinar.pdf
  26. H. Baier and M. H. M. Winands, “Monte-carlo tree search and minimax hybrids,” in Computational Intelligence in Games (CIG), 2013 IEEE Conference on, Aug 2013. http://dx.doi.org/10.1109/CIG.2013.6633630. ISSN 2325-4270 pp. 1–8.
  27. J. Schmidhuber, “Deep learning in neural networks: An overview,” Neural Networks, vol. 61, pp. 85–117, 2015. http://dx.doi.org/10.1016/j.neunet.2014.09.003