[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

A state-of-the-art review on topology and differential geometry-based robotic path planning—part I: planning under static constraints

  • Regular Paper
  • Published:
International Journal of Intelligent Robotics and Applications Aims and scope Submit manuscript

Abstract

Autonomous robotics has permeated several industrial, research and consumer robotic applications, of which path planning is an important component. The path planning algorithm of choice is influenced by the application at hand and the history of algorithms used for such applications. The latter is dependent on an extensive conglomeration and classification of path planning literature, which is what this work focuses on. Specifically, we accomplish the following: typical classifications of path planning algorithms are provided. Such classifications rely on differences in knowledge of the environment (known/unknown), robot (model-specific/generic), and constraints (static/dynamic). This classification however, is not comprehensive. Thus, as a resolution, we propose a detailed taxonomy based on a fundamental parameter of the space, i.e. its ability to be characterized as a set of disjoint or connected points. We show that this taxonomy encompasses important attributes of path planning problems, such as connectivity and partitioning of spaces. Consequently, path planning spaces in robotics may be viewed as simply a set of points, or as manifolds. The former can further be divided into unpartitioned and partitioned spaces, of which the former uses variants of sampling algorithms, optimization algorithms, model predictive controls, and evolutionary algorithms, while the latter uses cell decomposition and graph traversal, and sampling-based optimization techniques.This article achieves the following two goals: The first is the introduction of an all-encompassing taxonomy of robotic path planning. The second is to streamline the migration of path planning work from disciplines such as mathematics and computer vision to robotics, into one comprehensive survey. Thus, the main contribution of this work is the review of works for static constraints that fall under the proposed taxonomy, i.e., specifically under topology and manifold-based methods. Additionally, further taxonomy is introduced for manifold-based path planning, based on incremental construction or one-step explicit parametrization of the space.

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
£29.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 includes VAT (United Kingdom)

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
Fig. 9
Fig. 10
Fig. 11

Similar content being viewed by others

Explore related subjects

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

Availability of data and materials

There is no data or materials to share.

Code availability

Not applicable.

Abbreviations

2LPM:

2-Link planar manipulator

ACO:

Ant colony optimization

APF:

Artificial potential field

BFP:

Best first planner

CCM:

Closed chain manipulator

CDGT:

Cell decomposition and graph traversal

CFDM:

Constraint-free discretized manifold

CFDMPP:

Constraint-free discretized manifolds-based path planner

CFM:

Constraint-free manifold

CS:

Constraint set

CV:

Certainty value

DAPF:

Dubin’s APF

DC:

Dynamic constraint

DCS:

Disjoint constraint set

DMP:

Dynamic movement primitives

DOF:

Degrees of freedom

DTD:

Dynamic topology detector

EA:

Evolutionary algorithm

EE:

End-effector

FSF:

Free space force

FSH:

Free space histogram

GA:

Genetic algorithm

GVD:

Generalized Voronoi diagram

HA*:

Homotopic A*

HB:

Homotopic bug

HBM:

Homotopy based method

HCM:

Homotopy continuation methods

HIMM:

Histogram in motion mapping

HRRT:

Homotopic RRT

HSFM:

Headed social force model

ICE:

Inner constraint edge

IFTM:

Inverse function theorem for manifolds

LAG:

L-augmented graph

LPRM:

Lazy PRM

LM-RRT:

Machine learning-based multi-RRT

MA:

Memetic algorithm

MBM:

Model based methods

MPC:

Model predictive control

MR:

Mobile robot

NAES:

Non-linear algebraic equation system

NF:

Navigation functions

NLOC:

Non-linear optimal control

NOCP:

Non-linear optimal control problem

NOP:

Non-linear optimization problem

OA:

Optimization algorithm

OCE:

Outer constraint edge

OCM:

Open chain manipulator

P-RRT*:

Potential functions-based RRT*

PDR:

Path deformation roadmap

PGD-RRT*:

Potential guided directionalized-RRT*

PPM:

Path planning manifold

PPP:

Path planning problem

PPS:

Path planning space

PPPS:

Primary path planning space

PRM:

Probabilistic road map

PRM*:

Probabilistic road map*

PSM:

Product smooth manifold

PSO:

Particle swarm optimization

RPP:

Randomized path planner

RRG:

Rapidly exploring random graph

RRT:

Rapidly exploring random tree

RRT*:

Rapidly exploring random tree*

RRT*-AB:

RRT*-adjustable bounds

SA:

Sampling algorithm

SC:

Static constraint

SFLA:

Shuffled frog leaping algorithm

SHIO:

Single homotopy inducing obstacle

SLPRM:

Semi-lazy PRM

SM:

Smooth manifold

SO:

Special orthogonal group

SPPS:

Secondary path planning space

SR:

Stationary robot

S-RRT:

Smoothly-RRT

TG:

Tangent graph

TM:

Topological manifold

T-RRT:

Transition-based RRT

UGV:

Unmanned ground vehicle

UAV:

Unmanned aerial vehicle

UUV:

Unmanned underwater vehicle

VG:

Visibility graph

VOS:

Velocity obstacle sets

VFF:

Virtual force fields

References

  • Abbas, M.A., Milman, R., Eklund, J.M.: Obstacle avoidance in real time with nonlinear model predictive control of autonomous vehicles. In: 2014 IEEE 27th Canadian Conference on Electrical and Computer Engineering (CCECE), pp. 1–6 (2014). https://doi.org/10.1109/CCECE.2014.6901109

  • Ademovic, A., Lacevic, B.: Path planning for robotic manipulators using expanded bubbles of free c-space. In: 2016 IEEE International Conference on Robotics and Automation (ICRA), vol. 2016, pp. 77–82. IEEE, Stockholm (2016). https://doi.org/10.1109/ICRA.2016.7487118

  • Aghababa, M.P.: 3D path planning for underwater vehicles using five evolutionary optimization algorithms avoiding static and energetic obstacles. Appl. Ocean Res. 38, 48–62 (2012)

    Article  Google Scholar 

  • Agirrebeitia, J., Avilés, R., de Bustos, I.F., Ajuria, G.: A new APF strategy for path planning in environments with obstacles. Mech. Mach. Theory 40(6), 645–658 (2005)

    Article  MathSciNet  Google Scholar 

  • Akbaripour, H., Akbaripour, H., Masehian, E., Masehian, E.: Semi-lazy probabilistic roadmap: a parameter-tuned, resilient and robust path planning method for manipulator robots. Int. J. Adv. Manuf. Technol. 89(5), 1401–1430 (2017)

    Article  Google Scholar 

  • Atramentov, A., LaValle, S.M.: Efficient nearest neighbor searching for motion planning. In: Proceedings 2002 IEEE International Conference on Robotics and Automation (Cat. No.02CH37292), vol. 1, pp. 632–6371 (2002). https://doi.org/10.1109/ROBOT.2002.1013429

  • Barraquand, J., Latombe, J.-C.: Robot motion planning: a distributed representation approach. Int. J. Robot. Res. 10(6), 628–649 (2016)

    Article  Google Scholar 

  • Berenson, D., Srinivasa, S., Kuffner, J.: Task space regions: a framework for pose-constrained manipulation planning. Int. J. Robot. Res. 30(12), 1435–1460 (2011)

    Article  Google Scholar 

  • Bhattacharya, S.: Towards optimal path computation in a simplicial complex. Int. J. Robot. Res. 38(8), 981–1009 (2019)

    Article  Google Scholar 

  • Bhattacharya, S., Pivtoraiko, M.: A classification of configuration spaces of planar robot arms for a continuous inverse kinematics problem. Acta Applicandae Mathematicae 139(1), 133–166 (2015)

    Article  MathSciNet  Google Scholar 

  • Bhattacharya, S., Likhachev, M., Kumar, V.: Topological constraints in search-based robot path planning. Auton. Robot. 33(3), 273–290 (2012)

    Article  Google Scholar 

  • Bhattacharya, S., Ghrist, R., Kumar, V.: Multi-robot coverage and exploration on Riemannian manifolds with boundaries. Int. J. Robot. Res. 33(1), 113–137 (2014)

    Article  Google Scholar 

  • Blaszczyk, Z., Carrasquel-Vera, J.G.: Topological complexity and efficiency of motion planning algorithms. Revista Matemática Iberoamericana 34(4), 1679–1684 (2018)

    Article  MathSciNet  Google Scholar 

  • Bohigas, O., Henderson, M.E., Ros, L., Porta, J.M.: A singularity-free path planner for closed-chain manipulators. In: 2012 IEEE International Conference on Robotics and Automation, pp. 2128–2134. IEEE, Saint Paul (2012). https://doi.org/10.1109/ICRA.2012.6224899

  • Bohigas, O., Henderson, M.E., Ros, L., Manubens, M., Porta, J.M.: Planning singularity-free paths on closed-chain manipulators. IEEE Trans. Robot. 29(4), 888–898 (2013). https://doi.org/10.1109/TRO.2013.2260679

    Article  Google Scholar 

  • Bohlin, R., Kavraki, L.E.: Path planning using lazy PRM. In: Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Proceedings (Cat. No.00CH37065), vol. 1, pp. 521–5281 (2000). https://doi.org/10.1109/ROBOT.2000.844107

  • Brooks, R.A.: Planning collision-free motions for pick-and-place operations. Int. J. Robot. Res. 2(4), 19–44 (1983)

    Article  Google Scholar 

  • Campana, M., Lamiraux, F., Laumond, J.-P.: A gradient-based path optimization method for motion planning. Adv. Robot. 30(17–18), 1126–1144 (2016)

    Article  Google Scholar 

  • Carpin, S., Pillonetto, G.: Motion planning using adaptive random walks. IEEE Trans. Robot. 21(1), 129–136 (2005)

    Article  Google Scholar 

  • Chu, K., Lee, M., Sunwoo, M.: Local path planning for off-road autonomous driving with avoidance of static obstacles. IEEE Trans. Intell. Transp. Syst. 13(4), 1599–1616 (2012)

    Article  Google Scholar 

  • Dale, L.K., Amato, N.M.: Probabilistic roadmaps-putting it all together. In: Proceedings 2001 ICRA. IEEE International Conference on Robotics and Automation (Cat. No.01CH37164), vol. 2, pp. 1940–19472 (2001). https://doi.org/10.1109/ROBOT.2001.932892

  • Dash, A.K., Chen, I.-M., Yeo, S.H., Yang, G.: Singularity-free path planning of parallel manipulators using clustering algorithm and line geometry. In: 2003 IEEE International Conference on Robotics and Automation (Cat. No.03CH37422), vol. 1, pp. 761–766 (2003)

  • Diankov, R., Kuffner, J.: Randomized statistical path planning. In: 2007 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 1–6 (2007). https://doi.org/10.1109/IROS.2007.4399557

  • Donald, B., Lynch, K.K.M., Rus, D. (eds.): Algorithmic and Computational Robotics: New Directions 2000 WAFR, 1st edn. A K Peters/CRC Press, an imprint of Taylor and Francis, Boca Raton (2001)

  • Dorst, L., Mandhyan, I., Trovato, K.: The geometrical representation of path planning problems. Robot. Auton. Syst. 7(2), 181–195 (1991)

    Article  Google Scholar 

  • Elbanhawi, M., Simic, M.: Sampling-based robot motion planning: a review. IEEE Access 2, 56–77 (2014). https://doi.org/10.1109/ACCESS.2014.2302442

    Article  Google Scholar 

  • Farber, M.: Topological complexity of motion planning. Discret. Comput. Geom. 29(2), 211–221 (2003)

    Article  MathSciNet  Google Scholar 

  • Faverjon, B., Tournassoud, P.: A local based approach for path planning of manipulators with a high number of degrees of freedom. In: Proceedings. 1987 IEEE International Conference on Robotics and Automation, vol. 4, pp. 1152–1159 (1987). https://doi.org/10.1109/ROBOT.1987.1087982

  • Ferguson, D., Stentz, A.: Anytime RRTs. In: 2006 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 5369–5375 (2006). https://doi.org/10.1109/IROS.2006.282100

  • Gao, Y., Lin, T., Borrelli, F., Tseng, E., Hrovat, D.: Predictive control of autonomous ground vehicles with obstacle avoidance on slippery roads. In: Dynamic Systems and Control Conference, ASME 2010 Dynamic Systems and Control Conference, vol. 1, pp. 265–272. ASME (2010). https://doi.org/10.1115/DSCC2010-4263

  • Gao, Y., Gray, A., Tseng, H.E., Borrelli, F.: A tube-based robust nonlinear predictive control approach to semiautonomous ground vehicles. Veh. Syst. Dyn. 52(6), 802–823 (2014). https://doi.org/10.1080/00423114.2014.902537

    Article  Google Scholar 

  • Havoutis, I., Ramamoorthy, S.: Motion planning and reactive control on learnt skill manifolds. Int. J. Robot. Res. 32(9–10), 1120–1150 (2013)

    Article  Google Scholar 

  • Henderson, M.E.: Multiple parameter continuation: computing implicitly defined k-manifolds. Int. J. Bifurc. Chaos Appl. Sci. Eng. 12(3), 451–476 (2002)

    Article  MathSciNet  Google Scholar 

  • Hsu, D., Sun, Z.: Adaptively combining multiple sampling strategies for probabilistic roadmap planning. In: IEEE Conference on Robotics, Automation and Mechatronics, 2004., vol. 2, pp. 774–7792 (2004). https://doi.org/10.1109/RAMECH.2004.1438016

  • Jaillet, L., Porta, J.: Asymptotically-optimal path planning on manifolds. Robot. Sci. Syst. VIII:145–152 (2012)

    Google Scholar 

  • Jaillet, L., Porta, J.M.: Path planning under kinematic constraints by rapidly exploring manifolds. IEEE Trans. Robot. 29(1), 105–117 (2013). https://doi.org/10.1109/TRO.2012.2222272

    Article  Google Scholar 

  • Jaillet, L., Simeon, T.: Path deformation roadmaps: compact graphs with useful cycles for motion planning. Int. J. Robot. Res. 27(11–12), 1175–1188 (2008). https://doi.org/10.1177/0278364908098411

    Article  Google Scholar 

  • Jaillet, L., Cortés, J., Siméon, T.: Sampling-based path planning on configuration-space costmaps. IEEE Trans. Robot. 26(4), 635–646 (2010)

    Article  Google Scholar 

  • Kang, G., Kim, Y.B., Lee, Y.H., Oh, H.S., You, W.S., Choi, H.R.: Sampling-based motion planning of manipulator with goal-oriented sampling. Intell. Serv. Robot. 12(3), 265–273 (2019)

    Article  Google Scholar 

  • Karaman, S., Frazzoli, E.: Sampling-based algorithms for optimal motion planning. Int. J. Robot. Res. 30(7), 846–894 (2011)

    Article  Google Scholar 

  • Kavraki, L.E., Svestka, P., Latombe, J.-C., Overmars, M.H.: Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Trans. Robot. Autom. 12(4), 566–580 (1996). https://doi.org/10.1109/70.508439

    Article  Google Scholar 

  • Kavraki, L.E., Kolountzakis, M.N., Latombe, J.C.: Analysis of probabilistic roadmaps for path planning. IEEE Trans. Robot. Autom. 14(1), 166–171 (1998). https://doi.org/10.1109/70.660866

    Article  Google Scholar 

  • Kennedy, M., Thakur, D., Ani Hsieh, M., Bhattacharya, S., Kumar, V.: Optimal paths for polygonal robots in SE(2). J. Mech. Robot. 10(2), 021005-1–021005-8 (2018)

    Article  Google Scholar 

  • Khatib, O.: Real-time obstacle avoidance for manipulators and mobile robots. Int. J. Robot. Res. 5(1), 90–98 (1986)

    Article  Google Scholar 

  • Khosla, P., Volpe, R.: Superquadric artificial potentials for obstacle avoidance and approach. In: Proceedings. 1988 IEEE International Conference on Robotics and Automation, pp. 1778–17843 (1988). https://doi.org/10.1109/ROBOT.1988.12323

  • Kim, H., Cheang, U.K., Rogowski, L.W., Kim, M.J.: Motion planning of particle based microrobots for static obstacle avoidance. J. Micro-Bio Robot. 14(1–2), 41–49 (2018)

    Article  Google Scholar 

  • Kimmel, R., Sethian, J.A.: Computing geodesic paths on manifolds. Proc. Natl. Acad. Sci. 95(15), 8431–8435 (1998)

    Article  MathSciNet  Google Scholar 

  • Koditschek, D.: Exact robot navigation by means of potential functions: some topological considerations. In: Proceedings. 1987 IEEE International Conference on Robotics and Automation, vol. 4, pp. 1–6 (1987). https://doi.org/10.1109/ROBOT.1987.1088038

  • Koditschek, D.E., Rimon, E.: Robot navigation functions on manifolds with boundary. Adv. Appl. Math. 11(4), 412–442 (1990)

    Article  MathSciNet  Google Scholar 

  • Kowalczyk, W.: Rapid navigation function control for two-wheeled mobile robots. J. Intell. Robot. Syst. 93(3–4), 687–697 (2018)

    Google Scholar 

  • Kowalczyk, W., Kowalczyk, W., Przybyla, M., Przybyla, M., Kozlowski, K., Kozlowski, K.: Set-point control of mobile robot with obstacle detection and avoidance using navigation function—experimental verification. J. Intell. Robot. Syst. 85(3), 539–552 (2017)

    Article  Google Scholar 

  • Kuffner, J.J., LaValle, S.M.: RRT-connect: an efficient approach to single-query path planning. In: Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Proceedings (Cat. No.00CH37065), vol. 2, pp. 995–10012 (2000). https://doi.org/10.1109/ROBOT.2000.844730

  • Kuwata, Y., Teo, J., Karaman, S., Fiore, G., Frazzoli, E., How, J.: Motion planning in complex environments using closed-loop prediction. In: AIAA Guidance, Navigation and Control Conference and Exhibit. AIAA (2008). https://doi.org/10.2514/6.2008-7166

  • LaValle, M.S.: Rapidly-exploring random trees: a new tool for path planning. Technical report, Iowa State University, Ames, IA 50011, USA (1998)

  • LaValle, S.M., Kuffner, J.J.: Randomized kinodynamic planning. Int. J. Robot. Res. 20(5), 378–400 (2001)

    Article  Google Scholar 

  • LaValle, S.M., Branicky, M.S., Lindemann, S.R.: On the relationship between classical grid search and probabilistic roadmaps. Int. J. Robot. Res. 23(7–8), 673–692 (2004)

    Article  Google Scholar 

  • Lee, J., Pippin, C., Balch, T.: Cost based planning with RRT in outdoor environments. In: 2008 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 684–689 (2008). https://doi.org/10.1109/IROS.2008.4651052

  • Leica, P., Chavez, D., Rosales, A., Roberti, F., Toibero, J.M., Carelli, R.: Strategy based on multiple objectives and null space for the formation of mobile robots and dynamic obstacle avoidance. Revista Politécnica (Quito) 33(1) (2014)

    Google Scholar 

  • Lengyel, J., Reichert, M., Donald, B.R., Greenberg, D.P.: Real-time robot motion planning using rasterizing computer graphics hardware. Comput. Graph. (New York, N.Y.) 24(4), 327–335 (1990)

    Google Scholar 

  • Lin, Y., Saripalli, S.: Sampling-based path planning for UAV collision avoidance. IEEE Trans. Intell. Transp. Syst. 18(11), 3179–3192 (2017)

    Article  Google Scholar 

  • Liu, G., Trinkle, J., Yang, Y., Luo, S.: Motion planning of planar closed chains based on structural sets. IEEE Access 8, 117203–117217 (2020)

    Article  Google Scholar 

  • Masehian, E., Amin-Naseri, M.R.: A voronoi diagram-visibility graph-potential field compound algorithm for robot path planning. J. Robot. Syst. 21(6), 275–300 (2004)

    Article  Google Scholar 

  • McMahon, T., Thomas, S., Amato, N.M.: Sampling-based motion planning with reachable volumes for high-degree-of-freedom manipulators. Int. J. Robot. Res. 37(7), 779–817 (2018)

    Article  Google Scholar 

  • Molina, C.P., Ortego, R.G., Pérez, F.M.: Perspectives on Technological Developments Applied to Robotics, pp. 59–86. Springer, London (2014). https://doi.org/10.1007/978-1-4471-5358-0_5

    Book  Google Scholar 

  • Montiel, O., Orozco-Rosas, U., Sepúlveda, R.: Path planning for mobile robots using bacterial potential field for avoiding static and dynamic obstacles. Expert Syst. Appl. 42(12), 5177–5191 (2015)

    Article  Google Scholar 

  • Noreen, I., Khan, A., Ryu, H., Doh, N.L., Habib, Z.: Optimal path planning in cluttered environment using RRT-AB. Intell. Serv. Robot. 11(1), 41–52 (2017)

    Article  Google Scholar 

  • Olmstead Muhs, J.C., Yang, J.: A geodesics-based model for obstacle avoidance. In: 2005 Digital Human Modeling for Design and Engineering Symposium. SAE International, Iowa City, IA, USA (2005). https://doi.org/10.4271/2005-01-2692

  • Oriolo, G.: Motion Planning 3 Artificial Potential Fields. Slide deck delivered as part of Autonomous and Mobile Robotics by Prof. Giuseppe Oriolo at the Universita Di Roma (2020). http://diag.uniroma1.it/oriolo/amr/slides/MotionPlanning3_Slides.pdf

  • Park, J.M., Kim, D.W., Yoon, Y.S., Kim, H.J., Yi, K.S.: Obstacle avoidance of autonomous vehicles based on model predictive control. Proc. Inst. Mech. Eng. Part D: J. Automob. Eng. 223(12), 1499–1516 (2009)

    Article  Google Scholar 

  • Porta, J.M., Jaillet, L., Bohigas, O.: Randomized path planning on manifolds based on higher-dimensional continuation. Int. J. Robot. Res. 31(2), 201–215 (2012)

    Article  Google Scholar 

  • Qin, L., Yin, Q., Zha, Y., Peng, Y.: Dynamic detection of topological information from grid-based generalized voronoi diagrams. Math. Probl. Eng. 2013, 1–11 (2013)

    MathSciNet  Google Scholar 

  • Quillen, P., Muñoz, J., Subbarao, K.: Path planning to a reachable state using minimum control effort based navigation functions. J. Astronaut. Sci. 66(4), 554–581 (2019)

    Article  Google Scholar 

  • Quinlan, S.: Real-time modification of collision-free paths. ProQuest Dissertations Publishing, Stanford (1995)

  • Quinlan, S., Khatib, O.: Elastic bands: connecting path planning and control. In: [1993] Proceedings IEEE International Conference on Robotics and Automation, pp. 802–8072 (1993). https://doi.org/10.1109/ROBOT.1993.291936

  • Qureshi, A.H., Iqbal, K.F., Qamar, S.M., Islam, F., Ayaz, Y., Muhammad, N.: Potential guided directional-RRT* for accelerated motion planning in cluttered environments. In: 2013 IEEE International Conference on Mechatronics and Automation, pp. 519–524 (2013a). https://doi.org/10.1109/ICMA.2013.6617971

  • Qureshi, A.H., Mumtaz, S., Iqbal, K.F., Ali, B., Ayaz, Y., Ahmed, F., Muhammad, M.S., Hasan, O., Kim, W.Y., Ra, M.: Adaptive potential guided directional-RRT. In: 2013 IEEE International Conference on Robotics and Biomimetics (ROBIO), pp. 1887–1892 (2013b). https://doi.org/10.1109/ROBIO.2013.6739744

  • Qureshi, A.H., Ayaz, Y.: Intelligent bidirectional rapidly-exploring random trees for optimal motion planning in complex cluttered environments. Robot. Auton. Syst. 68, 1–11 (2015)

    Article  Google Scholar 

  • Qureshi, A.H., Qureshi, A.H., Ayaz, Y., Ayaz, Y.: Potential functions based sampling heuristic for optimal path planning. Auton. Robot. 40(6), 1079–1093 (2016)

    Article  Google Scholar 

  • Radhakrishnan, S.: Observable 2D SLAM and evidential occupancy grids. Master’s thesis, Carleton University (2014)

  • Radhakrishnan, S., Gueaieb, W.: A state-of-the-art review on topology and differential geometry-based robotic path planning—part II: planning under dynamic constraints. Int. J. Intell. Robot. Appl. (2023). (Submitted: Nov. 2023)

  • Rasekhipour, Y., Khajepour, A., Chen, S., Litkouhi, B.: A potential field-based model predictive path-planning controller for autonomous road vehicles. IEEE Trans. Intell. Transp. Syst. 18(5), 1255–1267 (2017). https://doi.org/10.1109/TITS.2016.2604240

    Article  Google Scholar 

  • Rasekhipour, Y., Fadakar, I., Khajepour, A.: Autonomous driving motion planning with obstacles prioritization using lexicographic optimization. Control Eng. Pract. 77, 235–246 (2018)

    Article  Google Scholar 

  • Roy, D.: Algorithmic path planning of static robots in three dimensions using configuration space metrics. Robotica 29(2), 295–315 (2011)

    Article  Google Scholar 

  • Ryu, J.C., Ryu, J.C., Park, F.C., Park, F.C., Kim, Y.Y., Kim, Y.Y.: Mobile robot path planning algorithm by equivalent conduction heat flow topology optimization. Struct. Multidiscip. Optim. 45(5), 703–715 (2012)

    Article  MathSciNet  Google Scholar 

  • Sethian, J.A.: A fast marching level set method for monotonically advancing fronts. Proc. Natl. Acad. Sci. 93(4), 1591–1595 (1996)

    Article  MathSciNet  Google Scholar 

  • Sethian, J.A.: Fast marching methods. SIAM Rev. 41(2), 199–235 (1999)

    Article  MathSciNet  Google Scholar 

  • Sgorbissa, A.: Integrated robot planning, path following, and obstacle avoidance in two and three dimensions: wheeled robots, underwater vehicles, and multicopters. Int. J. Robot. Res. 38(7), 853–876 (2019)

    Article  Google Scholar 

  • Shvalb, N., Shoham, M., Liu, G., Trinkle, J.C.: Motion planning for a class of planar closed-chain manipulators. Int. J. Robot. Res. 26(5), 457–473 (2007)

    Article  Google Scholar 

  • Siciliano, B.: Robotics Modelling, Planning and Control, 1st edn. Advanced Textbooks in Control and Signal Processing. Springer, London (2009). https://doi.org/10.1007/978-1-84628-642-1

  • Stentz, A.: Optimal and efficient path planning for partially-known environments. In: Proceedings of the 1994 IEEE International Conference on Robotics and Automation, pp. 3310–33174 (1994). https://doi.org/10.1109/ROBOT.1994.351061

  • Suh, J., Gong, J., Oh, S.: Fast sampling-based cost-aware path planning with nonmyopic extensions using cross entropy. IEEE Trans. Robot. 33(6), 1313–1326 (2017)

    Article  Google Scholar 

  • Tanner, H.G., Kumar, A.: Towards decentralization of multi-robot navigation functions. In: Proceedings of the 2005 IEEE International Conference on Robotics and Automation, pp. 4132–4137. IEEE, Barcelona (2005)

  • Tao, S., Tan, J.: Path planning with obstacle avoidance based on normalized r-functions. J. Robot. 2018, 1–10 (2018)

    Article  Google Scholar 

  • Trinkle, J.C., Milgram, R.J.: Complete path planning for closed kinematic chains with spherical joints. Int. J. Robot. Res. 21(9), 773–789 (2002)

    Article  Google Scholar 

  • Volpe, R., Khosla, P.: Artificial potentials with elliptical isopotential contours for obstacle avoidance. In: 26th IEEE Conference on Decision and Control, vol. 26, pp. 180–185 (1987). https://doi.org/10.1109/CDC.1987.272738

  • Volpe, R., Khosla, P.: Manipulator control with superquadric artificial potential functions: theory and experiments. IEEE Trans. Syst. Man Cybern. 20(6), 1423–1436 (1990). https://doi.org/10.1109/21.61211

    Article  Google Scholar 

  • Wang, C., Mao, Y.S., Du, K.J.: Simulation on local obstacle avoidance algorithm for unmanned surface vehicle. Int. J. Simul. Model. 15(3), 460–472 (2016)

    Article  Google Scholar 

  • Wang, W., Zuo, L., Xu, X.: A learning-based multi-RRT approach for robot path planning in narrow passages. J. Intell. Robot. Syst. 90(1–2), 81–100 (2017)

    Google Scholar 

  • Wang, D., Wang, P., Zhang, X., Guo, X., Shu, Y., Tian, X.: An obstacle avoidance strategy for the wave glider based on the improved artificial potential field and collision prediction model. Ocean Eng. 206, 107356 (2020)

    Article  Google Scholar 

  • Wei, K., Ren, B.: A method on dynamic path planning for robotic manipulator autonomous obstacle avoidance based on an improved RRT algorithm. Sensors (Basel, Switz.) 18(2), 571 (2018)

    Article  Google Scholar 

  • Wu, K., Lo, C., Lin, Y., Liu, J.: 3D path planning based on nonlinear geodesic equation. In: 11th IEEE International Conference on Control Automation (ICCA), pp. 342–347 (2014). https://doi.org/10.1109/ICCA.2014.6870943

  • Wu, K.-L., Ho, T.-J., Huang, S.A., Lin, K.-H., Lin, Y.-C., Liu, J.-S.: Path planning and replanning for mobile robot navigation on 3D terrain: an approach based on geodesic. Math. Probl. Eng. 2016, 1–12 (2016)

    MathSciNet  Google Scholar 

  • Xu, B., Xu, B., Stilwell, D.J., Stilwell, D.J., Kurdila, A.J., Kurdila, A.J.: Fast path re-planning based on fast marching and level sets. J. Intell. Robot. Syst. 71(3), 303–317 (2013)

    Article  Google Scholar 

  • Yoon, Y., Shin, J., Kim, H.J., Park, Y., Sastry, S.: Model-predictive active steering and obstacle avoidance for autonomous ground vehicles. Control Eng. Pract. 17(7), 741–750 (2009)

    Article  Google Scholar 

  • Zhang, B., Liu, Y., Lu, Q., Wang, J.: A path planning strategy for searching the most reliable path in uncertain environments. Int. J. Adv. Robot. Syst. 13(5), 1–9 (2016). https://doi.org/10.1177/1729881416657751

    Article  Google Scholar 

Download references

Funding

This work was partially supported by the Natural Sciences and Engineering Research Council of Canada (NSERC). Grant RGPIN-2014-06512.

Author information

Authors and Affiliations

  1. School of Electrical Engineering and Computer Science, University of Ottawa, 800 King Edward Avenue, Ottawa, ON, K1N 6N5, Canada

    Sindhu Radhakrishnan & Wail Gueaieb

Authors
  1. Sindhu Radhakrishnan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Wail Gueaieb
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

All authors contributed to the study conception and design. Material preparation, data collection and analysis were performed by Sindhu Radhakrishnan. The first draft of the manuscript was written by Sindhu Radhakrishnan and all authors commented on previous versions of the manuscript. All authors read and approved the final manuscript.

Corresponding author

Correspondence to Wail Gueaieb.

Ethics declarations

Conflict of interest

The authors have no competing interests to declare that are relevant to the content of this article.

Ethics 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

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Radhakrishnan, S., Gueaieb, W. A state-of-the-art review on topology and differential geometry-based robotic path planning—part I: planning under static constraints. Int J Intell Robot Appl 8, 435–454 (2024). https://doi.org/10.1007/s41315-024-00330-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s41315-024-00330-5

Keywords

Search

Navigation