Skip to main content
SpringerLink
Log in

A numerical method for solving shortest path problems

  • Published:
Calcolo Aims and scope Submit manuscript

Abstract

Chebyshev pseudo-spectral method is one of the most efficient methods for solving continuous-time optimization problems. In this paper, we utilize this method to solve the general form of shortest path problem. Here, the main problem is converted into a nonlinear programming problem and by solving of which, we obtain an approximate shortest path. The feasibility of the nonlinear programming problem and the convergence of the method are given. Finally, some numerical examples are considered to show the efficiency of the presented method over the other methods.

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

Access this article

Log in via an institution

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

Similar content being viewed by others

References

  1. Borzabadi, A.H., Kamyad, A.V., Farahi, M.H., Mehne, H.H.: Solving some optimal path planning problems using an approach based on measure theory. Appl. Math. Comput. 170, 1418–1435 (2005)

    MathSciNet  MATH  Google Scholar 

  2. Canuto, C., Hussaini, Y., Quarteroni, A., Zang, T.A.: Spectral Methods in Fluid Dynamics (Scientific Computation). Springer, New York (1987)

    MATH  Google Scholar 

  3. Clenshaw, C.W., Curtis, A.R.: A method for numerical integration on an automatic computer. Numer. Math. 2, 197–205 (1960)

    Article  MathSciNet  MATH  Google Scholar 

  4. Fahroo, F., Ross, I.M.: Costate estimation by a legendre pseudospectral method. J. Guid. Control Dyn. 24(2), 270–277 (2001)

    Article  Google Scholar 

  5. Fahroo, F., Ross, I.M.: Direct trajectory optimization by a Chebyshev pseudospectral method. J. Guid. Control Dyn. 25(1), 160–166 (2002)

    Article  Google Scholar 

  6. Freud, G.: Orthogonal Polynomials. Pregamon Press, Elmsford (1971)

    MATH  Google Scholar 

  7. Ghaznavi, M., Noori Skandari, M.H.: An efficient pseudo-spectral method for nonsmooth dynamical systems. Iran. J. Sci. Technol. Trans. A Sci. (2016). https://doi.org/10.1007/s40995-016-0040-9

  8. Gong, Q., Kang, W., Ross, I.M.: A pseudospectral method for the optimal control of constrained feedback linearizable systems. IEEE Trans. Autom. Control 51(7), 1115–1129 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  9. Gong, Q., Ross, I.M., Kang, W., Fahroo, F.: Connections between the covector mapping theorem and convergence of pseudospectral methods for optimal control. Comput. Optim. Appl. 41(3), 307–335 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  10. Latombe, J.C.: Robot Motion Planning. Kluwer Academic, Norwell, MA (1991)

    Book  MATH  Google Scholar 

  11. Lu, Y., Yi, S., Liu, Y., Ji, Y.: A novel path planning method for biomimetic robot based on deep learning. Assem. Autom. 36(2), 186–191 (2016)

    Article  Google Scholar 

  12. Ma, Y., Zamirian, M., Yang, Y., Xu, Y., Zhang, J.: Path planning for mobile objects in four-dimension based on particle swarm optimization method with penalty function. Math. Probl. Eng. 2013, 1–9 (2013)

    Google Scholar 

  13. Mortezaee, M., Nazemi, A.: A wavelet collocation scheme for solving some optimal path planning problems. ANZIAM 57, 461–481 (2015)

    MathSciNet  MATH  Google Scholar 

  14. Noori Skandari, M.H., Ghaznavi, M.: Chebyshev pseudo-spectral method for Bratu’s problem. Iran. J. Sci. Technol. Trans. A Sci. 41, 913–921 (2017)

    Article  MathSciNet  Google Scholar 

  15. Noori Skandari, M.H., Kamyad, A.V., Effati, S.: Generalized Euler–Lagrange equation for nonsmooth calculus of variations. Nonlinear Dyn. 75(1–2), 85–100 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  16. Noori Skandari, M.H., Kamyad, A.V., Effati, S.: Smoothing approach for a class of nonsmooth optimal control problems. Appl. Math. Model. 40(2), 886–903 (2016)

    Article  MathSciNet  Google Scholar 

  17. O’Hara, H., Smith, F.J.: Error estimation in the Clenshaw–Curtis quadrature formula. Comput. J. 11, 213–219 (1968)

    Article  MathSciNet  MATH  Google Scholar 

  18. Otte, M., Correll, N.: C-FOREST: parallel shortest path planning with superlinear speedup. IEEE Robot. Autom. Soc. 29(3), 798–806 (2013)

    Google Scholar 

  19. Polak, E.: Optimization: Algorithms and Consistent Approximations. Springer, Heidelberg (1997)

    Book  MATH  Google Scholar 

  20. Shen, J., Tang, T., Wang, L.L.: Spectral Methods: Algorithm, Analysis and Applications. Springer, Berlin (2011)

    Book  MATH  Google Scholar 

  21. Tohidi, E., Samadi, O.R.N.: Legendre spectral collocation method for approximating the solution of shortest path problems. Syst. Sci. Control Eng. 3, 62–68 (2015)

    Article  Google Scholar 

  22. Trefethen, L.N.: Spectral Methods in MATLAB. Society for Industrial and Applied Mathematics, Philadelphia (2000)

    Book  MATH  Google Scholar 

  23. Wang, Y., Lane, D.M., Falconer, G.J.: Two novel approaches for unmanned under water vehicle path planning: constrained optimisation and semi-infinite constrained optimisation. Robotica 18, 123–142 (2000)

    Article  Google Scholar 

  24. Zamirian, M., Farahi, M.H., Nazemi, A.R.: An applicable method for solving the shortest path problems. Appl. Math. Comput. 190, 1479–1486 (2007)

    MathSciNet  MATH  Google Scholar 

  25. Zamirian, M., Kamyad, A.V., Farahi, M.H.: A novel algorithm for solving optimal path planning problems based on parametrization method and fuzzy aggregation. Phys. Lett. A 373(38), 3439–3449 (2009)

    Article  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Faculty of Mathematical Sciences, Shahrood University of Technology, Shahrood, Iran

    M. H. Noori Skandari & M. Ghaznavi

Authors
  1. M. H. Noori Skandari
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. M. Ghaznavi
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to M. H. Noori Skandari.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Noori Skandari, M.H., Ghaznavi, M. A numerical method for solving shortest path problems. Calcolo 55, 14 (2018). https://doi.org/10.1007/s10092-018-0256-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s10092-018-0256-5

Keywords

Mathematics Subject Classification

Search

Navigation