Skip to main content
SpringerLink
Log in

Automated synthesis of action selection policies for unmanned vehicles operating in adverse environments

  • Published:
Autonomous Robots Aims and scope Submit manuscript

Abstract

We address the problem of automated action selection policy synthesis for unmanned vehicles operating in adverse environments. We introduce a new evolutionary computation-based approach using which an initial version of the policy is automatically generated and then gradually refined by detecting and fixing its shortcomings. The synthesis technique consists of the automated extraction of the vehicle’s exception states and Genetic Programming (GP) for automated composition and optimization of corrective sequences of commands in the form of macro-actions to be applied locally.

The focus is specifically on automated synthesis of a policy for Unmanned Surface Vehicle (USV) to efficiently block the advancement of an intruder boat toward a valuable target. This task requires the USV to utilize reactive planning complemented by short-term forward planning to generate specific maneuvers for blocking. The intruder is human-competitive and exhibits a deceptive behavior so that the USV cannot exploit regularity in its attacking behavior.

We compared the performance of a hand-coded blocking policy to the performance of a policy that was automatically synthesized. Our results show that the performance of the automatically generated policy exceeds the performance of the hand-coded policy and thus demonstrates the feasibility of the proposed approach.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Similar content being viewed by others

References

  • Anderson, D. (2004). Boinc: A system for public-resource computing and storage. In Proceedings of the 5th IEEE/ACM international workshop on grid computing (pp. 4–10). IEEE Computer Society: Los Alamitos.

    Chapter  Google Scholar 

  • Andre, D., Friedman, N., & Parr, R. (1998). Generalized prioritized sweeping. Advances in Neural Information Processing Systems, 1001–1007.

  • Bacardit, J., Bernadó-Mansilla, E., & Butz, M. (2008). Learning classifier systems: looking back and glimpsing ahead. Learning Classifier Systems, 1–21.

  • Baker, C., Ferguson, D., & Dolan, J. (2008). Robust Mission Execution for Autonomous Urban Driving. Intelligent Autonomous Systems, 10, 155.

    Google Scholar 

  • Barate, R., & Manzanera, A. (2007). Automatic design of vision-based obstacle avoidance controllers using genetic programming. In Proceedings of the evolution artificielle, 8th international conference on Artificial evolution (pp. 25–36). Berlin: Springer.

    Google Scholar 

  • Barlow, G., & Oh, C. (2008). Evolved navigation control for unmanned aerial vehicles. Frontiers in Evolutionary Robotics, 596–621.

  • Board, N. (2005). Autonomous vehicles in support of naval operations. Washington: National Research Council.

    Google Scholar 

  • Buason, G., Bergfeldt, N., & Ziemke, T. (2005). Brains, bodies, and beyond: Competitive co-evolution of robot controllers, morphologies and environments. Genetic Programming and Evolvable Machines, 6(1), 25–51.

    Article  Google Scholar 

  • Buhmann, M. (2001). Radial basis functions. Acta Numerica, 9, 1–38.

    MathSciNet  Google Scholar 

  • Corfield, S., & Young, J. (2006). Unmanned surface vehicles–game changing technology for naval operations. Advances in Unmanned Marine Vehicles, 311–328.

  • Cox, M., & Cox, T. (2008). Multidimensional scaling. Handbook of data visualization (pp. 315–347).

    Google Scholar 

  • Dain, R. (1998). Developing mobile robot wall-following algorithms using genetic programming. Applied Intelligence, 8(1), 33–41.

    Article  MathSciNet  Google Scholar 

  • Diederich, J., Tickle, A., & Geva, S. (2010). Quo vadis? Reliable and practical rule extraction from neural networks. Advances in Machine Learning, I, 479–490.

    Article  Google Scholar 

  • Doherty, D., & O’Riordan, C. (2006). Evolving agent-based team tactics for combative computer games. In AICS 2006 17th Irish artificial intelligence and cognitive science conference.

    Google Scholar 

  • Dupuis, J., & Parizeau, M. (2006). Evolving a vision-based line-following robot controller. In IEEE proceedings.

    Google Scholar 

  • Finn, A., & Scheding, S. (2010). Developments and challenges for autonomous unmanned vehicles: a compendium. Berlin: Springer.

    Book  Google Scholar 

  • Floreano, D., & Mattiussi, C. (2008). Bio-inspired artificial intelligence: theories, methods, and technologies.

    Google Scholar 

  • Gajda, P., & Krawiec, K. (2008). Evolving a vision-driven robot controller for real-world indoor navigation. In Proceedings of the 2008 conference on applications of evolutionary computing (pp. 184–193). Berlin: Springer.

    Google Scholar 

  • Gerkey, B., Thrun, S., & Gordon, G. (2006). Visibility-based pursuit-evasion with limited field of view. The International Journal of Robotics Research, 25(4), 299.

    Article  Google Scholar 

  • Goldberg, D. (1989). Genetic algorithms in search and optimization.

    MATH  Google Scholar 

  • Haynes, T., & Sen, S. (1996). Evolving behavioral strategies in predators and prey. Adaption and Learning in Multi-Agent Systems, 113–126.

  • Jaskowski, W., Krawiec, K., & Wieloch, B. (2008). Winning ant wars: Evolving a human-competitive game strategy using fitnessless selection. In Genetic programming: Proceedings of 11th European conference, EuroGP 2008 (p. 13). Naples, Italy, 26–28 March 2008. New York: Springer.

    Google Scholar 

  • Kohl, N., & Miikkulainen, R. (2008). Evolving neural networks for fractured domains. In Proceedings of the 10th annual conference on genetic and evolutionary computation (pp. 1405–1412). New York: ACM.

    Chapter  Google Scholar 

  • Koza, J. (2003). Genetic programming IV: Routine human-competitive machine intelligence. Dordrecht: Kluwer Academic.

    MATH  Google Scholar 

  • Koza, J., & Rice, J. (1992). Automatic programming of robots using genetic programming. In Proceedings of the national conference on artificial intelligence (p. 194).

    Google Scholar 

  • Lanzi, P. (2008). Learning classifier systems: then and now. Evolutionary Intelligence, 1(1), 63–82.

    Article  Google Scholar 

  • LaValle, S. (2009). Filtering and planning in information spaces (IROS tutorial notes).

  • Lipson, H. (2007). Principles of modularity, regularity, and hierarchy for scalable systems. Journal of Biological Physics and Chemistry, 7(4), 125.

    Article  Google Scholar 

  • Lipson, H., Antonsson, E., Koza, J., Bentley, P., & Michod, R. (2003). Computational synthesis: from basic building blocks to high level functionality. In Proc. assoc. adv. artif. intell. symp. (pp. 24–31).

    Google Scholar 

  • Nehmzow, U. (2002). Physically embedded genetic algorithm learning in multi-robot scenarios: The PEGA algorithm. In 2nd international workshop on epigenetic robotics: modelling cognitive development in robotic systems.

    Google Scholar 

  • Poli, R., Langdon, W., & McPhee, N. (2008). A field guide to genetic programming. Lulu Enterprises UK Ltd.

  • Richards, M., Whitley, D., Beveridge, J., Mytkowicz, T., Nguyen, D., & Rome, D. (2005). Evolving cooperative strategies for UAV teams. In Proceedings of the 2005 conference on genetic and evolutionary computation (p. 1728). New York: ACM.

    Google Scholar 

  • Sammut, C., & Webb, G. (2011). Encyclopedia of machine learning. New York: Springer.

    MATH  Google Scholar 

  • Schrum, J., & Miikkulainen, R. (2009). Evolving multi-modal behavior in NPCs. In Proceedings of the 5th international conference on computational intelligence and games (pp. 325–332). New York: IEEE Press.

    Google Scholar 

  • Schwartz, M., Svec, P., Thakur, A., & Gupta, S. K. (2009). Evaluation of automatically generated reactive planning logic for unmanned surface vehicles. In Performance metrics for intelligent systems workshop (PERMIS’09).

    Google Scholar 

  • Shichel, Y., Ziserman, E., & Sipper, M. (2005). GP-robocode: Using genetic programming to evolve robocode players. Genetic Programming, 143–154.

  • Sipper, M., Azaria, Y., Hauptman, A., & Shichel, Y. (2007). Designing an evolutionary strategizing machine for game playing and beyond. IEEE Transactions on Systems, Man and Cybernetics. Part C, Applications and Reviews, 37(4), 583–593.

    Article  Google Scholar 

  • Stanley, K., & Miikkulainen, R. (2002). Evolving neural networks through augmenting topologies. Evolutionary Computation, 10(2), 99–127.

    Article  Google Scholar 

  • Sutton, R., & Barto, A. (1998). Reinforcement learning: an introduction. Adaptive computation and machine learning. Cambridge: MIT Press.

    Google Scholar 

  • Svec, P., Schwartz, M., Thakur, A., Anand, D. K., & Gupta, S. K. (2010). A simulation based framework for discovering planning logic for Unmanned Surface Vehicles. In ASME engineering systems design and analysis conference, Istanbul, Turkey.

    Google Scholar 

  • Thakur, A., & Gupta, S. (2011). Real-time dynamics simulation of unmanned sea surface vehicle for virtual environments. Journal of Computing and Information Science in Engineering, 11, 031005.

    Article  Google Scholar 

  • Theocharous, G., & Kaelbling, L. (2004). Approximate planning in pomdps with macro-actions. Advances in Neural Information Processing Systems, 16.

  • Togelius, J., Burrow, P., & Lucas, S. (2007). Multi-population competitive co-evolution of car racing controllers. In IEEE congress on evolutionary computation, CEC 2007 (pp. 4043–4050). New York: IEEE.

    Chapter  Google Scholar 

  • Urbanowicz, R., & Moore, J. (2009). Learning classifier systems: a complete introduction, review, and roadmap. Journal of Artificial Evolution and Applications, 2009, 1.

    Article  Google Scholar 

  • van Hoorn, N., Togelius, J., & Schmidhuber, J. (2009). Hierarchical controller learning in a first-person shooter. In IEEE symposium on computational intelligence and games (CIG 2009) (pp. 294–301).

    Chapter  Google Scholar 

  • Whiteson, S. (2010). Adaptive representations for reinforcement learning (Vol. 291). Berlin: Springer.

    Book  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Simulation Based System Design Laboratory, Department of Mechanical Engineering, University of Maryland, College Park, MD, 20742, USA

    Petr Svec

  2. Simulation Based System Design Laboratory, Maryland Robotics Center, Department of Mechanical Engineering and Institute for Systems Research, University of Maryland, College Park, MD, 20742, USA

    Satyandra K. Gupta

Authors
  1. Petr Svec
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Satyandra K. Gupta
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Petr Svec.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Svec, P., Gupta, S.K. Automated synthesis of action selection policies for unmanned vehicles operating in adverse environments. Auton Robot 32, 149–164 (2012). https://doi.org/10.1007/s10514-011-9268-6

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10514-011-9268-6

Keywords

Search

Navigation