{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,2,29]],"date-time":"2024-02-29T11:15:23Z","timestamp":1709205323855},"reference-count":39,"publisher":"University of Zielona G\u00f3ra, Poland","issue":"4","license":[{"start":{"date-parts":[[2019,12,1]],"date-time":"2019-12-01T00:00:00Z","timestamp":1575158400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019,12,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Sampling-based motion planning is a powerful tool in solving the motion planning problem for a variety of different robotic platforms. As its application domains grow, more complicated planning problems arise that challenge the functionality of these planners. One of the main challenges in the implementation of a sampling-based planner is its weak performance when reacting to uncertainty in robot motion, obstacles motion, and sensing noise. In this paper, a multi-query sampling-based planner is presented based on the optimal probabilistic roadmaps algorithm that employs a hybrid sample classification and graph adjustment strategy to handle diverse types of planning uncertainty such as sensing noise, unknown static and dynamic obstacles and an inaccurate environment map in a discrete-time system. The proposed method starts by storing the collision-free generated samples in a matrix-grid structure. Using the resulting grid structure makes it computationally cheap to search and find samples in a specific region. As soon as the robot senses an obstacle during the execution of the initial plan, the occupied grid cells are detected, relevant samples are selected, and in-collision vertices are removed within the vision range of the robot. Furthermore, a second layer of nodes connected to the current direct neighbors are checked against collision, which gives the planner more time to react to uncertainty before getting too close to an obstacle. The simulation results for problems with various sources of uncertainty show a significant improvement compared with similar algorithms in terms of the failure rate, the processing time and the minimum distance from obstacles. The planner is also successfully implemented and tested on a TurtleBot in four different scenarios with uncertainty.<\/jats:p>","DOI":"10.2478\/amcs-2019-0047","type":"journal-article","created":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T09:30:32Z","timestamp":1578475832000},"page":"641-654","source":"Crossref","is-referenced-by-count":2,"title":["Multiquery Motion Planning in Uncertain Spaces: Incremental Adaptive Randomized Roadmaps"],"prefix":"10.61822","volume":"29","author":[{"given":"Weria","family":"Khaksar","sequence":"first","affiliation":[{"name":"Robotics and Intelligent Systems Group (ROBIN), Department of Informatics , University of Oslo , Ole Johan Dahls hus, Gaustadallen 23 B, N- 0373 Oslo , Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Md Zia","family":"Uddin","sequence":"additional","affiliation":[{"name":"Robotics and Intelligent Systems Group (ROBIN), Department of Informatics , University of Oslo , Ole Johan Dahls hus, Gaustadallen 23 B, N- 0373 Oslo , Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jim","family":"Torresen","sequence":"additional","affiliation":[{"name":"Robotics and Intelligent Systems Group (ROBIN), Department of Informatics , University of Oslo , Ole Johan Dahls hus, Gaustadallen 23 B, N- 0373 Oslo , Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"37438","published-online":{"date-parts":[[2019,12,31]]},"reference":[{"key":"2023050302360440863_j_amcs-2019-0047_ref_001_w2aab3b7b1b1b6b1ab1ab1Aa","unstructured":"Achtelik, M.W., Weiss, S., Chli, M. and Siegwart, R. (2013). Rapidly-exploring random belief trees for motion planning under uncertainty, IEEE International Conference on Robotics and Automation, ICRA 2013, Karlsruhe, Germany, pp. 3926\u20133932, DOI: 10.1109\/ICRA.2013.6631130.10.1109\/ICRA.2013.6631130"},{"key":"2023050302360440863_j_amcs-2019-0047_ref_002_w2aab3b7b1b1b6b1ab1ab2Aa","doi-asserted-by":"crossref","unstructured":"Agha-Mohammadi, A.A. and Chakravorty, S.A.N.M. (2014). FIRM: Sampling-based feedback motion-planning under motion uncertainty and imperfect measurements, International Journal of Robotics Research33(2): 268\u2013304, DOI: 10.1177\/0278364913501564.10.1177\/0278364913501564","DOI":"10.1177\/0278364913501564"},{"key":"2023050302360440863_j_amcs-2019-0047_ref_003_w2aab3b7b1b1b6b1ab1ab3Aa","doi-asserted-by":"crossref","unstructured":"Aoude, G.S., Luders, B.D., Joseph, J.M., Roy, N. and How, J.P. (2013). Probabilistically safe motion planning to avoid dynamic obstacles with uncertain motion patterns, Autonomous Robots35(1): 51\u201376, DOI: 10.1007\/s10514-013-9334-3.10.1007\/s10514-013-9334-3","DOI":"10.1007\/s10514-013-9334-3"},{"key":"2023050302360440863_j_amcs-2019-0047_ref_004_w2aab3b7b1b1b6b1ab1ab4Aa","doi-asserted-by":"crossref","unstructured":"Axelrod, B., Kaelbling, L.P. and Lozano-Perez, T. (2018). Provably safe robot navigation with obstacle uncertainty, International Journal of Robotics Research37(13-14): 1760\u20131774, DOI: 10.1177\/0278364918778338.10.1177\/0278364918778338","DOI":"10.1177\/0278364918778338"},{"key":"2023050302360440863_j_amcs-2019-0047_ref_005_w2aab3b7b1b1b6b1ab1ab5Aa","doi-asserted-by":"crossref","unstructured":"Belghith, K., Kabanza, F. and Hartman, L. (2013). Randomized path planning with preferences in highly complex dynamic environments, Robotica31(8): 1195\u20131208, DOI: 10.1017\/S0263574713000428.10.1017\/S0263574713000428","DOI":"10.1017\/S0263574713000428"},{"key":"2023050302360440863_j_amcs-2019-0047_ref_006_w2aab3b7b1b1b6b1ab1ab6Aa","doi-asserted-by":"crossref","unstructured":"Bry, A. and Roy, N. (2011). Rapidly-exploring random belief trees for motion planning under uncertainty, IEEE International Conference on Robotics and Automation, ICRA 2011, Shanghai, China, pp. 723\u2013730, DOI: 10.1109\/ICRA.2011.5980508.10.1109\/ICRA.2011.5980508","DOI":"10.1109\/ICRA.2011.5980508"},{"key":"2023050302360440863_j_amcs-2019-0047_ref_007_w2aab3b7b1b1b6b1ab1ab7Aa","doi-asserted-by":"crossref","unstructured":"Burns, B. and Brock, O. (2007). Sampling-based motion planning with sensing uncertainty, IEEE International Conference on Robotics and Automation, ICRA 2007, Rome, Italy, pp. 3313\u20133318, DOI: 10.1109\/ROBOT.2007.363984.10.1109\/ROBOT.2007.363984","DOI":"10.1109\/ROBOT.2007.363984"},{"key":"2023050302360440863_j_amcs-2019-0047_ref_008_w2aab3b7b1b1b6b1ab1ab8Aa","unstructured":"Canny, J. (1988). The Complexity of Robot Motion Planning, MIT Press, Cambridge, MA."},{"key":"2023050302360440863_j_amcs-2019-0047_ref_009_w2aab3b7b1b1b6b1ab1ab9Aa","unstructured":"Choset, H.M., Hutchinson, S., Lynch, K.M., Kantor, G., Burgard, W., Kavraki, L.E. and Thrun, S. (2005). Principles of Robot Motion: Theory, Algorithms, and Implementations, MIT Press, Cambridge, MA."},{"key":"2023050302360440863_j_amcs-2019-0047_ref_010_w2aab3b7b1b1b6b1ab1ac10Aa","doi-asserted-by":"crossref","unstructured":"Elbanhawi, M. and Simic, M. (2014). Sampling-based robot motion planning: A review, IEEE Access2: 56\u201377, DOI: 10.1109\/ACCESS.2014.2302442.10.1109\/ACCESS.2014.2302442","DOI":"10.1109\/ACCESS.2014.2302442"},{"key":"2023050302360440863_j_amcs-2019-0047_ref_011_w2aab3b7b1b1b6b1ab1ac11Aa","doi-asserted-by":"crossref","unstructured":"Gonz\u00e1lez, D., P\u00e9rez, J., Milan\u00e9s, V. and Nashashibi, F. (2016). A review of motion planning techniques for automated vehicles, IEEE Transactions on Intelligent Transportation Systems17(4): 1135\u20131145, DOI: 10.1109\/TITS.2015.2498841.10.1109\/TITS.2015.2498841","DOI":"10.1109\/TITS.2015.2498841"},{"key":"2023050302360440863_j_amcs-2019-0047_ref_012_w2aab3b7b1b1b6b1ab1ac12Aa","doi-asserted-by":"crossref","unstructured":"Ha, J.S., Choi, H.L. and Jeon, J.H. (2018). Iterative methods for efficient sampling-based optimal motion planning of nonlinear systems, International Journal of Applied Mathematics and Computer Science28(1): 155\u2013168, DOI: 10.2478\/amcs-2018-0012.10.2478\/amcs-2018-0012","DOI":"10.2478\/amcs-2018-0012"},{"key":"2023050302360440863_j_amcs-2019-0047_ref_013_w2aab3b7b1b1b6b1ab1ac13Aa","doi-asserted-by":"crossref","unstructured":"Hsu, D., Kindel, R., Latombe, J.C. and Rock, S. (2002). Randomized kinodynamic motion planning with moving obstacles, International Journal of Robotics Research21(3): 233\u2013255, DOI: 10.1177\/027836402320556421.10.1177\/027836402320556421","DOI":"10.1177\/027836402320556421"},{"key":"2023050302360440863_j_amcs-2019-0047_ref_014_w2aab3b7b1b1b6b1ab1ac14Aa","doi-asserted-by":"crossref","unstructured":"Jafarzadeh, H. and Fleming, C.H. (2018). An exact geometry-based algorithm for path planning, International Journal of Applied Mathematics and Computer Science28(3): 493\u2013504, DOI: 10.2478\/amcs-2018-0038.10.2478\/amcs-2018-0038","DOI":"10.2478\/amcs-2018-0038"},{"key":"2023050302360440863_j_amcs-2019-0047_ref_015_w2aab3b7b1b1b6b1ab1ac15Aa","doi-asserted-by":"crossref","unstructured":"Jaillet, L., Hoffman, J., Van den Berg, J., Abbeel, P., Porta, J.M. and Goldberg, K. (2011). EG-RRT: Environment-guided random trees for kinodynamic motion planning with uncertainty and obstacles, IEEE\/RSJ International Conference on Intelligent Robots and Systems, IROS 2011, San Francisco, CA, USA, pp. 2646\u20132652, DOI: 10.1109\/IROS.2011.6094802.10.1109\/IROS.2011.6094802","DOI":"10.1109\/IROS.2011.6094802"},{"key":"2023050302360440863_j_amcs-2019-0047_ref_016_w2aab3b7b1b1b6b1ab1ac16Aa","unstructured":"Jaillet, L. and Simeon, T. (2004). A PRM-based motion planner for dynamically changing environments, Proceedings of the IEEE\/RSJ International Conference on Intelligent Robots and Systems, IROS 2004, Sendai, Japan, pp. 1606\u20131611, DOI: 10.1109\/IROS.2004.1389625.10.1109\/IROS.2004.1389625"},{"key":"2023050302360440863_j_amcs-2019-0047_ref_017_w2aab3b7b1b1b6b1ab1ac17Aa","doi-asserted-by":"crossref","unstructured":"Jaillet, L. and Sim\u00e9on, T. (2008). Path deformation roadmaps: Compact graphs with useful cycles for motion planning, The International Journal of Robotics Research27(11).10.1177\/0278364908098411","DOI":"10.1177\/0278364908098411"},{"key":"2023050302360440863_j_amcs-2019-0047_ref_018_w2aab3b7b1b1b6b1ab1ac18Aa","doi-asserted-by":"crossref","unstructured":"Janson, L., Ichter, B. and Pavone, M. (2018). Deterministic sampling-based motion planning: Optimality, complexity, and performance, International Journal of Robotics Research37(1): 46\u201361, DOI: 10.1177\/0278364917714338.10.1177\/0278364917714338","DOI":"10.1177\/0278364917714338"},{"key":"2023050302360440863_j_amcs-2019-0047_ref_019_w2aab3b7b1b1b6b1ab1ac19Aa","doi-asserted-by":"crossref","unstructured":"Karaman, S. and Frazzoli, E. (2011). Sampling-based algorithms for optimal motion planning, International Journal of Robotics Research30(7): 846\u2013894, DOI: 10.1177\/0278364911406761.10.1177\/0278364911406761","DOI":"10.1177\/0278364911406761"},{"key":"2023050302360440863_j_amcs-2019-0047_ref_020_w2aab3b7b1b1b6b1ab1ac20Aa","doi-asserted-by":"crossref","unstructured":"Kavraki, L.E., Svestka, P., Latombe, J.C. and Overmars, M.H. (1996). Probabilistic roadmaps for path planning in high-dimensional configuration spaces, IEEE Transactions on Robots and Automation12(4): 566\u2013580, DOI: 10.1109\/70.508439.10.1109\/70.508439","DOI":"10.1109\/70.508439"},{"key":"2023050302360440863_j_amcs-2019-0047_ref_021_w2aab3b7b1b1b6b1ab1ac21Aa","unstructured":"Khaksar, W., Tang, S.H., Ismail, N. and Arrifin, M. (2012). A review on robot motion planning approaches, Pertanika Journal of Science & Technology20(1): 15\u201329."},{"key":"2023050302360440863_j_amcs-2019-0047_ref_022_w2aab3b7b1b1b6b1ab1ac22Aa","doi-asserted-by":"crossref","unstructured":"Khaksar, W., Tang, S.H., Khaksar, M. and Motlagh, O. (2013). A low dispersion probabilistic roadmaps (LD-PRM) algorithm for fast and efficient sampling-based motion planning, International Journal of Advanced Robotic Systems10(11): 1\u201310, DOI: 10.5772\/56973.10.5772\/56973","DOI":"10.5772\/56973"},{"key":"2023050302360440863_j_amcs-2019-0047_ref_023_w2aab3b7b1b1b6b1ab1ac23Aa","doi-asserted-by":"crossref","unstructured":"Kingston, Z., Moll, M. and Kavraki, L.E. (2018). Sampling-based methods for motion planning with constraints, Annual Review of Control, Robotics, and Autonomous Systems1: 159\u2013185, DOI: 10.1146\/annurev-control-060117-105226.10.1146\/annurev-control-060117-105226","DOI":"10.1146\/annurev-control-060117-105226"},{"key":"2023050302360440863_j_amcs-2019-0047_ref_024_w2aab3b7b1b1b6b1ab1ac24Aa","doi-asserted-by":"crossref","unstructured":"Klau\u010do, M., Bla\u017eek, S. and Kvasnica, M. (2016). An optimal path planning problem for heterogeneous multi-vehicle systems, International Journal of Applied Mathematics and Computer Science26(2): 297\u2013308, DOI: 10.1515\/amcs-2016-0021.10.1515\/amcs-2016-0021","DOI":"10.1515\/amcs-2016-0021"},{"key":"2023050302360440863_j_amcs-2019-0047_ref_025_w2aab3b7b1b1b6b1ab1ac25Aa","doi-asserted-by":"crossref","unstructured":"Kurniawati, H., Bandyopadhyay, T. and Patrikalakis, N.M. (2012). Global motion planning under uncertain motion, sensing, and environment map, Autonomous Robots33(3): 255\u2013272, DOI: 10.1007\/s10514-012-9307-y.10.1007\/s10514-012-9307-y","DOI":"10.1007\/s10514-012-9307-y"},{"key":"2023050302360440863_j_amcs-2019-0047_ref_026_w2aab3b7b1b1b6b1ab1ac26Aa","doi-asserted-by":"crossref","unstructured":"LaValle, S.M. and Kuffner, J.J. (2001). Randomized kinodynamic planning, The International Journal of Robotics Research25(5): 378\u2013400, DOI: 10.1177\/02783640122067453.10.1177\/02783640122067453","DOI":"10.1177\/02783640122067453"},{"key":"2023050302360440863_j_amcs-2019-0047_ref_027_w2aab3b7b1b1b6b1ab1ac27Aa","doi-asserted-by":"crossref","unstructured":"Leven, P. and Hutchinson, S. (2011). A framework for real-time path planning in changing environments, The International Journal of Robotics Research21(12): 999\u20131030, DOI: 10.1177\/0278364902021012001.10.1177\/0278364902021012001","DOI":"10.1177\/0278364902021012001"},{"key":"2023050302360440863_j_amcs-2019-0047_ref_028_w2aab3b7b1b1b6b1ab1ac28Aa","doi-asserted-by":"crossref","unstructured":"Li, D., Li, Q., Cheng, N. and Song, J. (2014). Sampling-based real-time motion planning under state uncertainty for autonomous micro-aerial vehicles in GPS-denied environments, Sensors14(11): 21791\u201321825, DOI: 10.3390\/s141121791.10.3390\/s141121791427956225412217","DOI":"10.3390\/s141121791"},{"key":"2023050302360440863_j_amcs-2019-0047_ref_029_w2aab3b7b1b1b6b1ab1ac29Aa","doi-asserted-by":"crossref","unstructured":"Liu, W. and Ang, M.H. (2014). Incremental sampling-based algorithm for risk-aware planning under motion uncertainty, IEEE International Conference on Robotics and Automation, ICRA 2014, Hong Kong, China, pp. 2051\u20132058, DOI: 10.1109\/ICRA.2014.6907131.10.1109\/ICRA.2014.6907131","DOI":"10.1109\/ICRA.2014.6907131"},{"key":"2023050302360440863_j_amcs-2019-0047_ref_030_w2aab3b7b1b1b6b1ab1ac30Aa","doi-asserted-by":"crossref","unstructured":"Luders, B.D. and How, J.P. (2014). An optimizing sampling-based motion planner with guaranteed robustness to bounded uncertainty, American Control Conference, ACC 2014, Portland, OR, USA, pp. 771\u2013777, DOI: 10.1109\/ACC.2014.6859383.10.1109\/ACC.2014.6859383","DOI":"10.1109\/ACC.2014.6859383"},{"key":"2023050302360440863_j_amcs-2019-0047_ref_031_w2aab3b7b1b1b6b1ab1ac31Aa","doi-asserted-by":"crossref","unstructured":"Luna, R., S\u00b8ucan, I.A., Moll, M. and Kavraki, L.E. (2013). Anytime solution optimization for sampling-based motion planning, IEEE International Conference on Robotics and Automation, ICRA 2013, Karlsruhe, Germany, pp. 5068\u20135074, DOI: 10.1109\/ICRA.2013.6631301.10.1109\/ICRA.2013.6631301","DOI":"10.1109\/ICRA.2013.6631301"},{"key":"2023050302360440863_j_amcs-2019-0047_ref_032_w2aab3b7b1b1b6b1ab1ac32Aa","doi-asserted-by":"crossref","unstructured":"Otte, M. and Frazzoli, E. (2016). RRTX: Asymptotically optimal single-query sampling-based motion planning with quick replanning, International Journal of Robotics Research35(7): 797\u2013822, DOI: 10.1177\/0278364915594679.10.1177\/0278364915594679","DOI":"10.1177\/0278364915594679"},{"key":"2023050302360440863_j_amcs-2019-0047_ref_033_w2aab3b7b1b1b6b1ab1ac33Aa","doi-asserted-by":"crossref","unstructured":"Pilania, V. and Gupta, K. (2017). Localization aware sampling and connection strategies for incremental motion planning under uncertainty, Autonomous Robots41(1): 111\u2013132, DOI: 10.1007\/s10514-015-9536-y.10.1007\/s10514-015-9536-y","DOI":"10.1007\/s10514-015-9536-y"},{"key":"2023050302360440863_j_amcs-2019-0047_ref_034_w2aab3b7b1b1b6b1ab1ac34Aa","doi-asserted-by":"crossref","unstructured":"Pilania, V. and Gupta, K. (2018). Mobile manipulator planning under uncertainty in unknown environments under uncertainty, International Journal of Robotics Research37(2\u20133): 316\u2013339, DOI: 10.1177\/0278364918754677.10.1177\/0278364918754677","DOI":"10.1177\/0278364918754677"},{"key":"2023050302360440863_j_amcs-2019-0047_ref_035_w2aab3b7b1b1b6b1ab1ac35Aa","doi-asserted-by":"crossref","unstructured":"Przybylski, M. and Putz, B. (2017). D* Extra Lite: A dynamic A* with searchtree cutting and frontiergap repairing, International Journal of Applied Mathematics and Computer Science27(2): 273\u2013290, DOI: 10.1515\/amcs-2017-0020.10.1515\/amcs-2017-0020","DOI":"10.1515\/amcs-2017-0020"},{"key":"2023050302360440863_j_amcs-2019-0047_ref_036_w2aab3b7b1b1b6b1ab1ac36Aa","doi-asserted-by":"crossref","unstructured":"Shan, T. and Englot, B. (2017). Belief roadmap search: Advances in optimal and efficient planning under uncertainty, IEEE International Conference on Intelligent Robots and Systems, IROS 2017, Vancouver, BC, Canada, pp. 5318\u20135325, DOI: 10.1109\/IROS.2017.8206425.10.1109\/IROS.2017.8206425","DOI":"10.1109\/IROS.2017.8206425"},{"key":"2023050302360440863_j_amcs-2019-0047_ref_037_w2aab3b7b1b1b6b1ab1ac37Aa","doi-asserted-by":"crossref","unstructured":"Summers, T. (2018). Distributionally robust sampling-based motion planning under uncertainty, IEEE International Conference on Intelligent Robots and Systems, IROS 2017, Vancouver, BC, Canada, pp. 6518\u20136523, DOI: 10.1109\/IROS.2018.8593893.10.1109\/IROS.2018.8593893","DOI":"10.1109\/IROS.2018.8593893"},{"key":"2023050302360440863_j_amcs-2019-0047_ref_038_w2aab3b7b1b1b6b1ab1ac38Aa","doi-asserted-by":"crossref","unstructured":"Sun, W., Patil, S. and Alterovitz, R. (2015). High-frequency replanning under uncertainty using parallel sampling-based motion planning, IEEE Transactions on Robotics31(1): 104\u2013116, DOI: 10.1109\/TRO.2014.2380273.10.1109\/TRO.2014.2380273453573126279645","DOI":"10.1109\/TRO.2014.2380273"},{"key":"2023050302360440863_j_amcs-2019-0047_ref_039_w2aab3b7b1b1b6b1ab1ac39Aa","doi-asserted-by":"crossref","unstructured":"Vasquez-Gomez, J.I., Sucar, L.E. and Murrieta-Cid, R. (2017). View\/state planning for three-dimensional object reconstruction under uncertainty, Autonomous Robots41(1): 89\u2013109, DOI: 10.1007\/s10514-015-9531-3.10.1007\/s10514-015-9531-3","DOI":"10.1007\/s10514-015-9531-3"}],"container-title":["International Journal of Applied Mathematics and Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/content.sciendo.com\/view\/journals\/amcs\/29\/4\/article-p641.xml","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.sciendo.com\/pdf\/10.2478\/amcs-2019-0047","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,29]],"date-time":"2024-02-29T10:29:36Z","timestamp":1709202576000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.sciendo.com\/article\/10.2478\/amcs-2019-0047"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12,1]]},"references-count":39,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2019,12,31]]},"published-print":{"date-parts":[[2019,12,1]]}},"alternative-id":["10.2478\/amcs-2019-0047"],"URL":"https:\/\/doi.org\/10.2478\/amcs-2019-0047","relation":{},"ISSN":["2083-8492"],"issn-type":[{"value":"2083-8492","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,12,1]]}}}