Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Robot path planning in narrow passages based on improved PRM method

  • Original Research Paper
  • Published:
Intelligent Service Robotics Aims and scope Submit manuscript

Abstract

Probabilistic roadmap (PRM) method has been shown to perform well in robot path planning. However, its performance degrades when the robot needs to pass through narrow passages. To solve this problem, an improved PRM method with hybrid uniform sampling and Gaussian sampling is proposed in this paper. With the proposed method, the robot can improve the success rate and efficiency of path planning in narrow passages. Firstly, the narrow-passage-aware Gaussian sampling method is developed for narrow passages. Combining uniform sampling globally, the new sampling strategy can increase the sampling density at the narrow passages and reduce the redundancy of the samples in the wide-open regions. Then, we propose to use density-based clustering method to achieve accurate identification of narrow channels by removing the noise points. Next, graph search algorithm is used to search the shortest path from the start point to the goal point. Finally, simulations are carried out to evaluate the validity of the proposed method. Results show that the improved PRM method is more effective for path planning with narrow passages.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Algorithm 1
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Xu M, Liu Y, Huang Q, Zhang Y, Luan G (2007) An improved Dijkstra’s shortest path algorithm for sparse network. Appl Math Comput 185(1):247–254

    MathSciNet  Google Scholar 

  2. Chaari I, Koubaa A, Bennaceur H, Ammar A, Alajlan M, Youssef H (2017) Design and performance analysis of global path planning techniques for autonomous mobile robots in grid environments. Int J Adv Rob Syst 14(2):1–15

    Google Scholar 

  3. Schoener M, Coyle E, Thompson D (2022) An anytime visibility-voronoi graph-search algorithm for generating robust and feasible unmanned surface vehicle paths. Auton Robot 46(8):911–927

    Article  Google Scholar 

  4. Sudhakara P, Ganapathy V, Priyadharshini B, Sundaran K (2018) Obstacle avoidance and navigation planning of a wheeled mobile robot using amended artificial potential field method. Procedia Comput Sci 133:998–1004

    Article  Google Scholar 

  5. Jia Q, Wang X (2010) An improved potential field method for path planning. In: 2010 Chinese control and decision conference, pp 2265–2270

  6. Bounini F, Gingras D, Pollart H, Gruyer D (2017) Modified artificial potential field method for online path planning applications. In: 2017 IEEE intelligent vehicles symposium (IV), pp 180–185

  7. Kashyap AK, Parhi DR (2023) Modified type-2 fuzzy controller for Intercollision avoidance of single and multi-humanoid robots in complex terrains. Intel Serv Robot 16(1):87–108

    Google Scholar 

  8. Karaman S, Frazzoli E (2010) Incremental sampling-based algorithms for optimal motion planning. Robot Sci Syst VI 104(2):267–274

    Google Scholar 

  9. Chen J, Zhou Y, Gong J, Deng Y (2019) An improved probabilistic roadmap algorithm with potential field function for path planning of quadrotor. In: 2019 Chinese control conference (CCC), pp 3248–3253

  10. Kingston Z, Moll M, Kavraki LE (2018) Sampling-based methods for motion planning with constraints. Ann Rev Control Robot Auton Syst 1:159–185

    Article  Google Scholar 

  11. Ichter B, Harrison J, Pavone M (2018) Learning sampling distributions for robot motion planning. In: 2018 IEEE International conference on robotics and automation (ICRA), pp. 7087–7094

  12. Babaiasl M, Yang F, Swensen JP (2022) Robotic needle steering: state-of-the-art and research challenges. Intel Serv Robot 15(5):679–711

    Article  Google Scholar 

  13. Morales EF, Murrieta-Cid R, Becerra I, Esquivel-Basaldua MA (2021) A survey on deep learning and deep reinforcement learning in robotics with a tutorial on deep reinforcement learning. Intel Serv Robot 14(5):773–805

    Article  Google Scholar 

  14. Lindemann SR, LaValle SM (2005) Current issues in sampling-based motion planning. In: Robotics research. The eleventh international symposium: with 303 figures, pp. 36–54

  15. Kavraki LE, Svestka P, Latombe J-C, Overmars MH (1996) Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Trans Robot Autom 12(4):566–580

    Article  Google Scholar 

  16. Bohlin R, Kavraki LE (2000) Path planning using lazy prm. In: Proceedings 2000 ICRA. Millennium Conference. In: IEEE international conference on robotics and automation. Symposia proceedings (Cat. No. 00CH37065), vol 1, pp 521–528

  17. Plaku E, Bekris KE, Chen BY, Ladd AM, Kavraki LE (2005) Sampling-based roadmap of trees for parallel motion planning. IEEE Trans Rob 21(4):597–608

    Article  Google Scholar 

  18. Chen P, Waslander S (2010) Kinodynamic motion planning for holonomic UAVS in complex 3d environments. In: AIAA Guidance, navigation, and control conference, p 7883

  19. An D, Mu Y, Wang Y, Li B, Wei Y (2023) Intelligent path planning technologies of underwater vehicles: a review. J Intell Robot Syst 107(2):22

    Article  Google Scholar 

  20. Sakcak B, Bascetta L, Ferretti G, Prandini M (2019) Sampling-based optimal kinodynamic planning with motion primitives. Auton Robot 43:1715–1732

    Article  Google Scholar 

  21. Zhai H, Egerstedt M, Zhou H (2022) Path exploration in unknown environments using Fokker-Planck equation on graph. J Intell Robot Syst 104(4):71

    Article  Google Scholar 

  22. Rantanen MT, Juhola M (2014) How to construct small probabilistic roadmaps with a good coverage? Adv Robot 28(22):1519–1531

    Article  Google Scholar 

  23. Palma B, Lima C, Caarls W, Vettorazzi D (2016) Wich probabilistic roadmap method should be used by a robot in an actual environment? An analysis of the main methods through simulations. IEEE Lat Am Trans 14(4):2020–2025

    Article  Google Scholar 

  24. Liu C, Chang J, Liu C (2009) Path planning for mobile robot based on an improved probabilistic roadmap method. Chin J Electron 18(3):395–399

    Google Scholar 

  25. Rodriguez S, Thomas S, Pearce R, Amato NM (2008) Resampl: A region-sensitive adaptive motion planner. In: Algorithmic foundation of robotics VII: selected contributions of the seventh international workshop on the algorithmic foundations of robotics, pp 285–300

  26. Rantanen MT (2011) A connectivity-based method for enhancing sampling in probabilistic roadmap planners. J Intell Robot Syst 64:161–178

    Article  Google Scholar 

  27. Elbanhawi M, Simic M (2014) Sampling-based robot motion planning: a review. IEEE ACCESS 2:56–77

    Article  Google Scholar 

  28. Rantanen MT, Juhola M (2015) Speeding up probabilistic roadmap planners with locality-sensitive hashing. Robotica 33(7):1491–1506

    Article  Google Scholar 

  29. Kala R (2018) Increased visibility sampling for probabilistic roadmaps. In: 2018 IEEE international conference on simulation, modeling, and programming for autonomous robots (SIMPAR), pp 87–92

  30. Wilmarth SA, Amato NM, Stiller PF (1999) Maprm: a probabilistic roadmap planner with sampling on the medial axis of the free space. In: Proceedings 1999 IEEE international conference on robotics and automation (Cat. No. 99CH36288C), vol 2, pp 1024–1031

  31. Boor V, Overmars MH, Van Der Stappen AF (1999) The gaussian sampling strategy for probabilistic roadmap planners. In: Proceedings 1999 IEEE international conference on robotics and automation (Cat. No. 99CH36288C), vol 2, pp 1018–1023

  32. Hsu D, Jiang T, Reif J, Sun Z (2003) The bridge test for sampling narrow passages with probabilistic roadmap planners. In: 2003 IEEE international conference on robotics and automation (cat. No. 03CH37422), vol 3, pp 4420–4426

  33. Ravankar AA, Ravankar A, Emaru T, Kobayashi Y (2020) Hpprm: hybrid potential based probabilistic roadmap algorithm for improved dynamic path planning of mobile robots. IEEE Access 8:221743–221766

  34. Chen G, Luo N, Liu D, Zhao Z, Liang C (2021) Path planning for manipulators based on an improved probabilistic roadmap method. Robot Comput Integr Manuf 72:102196

    Article  Google Scholar 

  35. Yang R, Li J, Jia Z, Wang S, Yao H, Dong E (2023) Epl-prm: equipotential line sampling strategy for probabilistic roadmap planners in narrow passages. Biomim Intell Robot 3(3):100112

    Google Scholar 

  36. Zhong J, Su J (2011) Narrow passages identification for probabilistic roadmap method. In: Proceedings of the 30th Chinese control conference, pp 3908–3912

  37. Jin Q, Hu Q, Zhao P, Wang S, Ai M (2023) An improved probabilistic roadmap planning method for safe indoor flights of unmanned aerial vehicles. Drones 7(2):92

    Article  Google Scholar 

Download references

Funding

This work was supported by the National Natural Science Foundation of China (62273129, 62203147), and Anhui Provincial Key Research and Development Plan (2022A05020025, 202304a05020077).

Author information

Authors and Affiliations

  1. School of Electrical Engineering and Automation, Hefei University of Technology, Tunxi Road 193, Hefei, 230009, Anhui, China

    Yunzhi Huang, Hui Wang, Liang Han & Yuquan Xu

Authors
  1. Yunzhi Huang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Hui Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Liang Han
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Yuquan Xu
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

Yunzhi Huang, Hui Wang, Liang Han and Yuquan Xu contributed to this paper.Yunzhi Huang provided the innovative points of this paper. Hui Wang and Yuquan Xu wrote several chapters of this paper respectively. According to the algorithm proposed in this paper,Yuquan Xu did the relevant simulations. Yunzhi Huang,Hui Wang and Liang Han checked the theory of the article.Yunzhi Huang and Liang Han checked the grammar rules of this paper.Each author discussed previous versions of the paper. All authors read and approved the final manuscript.

Corresponding author

Correspondence to Liang Han.

Ethics declarations

Conflict of interest

The authors have no relevant financial or non-financial interests to disclose.

Ethical approval

Not applicable.

Consent to participate

Not applicable.

Consent for publication

Not applicable.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Huang, Y., Wang, H., Han, L. et al. Robot path planning in narrow passages based on improved PRM method. Intel Serv Robotics 17, 609–620 (2024). https://doi.org/10.1007/s11370-024-00527-4

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11370-024-00527-4

Keywords