Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Optimal acceleration thresholds for non-holonomic agents

  • Original Article
  • Published:
The Visual Computer Aims and scope Submit manuscript

Abstract

Finding optimal trajectories for non-accelerating, non-holonomic agents is a well-understood problem. However, in video games, robotics, and crowd simulations non-holonomic agents start and stop frequently. With the vision of improving crowd simulation, we find optimal paths for virtual agents accelerating from a standstill. These paths are designed for the “ideal”, initial stage of planning when obstacles are ignored. We analytically derive paths and arrival times using arbitrary acceleration angle thresholds. We use these paths and arrival times to find an agent’s optimal ideal path. We then numerically calculate the decision surface that can be used by an application at run-time to quickly choose the optimal path. Finally, we use quantitative error analysis to validate the accuracy of our approach.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

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

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Arechavaleta, G., Laumond, J.P., Hicheur, H., Berthoz, A.: Optimizing principles underlying the shape of trajectories in goal oriented locomotion for humans. In: Humanoid Robots, 2006 6th IEEE-RAS International Conference on pp. 131–136 (2006)

  2. Arechavaleta, G., Laumond, J.P., Hicheur, H., Berthoz, A.: An optimality principle governing human walking. IEEE Trans. Robot. 24(1), 5–14 (2008)

    Article  Google Scholar 

  3. Van den Berg, J., Lin, M., Manocha, D.: Reciprocal velocity obstacles for real-time multi-agent navigation. In: Proceedings of Robotics and Automation pp. 1928–1935 (2008)

  4. Cockayne, E., Hall, G.: Plane motion of a particle subject to curvature constraints. SIAM J. Control 13(1), 197–220 (1975)

    MATH  MathSciNet  Google Scholar 

  5. Dubins, L.E.: On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents. Am. J. Math. 79(3), 497–516 (1957)

    MATH  MathSciNet  Google Scholar 

  6. Fiorini, P., Shiller, Z.: Motion planning in dynamic environments using velocity obstacles. Int. J. Robot. Research 17(7), 760 (1998)

    Article  Google Scholar 

  7. Harris, C.M., Wolpert, D.M.: Signal-dependent noise determines motor planning. Nature 394(6695), 780–784 (1998)

    Article  Google Scholar 

  8. Helbing, D., Molnar, P.: Social force model for pedestrian dynamics. Phys. Review 51(5), 4282–4286 (1995)

    Google Scholar 

  9. Hicheur, H., Pham, Q.C., Arechavaleta, G., Laumond, J.P., Berthoz, A.: The formation of trajectories during goal-oriented locomotion in humans. I. A stereotyped behaviour. Eur. J. Neurosci. 26(8), 2376–2390 (2007)

    Article  Google Scholar 

  10. Lacquaniti, F., Terzuolo, C., Viviani, P.: The law relating the kinematic and figural aspects of drawing movements. Acta Psychol. 54(1), 115–130 (1983)

    Google Scholar 

  11. Ondřej, J., Pettré, J., Olivier, A., Donikian, S.: A synthetic-vision based steering approach for crowd simulation. ACM Trans. Graph. (TOG) 29(4), 123:1–123:9 (2010)

  12. Reynolds, C.: Flocks, herds and schools: a distributed behavioral model. Proc. ACM SIGGRAPH Comput. Graph. 21(4), 25–34 (1987)

    Article  Google Scholar 

  13. Soueres, P., Laumond, J.P.: Shortest paths synthesis for a car-like robot. IEEE Trans. Autom. Control 41(5), 672–688 (1996)

    Article  MATH  MathSciNet  Google Scholar 

  14. Thalmann, D., Musse, S.R.: Crowd simulation. Wiley Online Library (2007)

  15. Todorov, E., Jordan, M.I.: Smoothness maximization along a predefined path accurately predicts the speed profiles of complex arm movements. J. Neurophysiol. 80(2), 696–714 (1998)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. CCICADA Center, Rutgers University, New Brunswick, USA

    Brian C. Ricks

  2. Brigham Young University, Provo, USA

    Parris K. Egbert

Authors
  1. Brian C. Ricks
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Parris K. Egbert
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Brian C. Ricks.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Ricks, B.C., Egbert, P.K. Optimal acceleration thresholds for non-holonomic agents. Vis Comput 30, 579–589 (2014). https://doi.org/10.1007/s00371-014-0972-z

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00371-014-0972-z

Keywords

Search

Navigation