Skip to main content
Erschienen in: Soft Computing 11/2017

21.12.2015 | Methodologies and Application

Solving robot path planning problem by using a new elitist multi-objective IWD algorithm based on coefficient of variation

verfasst von: Soheila Salmanpour, Hesamoddin Monfared, Hesam Omranpour

Erschienen in: Soft Computing | Ausgabe 11/2017

Einloggen

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

In this paper, we want to solve multi-objective robot path planning problem. A new elitist multi-objective approach is proposed to determine Pareto front based on coefficient of variation. Intelligent water drops (IWD) algorithm is generalized by this approach and as a new multi-objective IWD algorithm. We call our new algorithm CV-based MO-IWD. It tried to optimize two objectives: length and safety of the path. In the CV-based MO-IWD, we want to discover solutions as close to optimal Pareto solutions as possible and find solutions as diverse as possible in the obtained Pareto front. In this way, coefficient of variation of Pareto front is determined in each objective. Then, appropriate number of heuristic operations (local search in this paper) is calculated and applied for each solution. Implementation results and comparisons with NSGA_II algorithm show the ability of the proposed approach to achieve a near optimal Pareto front with a good diversity, while the number of fitness function calls does not increase. This method is superior because of suitable distribution of heuristic operations.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Literatur
Zurück zum Zitat Ahmed F, Deb K (2011) Multi-objective path planning using spline representation. In: Proceedings of the IEEE international conference on robotics and biomimetics (IEEE-ROBIO), Piscatway. pp 1047–1052 Ahmed F, Deb K (2011) Multi-objective path planning using spline representation. In: Proceedings of the IEEE international conference on robotics and biomimetics (IEEE-ROBIO), Piscatway. pp 1047–1052
Zurück zum Zitat Ahmed F, Deb K (2013) Multi-objective optimal path planning using elitist non-dominated sorting genetic algorithms. Soft Comput 17(7):1283–1299CrossRef Ahmed F, Deb K (2013) Multi-objective optimal path planning using elitist non-dominated sorting genetic algorithms. Soft Comput 17(7):1283–1299CrossRef
Zurück zum Zitat Alaya C Solnon, Ghedira K (2007) Ant colony optimization for multi-objective optimization problems. In: 19th IEEE international conference on tools with artificial intelligence (ICTAI), vol 1, pp 450-457 Alaya C Solnon, Ghedira K (2007) Ant colony optimization for multi-objective optimization problems. In: 19th IEEE international conference on tools with artificial intelligence (ICTAI), vol 1, pp 450-457
Zurück zum Zitat Angus D, Woodward C (2009) Multiple objective ant colony optimisation. Swarm Intell 3(1):69–85CrossRef Angus D, Woodward C (2009) Multiple objective ant colony optimisation. Swarm Intell 3(1):69–85CrossRef
Zurück zum Zitat Barán B, Schaerer M (2003) A multiobjective ant colony system for vehicle routing problem with time windows. In: Proceedings of the 21st IASTED International Conference, Applied informatics, Innsbruck, Austria, pp 97–102 Barán B, Schaerer M (2003) A multiobjective ant colony system for vehicle routing problem with time windows. In: Proceedings of the 21st IASTED International Conference, Applied informatics, Innsbruck, Austria, pp 97–102
Zurück zum Zitat Botzheim J, Toda Y, Kubota N (2012) Bacterial memetic algorithm for offline path planning of mobile robots. Memet Comput 4(1):73–86CrossRef Botzheim J, Toda Y, Kubota N (2012) Bacterial memetic algorithm for offline path planning of mobile robots. Memet Comput 4(1):73–86CrossRef
Zurück zum Zitat Castilho O, Trujilo L (2005) Multiple objective optimization genetic algorithms for path planning in autonomous mobile robots. Int J Comput Syst Signal 6(1):48–63 Castilho O, Trujilo L (2005) Multiple objective optimization genetic algorithms for path planning in autonomous mobile robots. Int J Comput Syst Signal 6(1):48–63
Zurück zum Zitat Dakulović M, Petrović I (2011) Two-way D* algorithm for path planning and replanning. Robot Auton Syst 59(5):329–342CrossRef Dakulović M, Petrović I (2011) Two-way D* algorithm for path planning and replanning. Robot Auton Syst 59(5):329–342CrossRef
Zurück zum Zitat Davoodi M, Panahi F, Mohades A, Hashemi SN (2013) Multi-objective path planning in discrete space. Appl Soft Comput 13(1):709–720CrossRef Davoodi M, Panahi F, Mohades A, Hashemi SN (2013) Multi-objective path planning in discrete space. Appl Soft Comput 13(1):709–720CrossRef
Zurück zum Zitat Deb K (2001) Multi-objective optimization using evolutionary algorithms. Wiley, HobokenMATH Deb K (2001) Multi-objective optimization using evolutionary algorithms. Wiley, HobokenMATH
Zurück zum Zitat Deb K, Agrawal S, Pratap A, Meyarivan T (2000) A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II. In: Lecture notes in computer science, vol 1917, pp 849–858 Deb K, Agrawal S, Pratap A, Meyarivan T (2000) A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II. In: Lecture notes in computer science, vol 1917, pp 849–858
Zurück zum Zitat Doerner K, Gutjahr WJ, Hartl RF, Strauss C, Stummer C (2004) Pareto ant colony optimization: a metaheuristic approach to multiobjective portfolio selection. Ann Oper Res 131(1–4):79–99MathSciNetCrossRefMATH Doerner K, Gutjahr WJ, Hartl RF, Strauss C, Stummer C (2004) Pareto ant colony optimization: a metaheuristic approach to multiobjective portfolio selection. Ann Oper Res 131(1–4):79–99MathSciNetCrossRefMATH
Zurück zum Zitat Doerner KF, Hartl RF, Reimann M (2003) Are CompetAnts more competent for problem solving? The case of a multiple objective transportation problem. Cent Eur J Oper Res Econ 11(2):115–141MATH Doerner KF, Hartl RF, Reimann M (2003) Are CompetAnts more competent for problem solving? The case of a multiple objective transportation problem. Cent Eur J Oper Res Econ 11(2):115–141MATH
Zurück zum Zitat Ferariu L, Cimpanu C (2014) Multiobjective hybrid evolutionary path planning with adaptive pareto ranking of variable-length chromosomes. In: 2014 IEEE 12th international symposium on applied machine intelligence and informatics (SAMI), pp 73–78 Ferariu L, Cimpanu C (2014) Multiobjective hybrid evolutionary path planning with adaptive pareto ranking of variable-length chromosomes. In: 2014 IEEE 12th international symposium on applied machine intelligence and informatics (SAMI), pp 73–78
Zurück zum Zitat Fonseca CM, Fleming PJ (1993) Genetic algorithms for multiobjective optimization: Formulation, discussion and generalization. In: Proceedings of the fifth international conference on genetic algorithms, vol 423, pp 416–423 Fonseca CM, Fleming PJ (1993) Genetic algorithms for multiobjective optimization: Formulation, discussion and generalization. In: Proceedings of the fifth international conference on genetic algorithms, vol 423, pp 416–423
Zurück zum Zitat Gong D, Lu L, Li M (2009) Robot path planning in uncertain environments based on particle swarm optimization. In: IEEE congress on evolutionary computation, 2009 (CEC’09), pp 2127–2134 Gong D, Lu L, Li M (2009) Robot path planning in uncertain environments based on particle swarm optimization. In: IEEE congress on evolutionary computation, 2009 (CEC’09), pp 2127–2134
Zurück zum Zitat Gong DW, Zhang JH, Zhang Y (2011) Multi-objective particle swarm optimization for robot path planning in environment with danger sources. J Comput 6(8):1554–1561CrossRef Gong DW, Zhang JH, Zhang Y (2011) Multi-objective particle swarm optimization for robot path planning in environment with danger sources. J Comput 6(8):1554–1561CrossRef
Zurück zum Zitat López-Ibánez M, Stützle T (2011) The automatic design of multi-objective ant colony optimization algorithms. IEEE Trans Evol Comput 16:861–875CrossRef López-Ibánez M, Stützle T (2011) The automatic design of multi-objective ant colony optimization algorithms. IEEE Trans Evol Comput 16:861–875CrossRef
Zurück zum Zitat Lu Y, Huo X, Arslan O, Tsiotras P (2011) Incremental multi-scale search algorithm for dynamic path planning with low worst-case complexity. IEEE Trans Syst Man Cybern B Cybern 41(6):1556–1570CrossRef Lu Y, Huo X, Arslan O, Tsiotras P (2011) Incremental multi-scale search algorithm for dynamic path planning with low worst-case complexity. IEEE Trans Syst Man Cybern B Cybern 41(6):1556–1570CrossRef
Zurück zum Zitat Lu Y, Huo X, Tsiotras P (2010) Beamlet-like data processing for accelerated path-planning using multiscale information of the environment. In: 49th IEEE conference on decision and control (CDC), 2010, pp 3808–3813 Lu Y, Huo X, Tsiotras P (2010) Beamlet-like data processing for accelerated path-planning using multiscale information of the environment. In: 49th IEEE conference on decision and control (CDC), 2010, pp 3808–3813
Zurück zum Zitat Masehian E, Sedighizadeh D (2007) Classic and heuristic approaches in robot motion planning—a chronological review. World Acad Sci Eng Technol 29(1):101–106 Masehian E, Sedighizadeh D (2007) Classic and heuristic approaches in robot motion planning—a chronological review. World Acad Sci Eng Technol 29(1):101–106
Zurück zum Zitat Mohanty PK, Kumar S, Parhi DR (2015) A new ecologically inspired algorithm for mobile robot navigation. In: Proceedings of the 3rd international conference on frontiers of intelligent computing: theory and applications (FICTA) 2014. Springer International Publishing, pp 755–762 Mohanty PK, Kumar S, Parhi DR (2015) A new ecologically inspired algorithm for mobile robot navigation. In: Proceedings of the 3rd international conference on frontiers of intelligent computing: theory and applications (FICTA) 2014. Springer International Publishing, pp 755–762
Zurück zum Zitat Osyczka A, Kundu S (1995) A new method to solve generalized multicriteria optimization problems using the simple genetic algorithm. Struct Optim 10(2):94–99CrossRef Osyczka A, Kundu S (1995) A new method to solve generalized multicriteria optimization problems using the simple genetic algorithm. Struct Optim 10(2):94–99CrossRef
Zurück zum Zitat Salmanpour S, Motameni H (2014) Optimal path planning for mobile robot using Intelligent Water Drops algorithm. J Intell Fuzzy Syst 27(3):1519–1531 Salmanpour S, Motameni H (2014) Optimal path planning for mobile robot using Intelligent Water Drops algorithm. J Intell Fuzzy Syst 27(3):1519–1531
Zurück zum Zitat Shah-Hosseini H (2012) An approach to continuous optimization by the intelligent water drops algorithm. Proc Soc Behav Sci 32(224–229):2012 Shah-Hosseini H (2012) An approach to continuous optimization by the intelligent water drops algorithm. Proc Soc Behav Sci 32(224–229):2012
Zurück zum Zitat Shah-Hosseini H (2009) The intelligent water drops algorithm: a nature-inspired swarm-based optimization algorithm. Int J Bio-Inspired Comput 1(1):71–79CrossRef Shah-Hosseini H (2009) The intelligent water drops algorithm: a nature-inspired swarm-based optimization algorithm. Int J Bio-Inspired Comput 1(1):71–79CrossRef
Zurück zum Zitat Srinivas N, Deb K (1994) Muiltiobjective optimization using nondominated sorting in genetic algorithms. Evol Comput 2(3):221–248CrossRef Srinivas N, Deb K (1994) Muiltiobjective optimization using nondominated sorting in genetic algorithms. Evol Comput 2(3):221–248CrossRef
Zurück zum Zitat Stentz, (1995) The focussed D* algorithm for real-time replanning. In: International joint conference on artificial intelligence, vol 14, pp 1652–1659 Stentz, (1995) The focussed D* algorithm for real-time replanning. In: International joint conference on artificial intelligence, vol 14, pp 1652–1659
Zurück zum Zitat Sugihara K (1997) A case study on tuning of genetic algorithms by using performance evaluation based on experimental design. In: Proceedings of the 1997 joint conference on information sciences Sugihara K (1997) A case study on tuning of genetic algorithms by using performance evaluation based on experimental design. In: Proceedings of the 1997 joint conference on information sciences
Zurück zum Zitat Tuncer, Yildirim M (2012) Dynamic path planning of mobile robots with improved genetic algorithm. Comput Electr Eng 38(6):1564–1572 Tuncer, Yildirim M (2012) Dynamic path planning of mobile robots with improved genetic algorithm. Comput Electr Eng 38(6):1564–1572
Zurück zum Zitat Zhangqi W, Xiaoguang Z, Qingyao H (2011) Mobile robot path planning based on parameter optimization ant colony algorithm. Proc Eng 15:2738–2741CrossRef Zhangqi W, Xiaoguang Z, Qingyao H (2011) Mobile robot path planning based on parameter optimization ant colony algorithm. Proc Eng 15:2738–2741CrossRef
Zurück zum Zitat Zitzler E, Thiele L (1998) An evolutionary algorithm for multiobjective optimization: The strength pareto approach. Computer Engineering and Networks Laboratory (TIK), Swiss Federal Institute of Technology Zürich (ETH) Zitzler E, Thiele L (1998) An evolutionary algorithm for multiobjective optimization: The strength pareto approach. Computer Engineering and Networks Laboratory (TIK), Swiss Federal Institute of Technology Zürich (ETH)
Metadaten
Titel
Solving robot path planning problem by using a new elitist multi-objective IWD algorithm based on coefficient of variation
verfasst von
Soheila Salmanpour
Hesamoddin Monfared
Hesam Omranpour
Publikationsdatum
21.12.2015
Verlag
Springer Berlin Heidelberg
Erschienen in
Soft Computing / Ausgabe 11/2017
Print ISSN: 1432-7643
Elektronische ISSN: 1433-7479
DOI
https://doi.org/10.1007/s00500-015-1991-z

Weitere Artikel der Ausgabe 11/2017

Soft Computing 11/2017 Zur Ausgabe