Top

Soft Computing

Published in:

04-06-2016 | Methodologies and Application

Multi-objective multi-robot deployment in a dynamic environment

Authors: Reza Javanmard Alitappeh, Kossar Jeddisaravi, Frederico G. Guimarães

Published in: Soft Computing | Issue 21/2017

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Finding a distribution of a group of robots in an environment is known as Deployment problem, which is one of the challenges in multi-robot systems. In real applications, the environment may change over time and thus deployment must be repeated periodically in order to redistribute the robots. In this paper, we propose a multi-objective optimization method to deploy/redeploy robots in the environment by considering two objectives for the deployment. One objective represents a good estimation of final positions, where the robots will be located, while the second objective is finding the shortest path from the robots initial location to these positions. Thus, our problem is modeled as a multi-objective optimization problem, which is approached with a multi-objective optimization evolutionary algorithm. To deal with the deployment problem, a discrete setup of locational optimization framework and Voronoi partitioning technique are employed. Simulation results on real application testify the performance of our proposed method in comparison with other methods.

previous article Finding a good initial configuration of parameters for restricted Boltzmann machine pre-training

next article A hybrid social spider optimization and genetic algorithm for minimizing molecular potential energy function

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

In order to avoid conflict between the population in the distribution function and the population in the concept of an evolutionary algorithm, we use the word “crowd” hereafter in the paper to indicate the group of people or entities in our deployment workspace.

Ahmed F, Deb K (2013) Multi-objective optimal path planning using elitist non-dominated sorting genetic algorithms. Soft Comput 17(7):1283–1299CrossRef

Alitappeh RJ, Pimenta LCA (2016) Distributed safe deployment of networked robots. Distrib Auton Robot Syst Springer Tracts Adv Robot 112:65–77CrossRef

Belta C, Kumar V (2004) Abstraction and control for groups of robots. IEEE Trans Robot 20(5):865–875CrossRef

Bhattacharya S, Ghrist R, Kumar V (2013a) Multi-robot coverage and exploration in non-euclidean metric spaces. Algorithm Found Robot X Springer Tracts Adv Robot 86:245–262CrossRef

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

Bhattacharya S, Michael N, Kumar V (2013c) Distributed coverage and exploration in unknown non-convex environments. Distrib Auton Robot Syst Springer Tracts Adv Robot 83:61–75CrossRef

Brimberg J, Drezner Z (2013) A new heuristic for solving the p-median problem in the plane. Comput Oper Res 40(1):427–437MathSciNetCrossRefMATH

Budiharto W, Santoso A, Purwanto D, Jazidie A (2011) a method for path planning strategy and navigation of service robot. Paladyn J Behav Robot 2(2):100–108

Chaimowicz L, Cowley A, Gomez-Ibanez D, Grocholsky B, Hsieh MA, Hsu H, Keller JF, Kumar V, Swaminathan R, Taylor CJ (2005) Multi-robot systems. From swarms to intelligent automata. In: Proceedings from the 2005 international workshop on multi-robot systems, vol III, Springer, Netherlands, Dordrecht, chap Deploying air-ground multi-robot teams in urban environments, pp 223–234

Cormen TH, Leiserson CE, Rivest RL, Stein C (2009) Introduction to algorithms, 3rd edn. The MIT Press, London, p 1312

Cortes J, Martinez S, Karatas T, Bullo F (2004) Coverage control for mobile sensing networks. IEEE Trans Robot Autom 20(2):243–255CrossRef

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 (2015) Clear and smooth path planning. Appl Soft Comput 32:568–579CrossRef

Deb K, Pratap A, Agarwal S, Meyarivan T (2002) A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans Evol Comput 6(2):182–197CrossRef

Dijkstra E (1959) A note on two problems in connexion with graphs. Numer Math 1:269–271MathSciNetCrossRefMATH

Durham JW, Carli R (2012) Discrete partitioning and coverage control for gossiping robots. IEEE Trans Robot 28(2):364–378CrossRef

Figueira J, Greco S, Ehrogott M (2005) Multiple criteria decision analysis: state of the art surveys series. Int Ser Oper Res Manag Sci 78:1048

Fjallstrom PO (1998) Algorithms for graph partitioning: a survey. Linkop Electron Artic Comput Inf Sci 3(10)

Fleszar K, Hindi KS (2008) An effective VNS for the capacitated p-median problem. Eur J Oper Res 191:612–622CrossRefMATH

Friedrich T, Kroeger T, Neumann F (2013) Weighted preferences in evolutionary multi-objective optimization. Int J Mach Learn Cybern 4(2):139–148CrossRef

Gabriely Y, Rimon E (2001) Spanning-tree based coverage of continuous areas by a mobile robot. Ann Math Artif Intell 31(1–4):77–98CrossRefMATH

Hartigan JA, Wong MA (1979) Algorithm AS 136: A k-means clustering algorithm. R Stat Soc Ser C (Appl Stat) 28(2):100–108MATH

Hidalgo-Paniagua A, Vega-Rodrguez M, Ferruz J, Pavn N (2015) Solving the multi-objective path planning problem in mobile robotics with a firefly-based approach. Soft Comput 1–16

Holder A, Lim G, Reese J (2007) The relationship between discrete vector quantization and the p-median problem. Technical report

Huang HC (2013) Intelligence motion control for omnidirectional mobile robots using ant colony optimization. Appl Artif Intell Int J 27(3):151–169CrossRef

Ioannidisa K, Sirakoulisa GC, Andreadis I (2011) A path planning method based on cellular automata for cooperative robots. Appl Artif Intell Int J 25(8):721–745CrossRef

Jeddisaravi K, Alitappeh RJ, Pimenta LCA, Guimarães FG (2016) Multi-objective approach for robot motion planning in search tasks. Appl Intell 1–17. doi:10.1007/s10489-015-0754-y

Jensen M (2003) Reducing the run-time complexity of multiobjective EAs: the NSGA-II and other algorithms. IEEE Trans Evolut Comput 7(5):503–515CrossRef

Ji M, Egerstedt M (2007) Distributed coordination control of multiagent systems while preserving connectedness. IEEE Trans Robot 23(4):693–703CrossRef

King R, Rughooputh H (2003) Elitist multiobjective evolutionary algorithm for environmental/economic dispatch. In: Evolutionary computation, 2003. CEC ’03. The 2003 Congress on, vol 2, IEEE, pp 1108–1114

Klein PN (2005) Multiple-source shortest paths in planar graphs. In: Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms (SODA ’05), pp 146–155

Knowles J, Corne D (1999) The pareto archived evolution strategy: A new baseline algorithm for pareto multiobjective optimisation. In: Proceedings of the 1999 congress on evolutionary computation, 1999 CEC 99, vol 1, pp 98–105

Landa-Torres I, Del Ser J, Salcedo-Sanz S, Gil-Lopez S, Ja Portilla-Figueras, Alonso-Garrido O (2012) A comparative study of two hybrid grouping evolutionary techniques for the capacitated P-median problem. Comput Oper Res 39(9):2214–2222MathSciNetCrossRefMATH

Lim GJ, Reese J, Holder A (2009) Fast and robust techniques for the euclidean p-median problem with uniform weights. Comput Ind Eng 57:896–905CrossRef

Liu M, Zeng W (2010) Reducing the run-time complexity of NSGA-II for bi-objective optimization problem. In: Proceedings of IEEE international conference on intelligent computing and intelligent systems, IEEE, vol 2, pp 546–549

Lloyd S (1982) Least squares quantization in PCM. IEEE Trans Inf Theory 28(2):129–137MathSciNetCrossRefMATH

Ma CC, Ayala-Ramirez V, Hernandez-Belmonte UH (2015) Mobile robot path planning using artificial bee colony and evolutionary programming. Appl Soft Comput 30:319–328CrossRef

Marler R, Arora J (2004) Survey of multi-objective optimization methods for engineering. Struct Multidiscip Optim 26(6):369–395MathSciNetCrossRefMATH

Nowzari C, Cortés J (2012) Self-triggered coordination of robotic networks for optimal deployment. Automatica 48(6):1077–1087MathSciNetCrossRefMATH

Ortiza JAH, Rodríguez-Vázqueza K, Castañedab MAP, Cosíoa FA (2013) Autonomous robot navigation based on the evolutionary multi-objective optimization of potential fields. Eng Optim 45(1):19–43MathSciNetCrossRef

Parker LE (2002) Distributed algorithms for multi-robot observation of multiple moving targets. Auton Robots 12(3):231–255CrossRefMATH

Pimenta LCA, Kumar V, Mesquita RC, Pereira GAS (2008) Sensing and coverage for a network of heterogeneous robots. In: Proceedings of IEEE conference on decision and control (CDC), vol 2, pp 3947–3952

Poduri S, Sukhatme GS (2004) Constrained coverage for mobile sensor networks. In: Proceedings of IEEE international conference on robotics and automation (ICRA), IEEE, pp 165–171

Reese J (2006) Solution methods for the p-median problem: an annotated bibliography. Networks 48(3):125–142MathSciNetCrossRefMATH

Reif J, Wang H (1999) Social potential fields: a distributed behavioral control for autonomous robots. Robot Auton Syst 27(3):171–194CrossRef

Resende MGC, Werneck RF (2004) A hybrid heuristic for the p-median problem. J Heuristics 10(1):59–88CrossRefMATH

Roy B (1968) Classement et choix en présence de points de vue multiples (la méthode ELECTRE). La Revue d’Informatique et de Recherche Opérationelle (RIRO) 8:57–75

Senne ELF, LaN Lorena, Ma Pereira (2005) A branch-and-price approach to p-median location problems. Comput Oper Res 32:1655–1664MathSciNetCrossRef

Senthilkumar K, Bharadwaj K (2012) Multi-robot exploration and terrain coverage in an unknown environment. Robot Auton Syst 60(1):123–132CrossRef

Stergiopoulos Y, Tzes A (2011) Coverage-oriented coordination of mobile heterogeneous networks. In: Proceedings of mediterranian control & automation (MED) pp 175–180

Tzes A, Stergiopoulos Y (2010) Convex Voronoi-inspired space partitioning for heterogeneous networks: a coverage-oriented approach. IET Control Theory Appl 4(12):2802–2812

Veloso M, Biswas J, Coltin B, Rosenthal S, Brandao S, Mericli T, Ventura R (2012) Symbiotic-autonomous service robots for userrequested tasks in a multi-floor building. In: Proceedings of the cognitive assistive systems workshop, IROS 2012

Wanga X, Shia Y, Dingb D, Gua X (2015) Double global optimum genetic algorithm particle swarm optimization based welding robot path planning. J Eng Opt 48:1–18MathSciNet

Xue Y, Liu H (2010) Optimal path planning for service robot in indoor environment. In: Proceedings of international conference on intelligent computation technology and automation (ICICTA), IEEE, vol 2, pp 850–853

Yaghini M, Karimi M, Rahbar M (2013) A hybrid metaheuristic approach for the capacitated p-median problem. Appl Soft Comput 13(9):3922–3930CrossRef

Yun S, Rus D (2013) Distributed coverage with mobile robots on a graph: locational optimization and equal-mass partitioning. Robotica 32(02):257–277CrossRef

Zhang Y, Gong D, Zhang J (2012) Robot path planning in uncertain environment using multi-objective particle swarm optimization. Neurocomputing 103:172–185CrossRef

Zitzler E, Laumanns M, Thiele L (2002) SPEA2: improving the strength Pareto evolutionary algorithm. In: Proceedings of the evolutionary methods for design, optimisation, and control, pp 95–100

Title: Multi-objective multi-robot deployment in a dynamic environment
Authors: Reza Javanmard Alitappeh
Kossar Jeddisaravi
Frederico G. Guimarães
Publication date: 04-06-2016
Publisher: Springer Berlin Heidelberg
Published in: Soft Computing / Issue 21/2017
Print ISSN: 1432-7643
Electronic ISSN: 1433-7479
DOI: https://doi.org/10.1007/s00500-016-2207-x

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 21/2017

Regression line shifting mechanism for analyzing evolutionary optimization algorithms

Notes on divisible MV-algebras

An ant-based QoS-aware routing protocol for heterogeneous wireless sensor networks

Evolved FCM framework for working condition classification in furnace system

Graphical visualization of FFLS to explain the existence of solution and weak solution in circuit analysis

Finding a good initial configuration of parameters for restricted Boltzmann machine pre-training

Premium Partner