The DOI matches its Crossref record; 32 of the 32 references it cites were found in a registry or an index.
Motion planning under uncertainty using iterative local optimization in belief space
Abstract
We present a new approach to motion planning under sensing and motion uncertainty by computing a locally optimal solution to a continuous partially observable Markov decision process (POMDP). Our approach represents beliefs (the distributions of the robot’s state estimate) by Gaussian distributions and is applicable to robot systems with non-linear dynamics and observation models. The method follows the general POMDP solution framework in which we approximate the belief dynamics using an extended Kalman filter and represent the value function by a quadratic function that is valid in the vicinity of a nominal trajectory through belief space. Using a belief space variant of iterative LQG (iLQG), our approach iterates with second-order convergence towards a linear control policy over the belief space that is locally optimal with respect to a user-defined cost function. Unlike previous work, our approach does not assume maximum-likelihood observations, does not assume fixed estimator or control gains, takes into account obstacles in the environment, and does not require discretization of the state and action spaces. The running time of the algorithm is polynomial (O[n 6]) in the dimension n of the state space. We demonstrate the potential of our approach in simulation for holonomic and non-holonomic robots maneuvering through environments with obstacles with noisy and partial sensing and with non-linear dynamics and observation models.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Bellman, R. E. (2010) · doi:10.1515/9781400835386 · Cited by 14,588
(1995) · Cited by 10,558
Thrun, S. (2002) · Communications of the ACM · doi:10.1145/504729.504754 · Cited by 7,994
Unscented Filtering and Nonlinear Estimation
Julier, S. J., & Uhlmann, J. K. (2004) · Proceedings of the IEEE · doi:10.1109/jproc.2003.823141 · Cited by 6,588
Planning and acting in partially observable stochastic domains
Kaelbling, L. P., Littman, M. L., & Cassandra, A. R. (1998) · Artificial Intelligence · doi:10.1016/s0004-3702(98)00023-x · Cited by 4,149
Randomized Kinodynamic Planning
LaValle, S. M., & Kuffner, J. J. (2001) · The International Journal of Robotics Research · doi:10.1177/02783640122067453 · Cited by 3,254
Advances in neural information processing systems 11
Peter Sollich, A. (1999) · Cited by 3,168
Practical Methods for Optimal Control using Nonlinear Programming
Betts, & Kolmanovsky (2002) · Applied Mechanics Reviews · doi:10.1115/1.1483351 · Cited by 1,443
The Complexity of Markov Decision Processes
Papadimitriou, C. H., & Tsitsiklis, J. N. (1987) · Mathematics of Operations Research · doi:10.1287/moor.12.3.441 · Cited by 1,329 · cited 3×
“Solutions to POMDPs are known to be extremely complex (Papadimitriou and Tsisiklis, 1987), since the belief 1264 The International Journal of Robotics Research 31(11) space (over which a control policy is to be computed) is in the most general formulation, an infinite-dimensional space of all…”
InfluentialSARSOP: Efficient Point-Based POMDP Planning by Approximating Optimally Reachable Belief Spaces
Kurniawati, H., Hsu, D., & Sun Lee, W. (2008) · Robotics: Science and Systems IV · doi:10.15607/rss.2008.iv.009 · Cited by 759
Todorov, E., & Li, W. (2005) · Proceedings of the 2005, American Control Conference, 2005. · doi:10.1109/acc.2005.1469949 · Cited by 611
Differential dynamic programming
Denham, W. (1971) · IEEE Transactions on Automatic Control · doi:10.1109/tac.1971.1099760 · Cited by 530
Differential dynamic programming
Jacobson, D. H., & Mayne, D. Q. (1970) · CERN Document Server (European Organization for Nuclear Research) · Cited by 521
Rapidly-exploring Random Belief Trees for motion planning under uncertainty
Bry, A., & Roy, N. (2011) · 2011 IEEE International Conference on Robotics and Automation · doi:10.1109/icra.2011.5980508 · Cited by 439
LQG-MP: Optimized path planning for robots with motion uncertainty and imperfect state information
van den Berg, J., Abbeel, P., & Goldberg, K. (2011) · The International Journal of Robotics Research · doi:10.1177/0278364911406562 · Cited by 395
Self-citationThrun, S. (1999) · neural information processing systems · Cited by 303
Belief space planning assuming maximum likelihood observations
Platt, R., Tedrake, R., Kaelbling, L., & Lozano-Perez, T. (2010) · Robotics: Science and Systems VI · doi:10.15607/rss.2010.vi.037 · Cited by 298
Reciprocal collision avoidance with acceleration-velocity obstacles
van den Berg, J., Snape, J., Guy, S. J., & Manocha, D. (2011) · 2011 IEEE International Conference on Robotics and Automation · doi:10.1109/icra.2011.5980408 · Cited by 288
Self-citationThe Belief Roadmap: Efficient Planning in Belief Space by Factoring the Covariance
Prentice, S., & Roy, N. (2009) · The International Journal of Robotics Research · doi:10.1177/0278364909341659 · Cited by 269
Planning under Uncertainty for Robotic Tasks with Mixed Observability
Ong, S. C. W., Png, S. W., Hsu, D., & Lee, W. S. (2010) · The International Journal of Robotics Research · doi:10.1177/0278364910369861 · Cited by 238
Point-Based Value Iteration for Continuous POMDPs
Porta, J. M., Vlassis, N. A., Spaan, M. T. J., & Poupart, P. (2006) · DIGITAL.CSIC (Spanish National Research Council (CSIC)) · doi:10.13039/501100000780 · Cited by 234
Li, W., & Todorov, E. (2007) · International Journal of Control · doi:10.1080/00207170701364913 · Cited by 178
Monte Carlo Value Iteration for Continuous-State POMDPs
Bai, H., Hsu, D., Lee, W. S., & Vien, N. A. (2010) · Springer tracts in advanced robotics · doi:10.1007/978-3-642-17452-0_11 · Cited by 125
Parametric POMDPs for planning in continuous state spaces
Brooks, A., Makarenko, A., Williams, S. B., & Durrant-Whyte, H. F. (2006) · Robotics and Autonomous Systems · doi:10.1016/j.robot.2006.05.007 · Cited by 102
Robotic motion planning in dynamic, cluttered, uncertain environments
DUTOIT, N. E., & Burdick, J. W. (2010) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.2010.5509278 · Cited by 96
Closed-loop belief space planning for linear, Gaussian systems
Vitus, M. P., & Tomlin, C. J. (2011) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/icra.2011.5980257 · Cited by 65
Motion Planning Under Uncertainty Using Differential Dynamic Programming in Belief Space
van den Berg, J., Patil, S., & Alterovitz, R. (2016) · Springer tracts in advanced robotics · doi:10.1007/978-3-319-29363-9_27 · Cited by 65
Self-citationA Scalable Method for Solving High-Dimensional Continuous POMDPs Using Local ApproximationPreprint
Erez, T., & Smart, W. D. (2010) · arXiv (Cornell University) · doi:10.7936/k7mw2fbd · Cited by 54
Minimum uncertainty robot navigation using information-guided POMDP planning
Candido, S., & Hutchinson, S. (2011) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/icra.2011.5979695 · Cited by 48
Randomized Belief-Space Replanning in Partially-Observable Continuous Spaces
Hauser, K. K. (2010) · Springer tracts in advanced robotics · doi:10.1007/978-3-642-17452-0_12 · Cited by 46
Efficient Approximate Value Iteration for Continuous Gaussian POMDPs
van den Berg, J., Patil, S., & Alterovitz, R. (2021) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v26i1.8371 · Cited by 41
Self-citationicLQG: Combining local and global optimization for control in information space
Huynh, V. A., & Roy, N. (2009) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.2009.5152607 · Cited by 28
Research works printed but not linked: 7
- Erez T, 2010, 26th conference on uncertainty in artificial intelligence (UAI 2010), 160
- 10.1109/9.86943 · doi:10.1109/9.86943
- Porta J, 2006, Journal of Machine Learning Research, 7, 2329
- van den Berg J, 2011, 15th international symposium on robotics research (ISRR 2011)
- van den Berg J, 2012, 26th AAAI conference on artificial intelligence
- 10.1007/978-3-0348-7539-4_10 · doi:10.1007/978-3-0348-7539-4_10
- 10.1016/B978-0-12-012731-3.50008-1 · doi:10.1016/b978-0-12-012731-3.50008-1
Cited by
Past, Present, and Future of Simultaneous Localization and Mapping: Toward the Robust-Perception Age
Cadena, C., Carlone, L., Carrillo, H., Latif, Y., Scaramuzza, D., Neira, J., Reid, I., & Leonard, J. J. (2016) · IEEE Transactions on Robotics · doi:10.1109/tro.2016.2624754 · Cited by 3,596
“The online system of Flint et al. [95] presents a model that leverages the Manhattan world assumption to segment the map in the main planes in indoor scenes.”
Past, present, and future of simultaneous localization and mapping: Toward the robust-perception age
Cadena, C., Carlone, L., Carrillo, H., Latif, Y., Scaramuzza, D., Neira, J., Reid, I. D., & Leonard, J. J. (2016) · Zurich Open Repository and Archive (University of Zurich) · doi:10.5167/uzh-138892 · Cited by 3,048
Funnel libraries for real-time robust feedback motion planning
Majumdar, A., & Tedrake, R. (2017) · The International Journal of Robotics Research · doi:10.1177/0278364917712421 · Cited by 350
Sampling-based robotic information gathering algorithms
Hollinger, G. A., & Sukhatme, G. S. (2014) · The International Journal of Robotics Research · doi:10.1177/0278364914533443 · Cited by 334
A Survey on Active Simultaneous Localization and Mapping: State of the Art and New Frontiers
Placed, J. A., Strader, J., Carrillo, H., Atanasov, N., Indelman, V., Carlone, L., & Castellanos, J. A. (2023) · IEEE Transactions on Robotics · doi:10.1109/tro.2023.3248510 · Cited by 332
Metadata
- Authors
- van den Berg, J., Patil, S., & Alterovitz, R.
- Venue
- The International Journal of Robotics Research
- Publisher
- SAGE Publications
- Published
- 2012-09
- Volume
- 31
- Issue
- 11
- Pages
- 1263-1278
- ISSN
- 0278-3649 (ISSN-L)
- 1741-3176
- OpenAlex
- W2164429173
- Cited by
- 299
- References
- 32
- FWCI
- 16.72
- Type
- journal article
- Language
- en
- Open access
- closed
- Licence
- journals.sagepub.com/page/policies/text-and-data-mining-license (tdm)
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.