Parallelized egocentric fields for autonomous navigation
Tóm tắt
In this paper, we propose a general framework for local path-planning and steering that can be easily extended to perform high-level behaviors. Our framework is based on the concept of affordances: the possible ways an agent can interact with its environment. Each agent perceives the environment through a set of vector and scalar fields that are represented in the agent’s local space. This egocentric property allows us to efficiently compute a local space-time plan and has better parallel scalability than a global fields approach. We then use these perception fields to compute a fitness measure for every possible action, defined as an affordance field. The action that has the optimal value in the affordance field is the agent’s steering decision. We propose an extension to a linear space-time prediction model for dynamic collision avoidance and present our parallelization results on multicore systems. We analyze and evaluate our framework using a comprehensive suite of test cases provided in SteerBench and demonstrate autonomous virtual pedestrians that perform steering and path planning in unknown environments along with the emergence of high-level responses to never seen before situations.
Tài liệu tham khảo
Altun, K., Koku, A.: Evaluation of egocentric navigation methods. In: IEEE International Workshop on Robot and Human Interactive Communication (ROMAN 2005), pp. 396–401 (2005). doi:10.1109/ROMAN.2005.1513811
Arkin, R.: Motor schema based navigation for a mobile robot: An approach to programming by behavior. In: IEEE International Conference on Robotics and Automation. Proceedings, 1987, vol. 4, pp. 264–271 (1987). doi:10.1109/ROBOT.1987.1088037
Boulic, R.: Relaxed steering towards oriented region goals. In: Motion in Games, First International Workshop, pp. 176–187 (2008)
Chao, G., Dyer, M.: Concentric spatial maps for neural network based navigation. In: Ninth International Conference on Artificial Neural Networks (ICANN 99) (Conf. Publ. No. 470), vol. 1, pp. 144–149 (1999)
Chenney, S.: Flow tiles. In: Proceedings of the ACM SIGGRAPH/EG Symposium on Computer Animation (2004). doi:http://doi.acm.org/10.1145/1028523.1028553
Clements, R.R., Hughes, R.L.: Mathematical modelling of a medieval battle: the battle of Agincourt, 1415. Math. Comput. Simul. 64(2), 259–269 (2004)
Dechter, R., Pearl, J.: Generalized best-first search strategies and the optimality of a*. J. ACM 32(3), 505–536 (1985). doi:http://doi.acm.org/10.1145/3828.3830
Farenc, N., Schweiss, E., Kallmann, M., Aune, O., Boulic, R., Thalmann, D.: A paradigm for controlling virtual humans in urban environment simulations. Appl. Artif. Intell. 14, 69–91 (1999)
Fiorini, P., Shiller, Z.: Motion planning in dynamic environments using velocity obstacles. Int. J. Robot. Res. 17(7), 760–772 (1998). doi:10.1177/027836499801700706. URL http://ijr.sagepub.com/cgi/content/abstract/17/7/760
Fleming, P.: Implementing a robust 3 dimensional egocentric navigation system. Master’s thesis, Graduate School of Vanderbilt University (2005)
Gibson, J.J.: The theory of affordances. In: Perceiving, Acting, and Knowing (1977)
Goldenstein, S., Karavelas, M., Metaxas, D., Guibas, L., Aaron, E., Goswami, A.: Scalable nonlinear dynamical systems for agent steering and crowd simulation (2001)
Greeno, J.G.: Gibson’s affordances. Psychol. Rev. 336–342 (1994)
Hart, P., Nilsson, N., Raphael, B.: A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cybern. 4(2), 100–107 (1968). doi:10.1109/TSSC.1968.300136
Hart, P.E., Nilsson, N.J., Raphael, B.: Correction to “a formal basis for the heuristic determination of minimum cost paths”. SIGART Bull. 37, 28–29 (1972). doi:http://doi.acm.org/10.1145/1056777.1056779
Heck, R., Gleicher, M.: Parametric motion graphs. In: Proceedings of the 2007 Symposium on Interactive 3D Graphics and Games, I3D ’07, pp. 129–136. ACM, New York (2007). doi:http://doi.acm.org/10.1145/1230100.1230123
Helbing, D., Molnár, P.: Social force model for pedestrian dynamics. Phys. Rev. E 51(5), 4282–4286 (1995). doi:10.1103/PhysRevE.51.4282
Helbing, D., Buzna, L., Johansson, A., Werner, T.: Self-organized pedestrian crowd dynamics: Experiments, simulations, and design solutions. Transp. Sci. 39(1), 1–24 (2005). doi:10.1287/trsc.1040.0108
Hoogendoorn, S.P.: Pedestrian travel behavior modeling. In: 10th International Conference on Travel Behavior Research, Lucerne, pp. 507–535 (2003)
Kant, K., Zucker, S.W.: Planning collision-free trajectories in time-varying environments: a two-level hierarchy. Vis. Comput. 3(5), 304–313 (1988)
Kapadia, M., Singh, S., Hewlett, W., Faloutsos, P.: Egocentric affordance fields in pedestrian steering. In: Proceedings of the 2009 Symposium on Interactive 3D Graphics and Games, I3D ’09, pp. 215–223. ACM, New York (2009). doi:http://doi.acm.org/10.1145/1507149.1507185
Lamarche, F., Donikian, S.: Crowd of virtual humans: a new approach for real time navigation in complex and structured environments. In: Computer Graphics Forum, vol. 23 (2004)
Lee, K.H., Choi, M.G., Hong, Q., Lee, J.: Group behavior from video: a data-driven approach to crowd simulation. In: Proceedings of the ACM SIGGRAPH/EG Symposium on Computer Animation, pp. 109–118 (2007)
Lerner, A., Chrysanthou, Y., Lischinski, D.: Crowds by example. Comput. Graph. Forum 26(3), 655–664 (2007)
Li, T.Y., Chen, P.F., Huang, P.Z.: Motion planning for humanoid walking in a layered environment. In: Proceedings of IEEE ICRA, vol. 3, pp. 3421–3427 (2003). doi:10.1109/ROBOT.2003.1242119
Loscos, C., Marchal, D., Meyer, A.: Intuitive crowd behaviour in dense urban environments using local laws. In: TPCG ’03: Proceedings of the Theory and Practice of Computer Graphics 2003, p. 122. IEEE Comput. Soc., Washington (2003)
Lovas, G.: Modeling and simulation of pedestrian traffic flow. In: Transportation Research Record, pp. 429–443 (1994)
Michael, D., Chrysanthou, Y.: Automatic high level avatar guidance based on affordance of movement. In: Eurographics 2003. Eurographics Association, Geneva (2003)
Milazzo, J., Rouphail, N., Hummer, J., Allen, D.: The effect of pedestrians on the capacity of signalized intersections. In: Transportation Research Record, pp. 37–46 (1998)
Paris, S., Pettré, J., Donikian, S.: Pedestrian reactive navigation for crowd simulation: a predictive approach. In: EUROGRAPHICS 2007, vol. 26, pp. 665–674 (2007)
Paris, S., Gerdelan, A., O’Sullivan, C.: Ca-lod: Collision avoidance level of detail for scalable, controllable crowds. In: MIG ’09: Proceedings of the 2nd International Workshop on Motion in Games, pp. 13–28. Springer, Berlin (2009)
Park, S.I., Shin, H.J., Shin, S.Y.: On-line locomotion generation based on motion blending. In: Proceedings of the 2002 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, SCA ’02, pp. 105–111. ACM, New York (2002). doi:http://doi.acm.org/10.1145/545261.545279
Pelechano, N., Allbeck, J.M., Badler, N.I.: Controlling individual agents in high-density crowd simulation. In: Proceedings of the ACM SIGGRAPH/EG Symposium on Computer Animation, pp. 99–108 (2007)
Pelechano, N., Allbeck, J., Badler, N.: Virtual Crowds: Methods, Simulation, and Control. Synthesis Lectures on Computer Graphics and Animation. Morgan & Claypool Publishers, San Francisco (2008)
Quinn, M.J., Metoyer, R.A., Hunter-zaworski, K.: Parallel implementation of the social forces model. In: Proceedings of the Second International Conference in Pedestrian and Evacuation Dynamics, pp. 63–74 (2003)
Reynolds, C.W.: Flocks, herds and schools: A distributed behavioral model. In: Proceedings of ACM SIGGRAPH, pp. 25–34. ACM, New York (1987)
Reynolds, C.: Steering behaviors for autonomous characters. In: Game Developers Conference (1999)
Rodrigues, R.A., Lima Bicho, A., Paravisi, M., Jung, C.R., Magalhães, L.P., Musse, S.R.: Tree paths: A new model for steering behaviors. In: Proceedings of the 9th International Conference on Intelligent Virtual Agents, IVA ’09, pp. 358–371. Springer, Berlin (2009)
Rudomín, I., Millán, E., Hernández, B.: Fragment shaders for agent animation using finite state machines. Simul. Model. Pract. Theory 13(8), 741–751 (2005)
Shao, W., Terzopoulos, D.: Autonomous pedestrians. In: Proceedings of the ACM SIGGRAPH/EG Symposium on Computer Animation, pp. 19–28 (2005)
Shao, W., Terzopoulos, D.: Autonomous pedestrians. Graph. Models 69, 246–274 (2007). doi:10.1016/j.gmod.2007.09.001. URL http://portal.acm.org/citation.cfm?id=1323742.1323926
Shapiro, A., Kallmann, M., Faloutsos, P.: Interactive motion correction and object manipulation. In: I3D ’07: Proceedings of the 2007 Symposium on Interactive 3D Graphics and Games, pp. 137–144. ACM, New York (2007). doi:http://doi.acm.org/10.1145/1230100.1230124
Shimoda, S., Kuroda, Y., Iagnemma, K.: Potential field navigation of high speed unmanned ground vehicles on uneven terrain. In: Proceedings of the 2005 IEEE International Conference on Robotics and Automation (ICRA 2005), pp. 2828–2833 (2005)
Singh, S., Kapadia, M., Faloutsos, P., Reinman, G.: An open framework for developing, evaluating, and sharing steering algorithms. In: MIG ’09: Proceedings of the 2nd International Workshop on Motion in Games, pp. 158–169. Springer, Berlin (2009)
Singh, S., Kapadia, M., Faloutsos, P., Reinman, G.: Steerbench: a benchmark suite for evaluating steering behaviors. In: Computer Animation and Virtual Worlds, pp. 533–548 (2009)
Singh, S., Kapadia, M., Reinmann, G., Faloutsos, P.: On the interface between steering and animation for autonomous characters. In: Workshop on Crowd Simulation, Computer Animation and Social Agents, Saint-Malo, France (2010)
Singh, S., Kapadia, M., Hewlett, W., Reinmann, G., Faloutsos, P.: A modular framework for adaptive agent-based steering. In: Proceedings of the 2011 Symposium on Interactive 3D Graphics and Games, I3D ’11. ACM, New York (2011)
Sud, A., Gayle, R., Andersen, E., Guy, S., Lin, M., Manocha, D.: Real-time navigation of independent agents using adaptive roadmaps. In: VRST ’07: Proceedings of the 2007 ACM Symposium on Virtual Reality Software and Technology, pp. 99–106. ACM, New York (2007)
Surasmith, S.: Preprocessed solution for open terrain navigation. In: AI Game Programming Wisdom, pp. 161–170 (2002)
Takeuchi, R., Unuma, M., Amakawa, K.: Path planning and its application to human animation system. In: Creating and Animating the Virtual World, pp. 163–175. Springer, New York (1992). URL http://portal.acm.org/citation.cfm?id=141248.141259
Tecchia, F., Loscos, C., Conroy, R., Chrysanthou, Y.: Agent behaviour simulator (abs): A platform for urban behaviour development. In: GTEC’2001, pp. 17–21 (2001)
Thalmann, D., Musse, S.R.: Crowd Simulation. Springer, Berlin (2007)
Torrens, D.P.M.: Behavioral intelligence for geospatial agents in urban environments. In: IAT ’07: Proceedings of the 2007 IEEE/WIC/ACM International Conference on Intelligent Agent Technology, pp. 63–66. IEEE Comput. Soc., Washington (2007). doi:10.1109/IAT.2007.37
Treuille, A., Cooper, S., Popović, Z.: Continuum crowds. ACM Trans. Graph. 25(3), 1160–1168 (2006). doi:http://doi.acm.org/10.1145/1141911.1142008
Trovato, K.I., Dorst, L.: Differential a*. IEEE Trans. Knowl. Data Eng. 14(6), 1218–1229 (2002). doi:10.1109/TKDE.2002.1047763
Tsubouchi, T., Kuramochi, S., Arimoto, S.: Iterated forecast and planning algorithm to steer and drive a mobile robot in the presence of multiple moving objects. In: IROS ’95: Proceedings of the International Conference on Intelligent Robots and Systems, vol. 2, p. 2033. IEEE Comput. Soc., Washington (1995)
Turner, A., Penn, A.: Encoding natural movement as an agent-based system: an investigation into human pedestrian behaviour in the built environment. Environ. Plan. B, Plan. Des. 29, 473–490 (2002). http://eprints.ucl.ac.uk/73/
van den Berg, J., Lin, M.C., Manocha, D.: Reciprocal velocity obstacles for real-time multi-agent navigation. In: IEEE International Conference on Robotics and Automation, pp. 1928–1935. IEEE Press, New York (2008)
van den Berg, J., Patil, S., Sewall, J., Manocha, D., Lin, M.: Interactive navigation of multiple agents in crowded environments. In: SI3D ’08: Proceedings of the 2008 Symposium on Interactive 3D Graphics and Games, pp. 139–147. ACM, New York (2008)
Warren, C.: Global path planning using artificial potential fields. In: Proceedings of IEEE ICRA, vol. 1, pp. 316–321 (1989). doi:10.1109/ROBOT.1989.100007
Warren, C.: Multiple robot path coordination using artificial potential fields. In: Proceedings of IEEE ICRA, vol. 1, pp. 500–505 (1990). doi:10.1109/ROBOT.1990.126028