Skip to main content
SpringerLink
Log in

Hybrid System Models of Navigation Strategies for Games and Animations

  • Conference paper
  • First Online:
Hybrid Systems: Computation and Control (HSCC 2002)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 2289))

Included in the following conference series:

Abstract

The virtual worlds of computer games and similar animated simulations may be populated by autonomous characters that intelligently navigate in virtual cities. We concretely apply hybrid system theory and tools to model navigation strategies for virtual characters. In particular, we present hybrid systems for both low-level (local) and high-level (global) navigation strategies, and we describe how we modeled these systems using the hybrid system specification tool Charon. Further, we directly employed our hybrid system models to generate animations that demonstrate these navigation strategies. Overall, our results suggest that hybrid systems may be a natural framework for modeling aspects of intelligent virtual actors. We also present a small verification example for a simple navigation strategy, and we briefly discuss obstacles to widespread practical applicability of verification in this problem domain.

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

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. E. Aaron, F. Ivančić, and S. Goldenstein. Supplementary material, demonstrations, and CHARON-generated animations. Available at http://www.cis.upenn.edu/~eaaron/hscc02supplement.html.

  2. E. Aaron and D. Metaxas. Considering hierarchical hybrid systems for intelligent animated agents. In Proceedings of the First Workshop on Radical Agent Concepts. Springer Verlag, 2002.

    Google Scholar 

  3. E. Aaron, D. Metaxas, F. Ivančić, and O. Sokolsky. A framework for reasoning about animation systems. In Proceedings of the Third International Workshop on Intelligent Virtual Agents, volume 2190 of Lecture Notes in Artificial Intelligence, pages 47–60. Springer Verlag, 2001.

    Google Scholar 

  4. R. Alur, R. Grosu, Y. Hur, V. Kumar, and I. Lee. Modular specification of hybrid systems in CHARON. In N. Lynch and B. H. Krogh, editors, Hybrid Systems: Computation and Control, volume 1790of Lecture Notes in Computer Science. Springer Verlag, 2000.

    Chapter  Google Scholar 

  5. R. Alur, R. Grosu, I. Lee, and O. Sokolsky. Compositional refinement for hierarchical hybrid systems. In Hybrid Systems: Computation and Control, volume 2034 of Lecture Notes in Computer Science, pages 33–48. Springer Verlag, 2001.

    Chapter  Google Scholar 

  6. R. Alur, T. Henzinger, G. Lafferriere, and G. Pappas. Discrete abstractions of hybrid systems. Proceedings of the IEEE, 88:971–984, July 2000.

    Google Scholar 

  7. R. C. Arkin. Integrating behavioral, perceptual, and world knowledge in reactive navigation. Robotics and Autonomous Systems, 6:105–122, 1990.

    Article  Google Scholar 

  8. D. Brogan, R. Metoyer, and J. Hodgins. Dynamically simulated characters in virtual environments. IEEE Computer Graphics and Applications, 18(5):59–69, Sep/Oct 1998.

    Article  Google Scholar 

  9. Rodney A. Brooks. A robust layered control system for a mobile robot. IEEE Journal of Robotics and Automation, RA-2(1):14–23, 1986.

    Google Scholar 

  10. P. Cousot and R. Cousot. Static analysis of embedded software: Problems and perspectives, invited paper. In T.A. Henzinger and C.M. Kirsch, editors, Proc. First Int. Workshop on Embedded Software, EMSOFT 2001, volume 2211 of Lecture Notes in Computer Science, pages 97–113. Springer Verlag, 2001.

    Google Scholar 

  11. T. Dang and O. Maler. Reachability analysis via face lifting. In T. Henzinger and S. Sastry, editors, Hybrid Systems: Computation and Control, volume 1386 of Lecture Notes in Computer Science, pages 96–109. Springer Verlag, Berlin, 1998.

    Google Scholar 

  12. S. Das, D. L. Dill, and S. Park. Experience with predicate abstraction. In Computer Aided Verification, volume 1633 of Lecture Notes in Computer Science, pages 160–171. Springer Verlag, 1999.

    Chapter  Google Scholar 

  13. A. Deshpande, A. Göllu, and L. Semenzato. Shift programming language and run-time systems for dynamic networks of hybrid automata. Technical report, University of California at Berkeley, 1997.

    Google Scholar 

  14. J. Funge. AI for Games and Animation. A K Peters, 1999.

    Google Scholar 

  15. S. Goldenstein, M. Karavelas, D. Metaxas, L. Guibas, E. Aaron, and A. Goswami. Scalable nonlinear dynamical systems for agent steering and crowd simulation. Computers And Graphics, 25(6):983–998, 2001.

    Article  Google Scholar 

  16. S. Graf and H. Saidi. Construction of abstract state graphs with PVS. In O. Grumberg, editor, Proc. 9th International Conference on Computer Aided Verification (CAV’97), volume 1254, pages 72–83. Springer Verlag, 1997.

    Google Scholar 

  17. T.A. Henzinger and P.-H. Ho. A note on abstract-interpretation strategies for hybrid automata. In P. Antsaklis, A. Nerode, W. Kohn, and S. Sastry, editors, Hybrid Systems II, Lecture Notes in Computer Science 999, pages 252–264. Springer-Verlag, 1995.

    Google Scholar 

  18. T.A. Henzinger, P.-H. Ho, and H. Wong-Toi. A user guide to hytech. In E. Brinksma, W.R. Cleaveland, K.G. Larsen, T. Margaria, and B. Steffen, editors, TACAS 95: Tools and Algorithms for the Construction and Analysis of Systems, Lecture Notes in Computer Science 1019, pages 41–71. Springer-Verlag, 1995.

    Google Scholar 

  19. T.A. Henzinger, P.W. Kopke, A. Puri, and P. Varaiya. What’s decidable about hybrid automata? Journal of Computer and System Sciences, 57:94–124, 1998.

    Article  MATH  MathSciNet  Google Scholar 

  20. E. Large, H. Christensen, and R. Bajcsy. Scaling the dynamic approach to path planning and control: Competition among behavioral constraints. International Journal of Robotics Research, 18(1):37–58, 1999.

    Google Scholar 

  21. J.C. Latombe. Robot Motion Planning. Kluwer Academic Publishers, 1991.

    Google Scholar 

  22. H. Levesque and F. Pirri, editors. Logical Foundations for Cognitive Agents: Contributions in Honor of Ray Reiter. Springer, 1999.

    Google Scholar 

  23. M. J. Matarić. Integration of representation into goal-driven behaviour based robots. IEEE Trans on Robotics & Automation, June 1992, 8(3):304–312, 1992.

    Article  Google Scholar 

  24. G. J. Pappas and S. Sastry. Towards continuous abstractions of dynamical and control systems. In P. Antsaklis, W. Kohn, A. Nerode, and S. Sastry, editors, Hybrid Systems IV, volume 1273 of Lecture Notes in Computer Science, pages 329–341. Springer Verlag, Berlin, Germany, 1997.

    Chapter  Google Scholar 

  25. X. Tu and D. Terzopoulos. Artificial fishes: Physics, locomotion, perception, behavior. In Proc. of SIGGRAPH’ 94, pages 43–50, 1994.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer and Information Science, University Of Pennsylvania, 200 South 33rd Street, 19104-6389, Philadelphia, PA, USA

    Eric Aaron, Franjo Ivančić & Dimitris Metaxas

Authors
  1. Eric Aaron
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Franjo Ivančić
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Dimitris Metaxas
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Aeronautics and Astronautics, Stanford University, 250 Durand Building MC4035, 94305-4035, Stanford, CA, USA

    Claire J. Tomlin

  2. Department of Computer Science, University of British Columbia, 201-2366 Main Mall, V6T1Z4, Vancouver BC, Canada

    Mark R. Greenstreet

Rights and permissions

Reprints and permissions

Copyright information

© 2002 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Aaron, E., Ivančić, F., Metaxas, D. (2002). Hybrid System Models of Navigation Strategies for Games and Animations. In: Tomlin, C.J., Greenstreet, M.R. (eds) Hybrid Systems: Computation and Control. HSCC 2002. Lecture Notes in Computer Science, vol 2289. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45873-5_4

Download citation

  • DOI: https://doi.org/10.1007/3-540-45873-5_4

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-43321-7

  • Online ISBN: 978-3-540-45873-9

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation