The DOI matches its Crossref record; 26 of the 26 references it cites were found in a registry or an index.
The Belief Roadmap: Efficient Planning in Belief Space by Factoring the Covariance
Open accessAbstract
When a mobile agent does not know its position perfectly, incorporating the predicted uncertainty of future position estimates into the planning process can lead to substantially better motion performance. However, planning in the space of probabilistic position estimates, or belief space, can incur a substantial computational cost. In this paper, we show that planning in belief space can be performed efficiently for linear Gaussian systems by using a factored form of the covariance matrix. This factored form allows several prediction and measurement steps to be combined into a single linear transfer function, leading to very efficient posterior belief prediction during planning. We give a belief-space variant of the probabilistic roadmap algorithm called the belief roadmap (BRM) and show that the BRM can compute plans substantially faster than conventional belief space planning. We conclude with performance results for an agent using ultra-wide bandwidth radio beacons to localize and show that we can efficiently generate plans that avoid failures due to loss of accurate position estimation.
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
A New Approach to Linear Filtering and Prediction Problems
Kalman, R. E. (1960) · Journal of Basic Engineering · doi:10.1115/1.3662552 · Cited by 31,751
Probabilistic roadmaps for path planning in high-dimensional configuration spaces
Kavraki, L. E., Svestka, P., Latombe, J.-C., & Overmars, M. H. (1996) · IEEE Transactions on Robotics and Automation · doi:10.1109/70.508439 · Cited by 6,343 · cited 4×
“In contrast, the motion planning community has realized considerable success in using stochastic search to find path s through high-dimensional configuration spaces with algorithms such as the Probabilistic Roadmap (PRM) (Kavraki et al., 1996) or Rapidly-Exploring Randomized Trees (RRT) (LaValle and Kuffner, 2001).”
BackgroundMethodInfluentialPlanning 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
2009 International Joint Conference on Artificial Intelligence
(2009) · doi:10.1109/jcai15434.2009 · Cited by 2,800
Proceedings of the 2004 American Control Conference
(2004) · Proceedings of the 2004 American Control Conference · doi:10.23919/acc.2004.1383555 · Cited by 2,605
Win, M. Z., & Scholtz, R. A. (1998) · IEEE Communications Letters · doi:10.1109/4234.660796 · Cited by 2,201
Spatial Planning: A Configuration Space Approach
Lozano-Perez (1983) · IEEE Transactions on Computers · doi:10.1109/tc.1983.1676196 · Cited by 2,113
A new approach for filtering nonlinear systems
Julier, S. J., Uhlmann, J. K., & Durrant-Whyte, H. F. (2005) · Proceedings of 1995 American Control Conference - ACC'95 · doi:10.1109/acc.1995.529783 · Cited by 1,926
Estimating Uncertain Spatial Relationships in Robotics
Smith, R., Self, M., & Cheeseman, P. (1990) · Autonomous Robot Vehicles · doi:10.1007/978-1-4613-8997-2_14 · Cited by 1,288
Proceedings 1992 IEEE International Conference on Robotics and Automation
(1992) · doi:10.1109/robot.1992 · Cited by 1,084
The ultra-wide bandwidth indoor channel: from statistical model to simulations
Cassioli, D., Win, M. Z., & Molisch, A. F. (2002) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2002.801228 · Cited by 953
The focussed D* algorithm for real-time replanning
Stentz, A. (1995) · Cited by 865
Bohlin, R., & Kavraki, L. E. (2000) · Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Proceedings (Cat. No.00CH37065) · doi:10.1109/robot.2000.844107 · Cited by 856
Estimating uncertain spatial relationships in robotics
Smith, R., Self, M., & Cheeseman, P. (2005) · Proceedings. 1987 IEEE International Conference on Robotics and Automation · doi:10.1109/robot.1987.1087846 · Cited by 757
Improved fast replanning for robot navigation in unknown terrain
Koenig, S., & Likhachev, M. (2003) · Proceedings 2002 IEEE International Conference on Robotics and Automation (Cat. No.02CH37292) · doi:10.1109/robot.2002.1013481 · Cited by 294
On the Probabilistic Foundations of Probabilistic Roadmap Planning
Hsu, D., Latombe, J.-C., & Kurniawati, H. (2006) · The International Journal of Robotics Research · doi:10.1177/0278364906067174 · Cited by 260
Anytime path planning and replanning in dynamic environments
van den Berg, J., Ferguson, D., & Kuffner, J. (2006) · Proceedings 2006 IEEE International Conference on Robotics and Automation, 2006. ICRA 2006. · doi:10.1109/robot.2006.1642056 · Cited by 241
The Stochastic Motion Roadmap: A Sampling Framework for Planning with Markov Motion Uncertainty
Alterovitz, R., Simeon, T., & Goldberg, K. (2007) · Robotics: Science and Systems III · doi:10.15607/rss.2007.iii.030 · Cited by 232
A nonrecursive algebraic solution for the discrete Riccati equation
Vaughan, D. (1970) · IEEE Transactions on Automatic Control · doi:10.1109/tac.1970.1099549 · Cited by 191
Coastal Navigation with Mobile Robots
Roy, N., & Thrun, S. (1999) · Cited by 146
Self-citationAdapting probabilistic roadmaps to handle uncertain maps
Missiuro, P. V., & Roy, N. (2006) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.2006.1641882 · Cited by 139
Self-citationAlterovitz, R., Branicky, M. S., & Goldberg, K. (2008) · Springer tracts in advanced robotics · doi:10.1007/978-3-540-68405-3_20 · Cited by 34
Robust range-based localization and motion planning under uncertainty using ultra-wideband radio
Prentice, S. (2007) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 1
Self-citation
Cited by
Sampling-based algorithms for optimal motion planning
Karaman, S., & Frazzoli, E. (2011) · The International Journal of Robotics Research · doi:10.1177/0278364911406761 · Cited by 5,275
Incremental Sampling-based Algorithms for Optimal Motion Planning
Karaman, S., & Frazzoli, E. (2010) · Robotics: Science and Systems VI · doi:10.15607/rss.2010.vi.034 · Cited by 680
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
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
Deliberation for autonomous robots: A survey
Ingrand, F., & Ghallab, M. (2017) · Artificial Intelligence · doi:10.1016/j.artint.2014.11.003 · Cited by 309
Metadata
- Authors
- Prentice, S., & Roy, N.
- Venue
- The International Journal of Robotics Research
- Publisher
- SAGE Publications
- Published
- 2009-07-21
- Volume
- 28
- Issue
- 11-12
- Pages
- 1448-1465
- ISSN
- 0278-3649 (ISSN-L)
- 1741-3176
- OpenAlex
- W2053833381
- Cited by
- 269
- References
- 26
- FWCI
- 14.29
- Type
- journal article
- Language
- en
- Open access
- green
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.