Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Autonomous Robots
Published in: Autonomous Robots 6/2017

09-02-2017

Multipolicy decision-making for autonomous driving via changepoint-based behavior prediction: Theory and experiment

Authors: Enric Galceran, Alexander G. Cunningham, Ryan M. Eustice, Edwin Olson

Published in: Autonomous Robots | Issue 6/2017

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

This paper reports on an integrated inference and decision-making approach for autonomous driving that models vehicle behavior for both our vehicle and nearby vehicles as a discrete set of closed-loop policies. Each policy captures a distinct high-level behavior and intention, such as driving along a lane or turning at an intersection. We first employ Bayesian changepoint detection on the observed history of nearby cars to estimate the distribution over potential policies that each nearby car might be executing. We then sample policy assignments from these distributions to obtain high-likelihood actions for each participating vehicle, and perform closed-loop forward simulation to predict the outcome for each sampled policy assignment. After evaluating these predicted outcomes, we execute the policy with the maximum expected reward value. We validate behavioral prediction and decision-making using simulated and real-world experiments.
previous article Editor’s note: Special Issue on Robotics: Science and Systems, 2015
next article Guaranteeing spoof-resilient multi-robot networks

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now
Footnotes
1
In this paper, we use the term closed-loop policies to mean policies that react to the presence of other traffic participants, in a coupled manner. The same concept applies to the term closed-loop simulation.
 
Literature
Aoude, G. S., Luders, B. D., Joseph, J. M., Roy, N., & How, J. P. (2013). Probabilistically safe motion planning to avoid dynamic obstacles with uncertain motion patterns. Autonomous Robots, 35(1), 51–76.CrossRef
Bai, H., Hsu, D., & Lee, W. S. (2014). Integrated perception and planning in the continuous space: A POMDP approach. International Journal of Robotics Research, 33(9), 1288–1302.CrossRef
Bandyopadhyay, T., Jie, C. Z., Hsu, D., Ang, M. H., Rus, D., & Frazzoli, E. (2013a). In Experimental robotics: The 13th international symposium on experimental robotics (pp. 963–977). Springer International Publishing, chap Intention-Aware Pedestrian Avoidance.
Bandyopadhyay, T., Won, K., Frazzoli, E., Hsu, D., Lee, W., & Rus, D. (2013b). Intention-aware motion planning. In E. Frazzoli, T. Lozano-Perez, N. Roy, & D. Rus (Eds.), Proceedings of the international workshop on the algorithmic foundations of robotics, Springer tracts in advanced robotics (Vol. 86, pp. 475–491). Berlin: Springer.
Bishop, C. M. (2007). Pattern recognition and machine learning. Information science and statistics. Berlin: Springer.
Brechtel, S., Gindele, T., & Dillmann, R. (2011). Probabilistic MDP-behavior planning for cars. In Proceedings of the IEEE intelligent transportation systems conference (pp. 1537–1542).
Brechtel, S., Gindele, T., & Dillmann, R. (2014). Probabilistic decision-making under uncertainty for autonomous driving using continuous POMDPs. In Proceedings of the IEEE intelligent transportation systems conference (pp. 392–399).
Broadhurst, A., Baker, S., & Kanade, T. (2005). Monte carlo road safety reasoning. In Proceedings of the IEEE intelligent vehicles symposium (pp. 319–324). Las Vegas, NV: IEEE.
Candido, S., Davidson, J., & Hutchinson, S. (2010). Exploiting domain knowledge in planning for uncertain robot systems modeled as pomdps. In Proceedings of the IEEE international conference on robotics and automation (pp. 3596–3603). Anchorage, AK: IEEE.
Chandola, V., Banerjee, A., & Kumar, V. (2009). Anomaly detection: A survey. ACM Computing Surveys, 41(3), 15.CrossRef
Choi, J., Eoh, G., Kim, J., Yoon, Y., Park, J., & Lee, B. H. (2010). Analytic collision anticipation technology considering agents’ future behavior. In Proceedings of the IEEE/RSJ international conference on intelligent robots and systems (pp. 1656–1661). Taipei, Taiwan: IEEE.
Cunningham, A. G., Galceran, E., Eustice, R. M., & Olson, E. (2015). MPDM: Multipolicy decision-making in dynamic, uncertain environments for autonomous driving. In Proceedings of the IEEE international conference on robotics and automation, Seattle, WA.
Dagli, I., Brost, M., & Breuel, G. (2003). Agent technologies, infrastructures, tools, and applications for E-Services: NODe 2002 agent-related workshops. Springer Berlin Heidelberg, Chap Action Recognition and Prediction for Driver Assistance Systems Using Dynamic Belief Networks, pp. 179–194.
Du Toit, N., & Burdick, J. (2010). Robotic motion planning in dynamic, cluttered, uncertain environments. In Proceedings of the IEEE international conference on robotics and automation (pp. 966–973). Anchorage, AK: IEEE.
Du Toit, N. E., & Burdick, J. W. (2012). Robot motion planning in dynamic, uncertain environments. IEEE Transactions on Robotics, 28(1), 101–115.CrossRef
Fearnhead, P., & Liu, Z. (2007). On-line inference for multiple changepoint problems. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 69(4), 589–605.MathSciNetCrossRef
Ferguson, D., Darms, M., Urmson, C., & Kolski, S. (2008a). Detection, prediction, and avoidance of dynamic obstacles in urban environments. In Proceedings of the IEEE intelligent vehicles symposium (pp. 1149–1154). Eindhoven, Netherlands: IEEE.
Ferguson, D., Howard, T. M., & Likhachev, M. (2008b). Motion planning in urban environments. Journal of Field Robotics, 25(11–12), 939–960.CrossRef
Fulgenzi, C., Tay, C., Spalanzani, A., & Laugier, C. (2008). Probabilistic navigation in dynamic environment using rapidly-exploring random trees and gaussian processes. In Proceedings of the IEEE/RSJ international conference on intelligent robots and systems (pp. 1056–1062). Nice, France: IEEE.
Galceran, E., Cunningham, A.G., Eustice, R.M., & Olson, E. (2015a). Multipolicy decision-making for autonomous driving via changepoint-based behavior prediction. In Proceedings of the robotics: science & systems conference. Rome, Italy: Robotics: Science and Systems Foundation.
Galceran, E., Olson, E., & Eustice, R. M. (2015b). Augmented vehicle tracking under occlusions for decision-making in autonomous driving. In Proceedings of the IEEE/RSJ international conference on intelligent robots and systems (pp. 3559–3565). Hamburg, Germany: IEEE.
Gindele, T., Brechtel, S., & Dillmann, R. (2015). Learning driver behavior models from traffic observations for decision making and planning. IEEE Intelligent Transportation Systems Magazine, 7, 69–79.CrossRef
Hardy, J., & Campbell, M. (2013). Contingency planning over probabilistic obstacle predictions for autonomous road vehicles. IEEE Transactions on Robotics, 29(4), 913–929.CrossRef
Havlak, F., & Campbell, M. (2014). Discrete and continuous, probabilistic anticipation for autonomous robots in urban environments. IEEE Transactions on Robotics, 30(2), 461–474.CrossRef
He, R., Brunskill, E., & Roy, N. (2011). Efficient planning under uncertainty with macro-actions. Journal of Artificial Intelligence Research, 40, 523–570.MATH
Joseph, J., Doshi-Velez, F., Huang, A. S., & Roy, N. (2011). A Bayesian nonparametric approach to modeling motion patterns. Autonomous Robots, 31(4), 383–400.CrossRef
Kim, K., Lee, D., & Essa, I. (2011). Gaussian process regression flow for analysis of motion trajectories. In Proceedings of the IEEE international conference on computer vision (pp. 1164–1171). Barcelona, Spain: IEEE.
Kuderer, M., Gulati, S., & Burgard, W. (2015). Learning driving styles for autonomous vehicles from demonstration. In Proceedings of the IEEE international conference on robotics and automation (pp 2641–2646). Seattle, WA: IEEE.
Kurniawati, H., Hsu, D., & Lee, W. (2008). SARSOP: Efficient point-based POMDP planning by approximating optimally reachable belief spaces. In Proceedings of the robotics: Science & systems conference. Zurich, Switzerland: IEEE.
Lee, T., & Kim, Y. J. (2016). Massively parallel motion planning algorithms under uncertainty using POMDP. International Journal of Robotics Research, 35(8), 928–942.CrossRef
Madani, O., Hanks, S., & Condon, A. (2003). On the undecidability of probabilistic planning and related stochastic optimization problems. Artificial Intelligence, 147(1–2), 5–34.MathSciNetCrossRefMATH
Miller, I., et al. (2008). Team Cornell’s Skynet: Robust perception and planning in an urban environment. Journal of Field Robotics, 25(8), 493–527.CrossRef
Montemerlo, M., et al. (2008). Junior: The stanford entry in the urban challenge. Journal of Field Robotics, 25(9), 569–597.CrossRef
Niekum, S., Osentoski, S., Atkeson, C. G., & Barto, A. G. (2014). CHAMP: Changepoint detection using approximate model parameters. Tech. Rep. CMU-RI-TR-14-10, Robotics Institute, Carnegie Mellon University.
Niekum, S., Osentoski, S., Atkeson, C. G., & Barto, A. G. (2015). Online bayesian changepoint detection for articulated motion models. In Proceedings of the IEEE international conference on robotics and automation. Seattle, WA: IEEE.
Ohki, T., Nagatani, K., & Yoshida, K. (2010). Collision avoidance method for mobile robot considering motion and personal spaces of evacuees. In Proceedings of the IEEE/RSJ international conference on intelligent robots and systems (pp. 1819–1824). Taipei, Taiwan: IEEE.
Papadimitriou, C. H., & Tsitsiklis, J. N. (1987). The complexity of Markov decision processes. Mathematics of Operations Research, 12(3), 441–450.MathSciNetCrossRefMATH
Petti, S., & Fraichard, T. (2005). Safe motion planning in dynamic environments. In Proceedings of the IEEE/RSJ international conference on intelligent robots and systems (pp. 2210–2215). Edmonton, AB: IEEE.
Piciarelli, C., & Foresti, G. (2006). On-line trajectory clustering for anomalous events detection. Pattern Recognition Letters, 27(15), 1835–1842.CrossRef
Silver, D., & Veness, J. (2010). Monte-carlo planning in large POMDPs. In J. Lafferty, C. Williams, J. Shawe-Taylor, R. Zemel, & A. Culotta (Eds.), Advances in neural information processing systems 23 (pp. 2164–2172). Red Hook, NY: Curran Associates Inc.
Somani, A., Ye, N., Hsu, D., & Lee, W. S. (2013). DESPOT: Online POMDP planning with regularization. In C. Burges, L. Bottou, M. Welling, Z. Ghahramani, & K. Weinberger (Eds.), Advances in neural information processing systems 26 (pp. 1772–1780). Red Hook, NY: Curran Associates Inc.
Thrun, S. (2000). Monte Carlo POMDPs. In Proceedings of the advances in neural information processing systems Conference (pp 1064–1070).
Tran, Q., & Firl, J. (2013). Modelling of traffic situations at urban intersections with probabilistic non-parametric regression. In Proceedings of the IEEE intelligent vehicles symposium (pp. 334–339). Gold Coast City, Australia: IEEE.
Tran, Q., & Firl, J. (2014). Online maneuver recognition and multimodal trajectory prediction for intersection assistance using non-parametric regression. In Proceedings of the IEEE intelligent vehicles symposium (pp. 918–923). Dearborn, MI: IEEE.
Trautman, P., & Krause, A. (2010). Unfreezing the robot: Navigation in dense, interacting crowds. In Proceedings of the IEEE/RSJ international conference on intelligent robots and systems (pp. 797–803). Taipei, Taiwan: IEEE.
Ulbrich, S., & Maurer, M. (2013). Probabilistic online pomdp decision making for lane changes in fully automated driving. In Proceedings of the IEEE intelligent transportation systems conference (pp 2063–2067).
Urmson, C., Anhalt, J., Bagnell, D., Baker, C., Bittner, R., Clark, M. N., et al. (2008). Autonomous driving in urban environments: Boss and the urban challenge. Journal of Field Robotics, 25(8), 425–466.CrossRef
Wei, J., Dolan, J. M., Snider, J. M., & Litkouhi, B. (2011). A point-based MDP for robust single-lane autonomous driving behavior under uncertainties. In Proceedings of the IEEE international conference on robotics and automation (pp. 2586–2592). Shanghai, China: IEEE.
Werling, M., Ziegler, J., Kammel, S., & Thrun, S. (2010). Optimal trajectory generation for dynamic street scenarios in a frenet frame. In Proceedings of the IEEE international conference on robotics and automation (pp. 987–993). Anchorage, AK: IEEE.
Xu, W., Wei, J., Dolan, J., Zhao, H., & Zha, H. (2012). A real-time motion planner with trajectory optimization for autonomous vehicles. In Proceedings of the IEEE international conference on robotics and automation (pp. 2061–2067). Saint Paul, MN: IEEE.
Metadata
Title
Multipolicy decision-making for autonomous driving via changepoint-based behavior prediction: Theory and experiment
Authors
Enric Galceran
Alexander G. Cunningham
Ryan M. Eustice
Edwin Olson
Publication date
09-02-2017
Publisher
Springer US
Published in
Autonomous Robots / Issue 6/2017
Print ISSN: 0929-5593
Electronic ISSN: 1573-7527
DOI
https://doi.org/10.1007/s10514-017-9619-z

Other articles of this Issue 6/2017

Autonomous Robots 6/2017 Go to the issue

OriginalPaper

Distributed on-line dynamic task assignment for multi-robot patrolling

News

Editor’s note: Special Issue on Robotics: Science and Systems, 2015

OriginalPaper

Avoiding target congestion on the navigation of robotic swarms

OriginalPaper

Robust trajectory optimization under frictional contact with iterative learning

OriginalPaper

Orbital stabilization of an underactuated bipedal gait via nonlinear -control using measurement feedback

OriginalPaper

Guaranteeing spoof-resilient multi-robot networks