Multi-agent Path Planning Problem Under a Multi-objective Optimization Framework | SpringerLink
Skip to main content
Springer Nature Link
Log in

Multi-agent Path Planning Problem Under a Multi-objective Optimization Framework

  • Conference paper
Distributed Computing and Artificial Intelligence, Special Sessions, 17th International Conference (DCAI 2020)

Part of the book series: Advances in Intelligent Systems and Computing ((AISC,volume 1242))

  • 916 Accesses

Abstract

In this study, a mixed-integer programming formulation is developed for a team of homogeneous sensing agents under a bi-objective optimization framework to solve a discrete open-loop centralized multi-agent search and rescue path planning problem. The first objective represents the maximization of probability of target detection to ensure the success of mission planning and the second objective represents minimization of the cumulative path length of all the agents to ensure resource utilization and ensure adequate area coverage. A two-phase fuzzy programming technique is used to find the Pareto optimal solution. Numerical experiments are conducted with CPLEX to evaluate the effectiveness of the solution procedure with varying number of agents, and the impact of the size of a grid-based rectangular map with a sparsely distributed non-cooperative finite number of stationary targets.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 11439
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 14299
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Ali, S., Saha, S., Kaviraj, A.: Fermented mulberry leaf meal as fishmeal replacer in the formulation of feed for carp Labeo rohita and catfish Heteropneustes fossilis–optimization by mathematical programming. Trop. Anim. Health Produ. 52(2), 1–11 (2019)

    Google Scholar 

  2. Berger, J., Lo, N.: An innovative multi-agent search-and-rescue path planning approach. Comput. Oper. Res. 53, 24–31 (2015)

    Article  MathSciNet  Google Scholar 

  3. Berger, J., Lo, N., Barkaoui, M.: Static target search path planning optimization with heterogeneous agents. Ann. Oper. Res. 244(2), 295–312 (2016)

    Article  MathSciNet  Google Scholar 

  4. Chen, L., Peng, J., Zhang, B.: Uncertain goal programming models for bicriteria solid transportation problem. Appl. Soft Comput. 51, 49–59 (2017)

    Article  Google Scholar 

  5. Chen, L.H., Chen, H.H.: A two-phase fuzzy approach for solving multi-level decision-making problems. Knowl.-Based Syst. 76, 189–199 (2015)

    Article  Google Scholar 

  6. Chung, C.K., Chen, H.M., Chang, C.T., Huang, H.L.: On fuzzy multiple objective linear programming problems. Expert Syst. Appl. 114, 552–562 (2018)

    Article  Google Scholar 

  7. Danancier, K., Ruvio, D., Sung, I., Nielsen, P.: Comparison of path planning algorithms for an unmanned aerial vehicle deployment under threats. IFAC-PapersOnLine 52(13), 1978–1983 (2019)

    Article  Google Scholar 

  8. Eagle, J.N.: The optimal search for a moving target when the search path is constrained. Oper. Res. 32(5), 1107–1115 (1984)

    Article  MathSciNet  Google Scholar 

  9. Fajardo, D., Waller, S.T.: Dynamic Traveling Salesman Problem in stochastic-state network setting for search-and-rescue application. Transp. Res. Rec. 2283(1), 122–130 (2012)

    Article  Google Scholar 

  10. Guu, S.M., Yu, J., Wu, Y.K.: A two-phase approach to finding a better managerial solution for systems with addition-min fuzzy relational inequalities. IEEE Trans. Fuzzy Syst. 26(4), 2251–2260 (2017)

    Article  Google Scholar 

  11. Guua, S.M., Wu, Y.K.: Two-phase approach for solving the fuzzy linear programming problems. Fuzzy Sets Syst. 107(2), 191–195 (1999)

    Article  MathSciNet  Google Scholar 

  12. Hollinger, G., Kehagias, A., Singh, S.: GSST: anytime guaranteed search. Auton. Robots 29(1), 99–118 (2010)

    Article  Google Scholar 

  13. Janardhanan, M.N., Li, Z., Bocewicz, G., Banaszak, Z., Nielsen, P.: Metaheuristic algorithms for balancing robotic assembly lines with sequence-dependent robot setup times. Appl. Math. Model. 65, 256–270 (2019)

    Article  MathSciNet  Google Scholar 

  14. Lanillos, P., Yañez-Zuluaga, J., Ruz, J.J., Besada-Portas, E.: A Bayesian approach for constrained multi-agent minimum time search in uncertain dynamic domains. In: Proceedings of the 15th Annual Conference on Genetic and Evolutionary Computation, pp. 391–398, July 2013

    Google Scholar 

  15. Lee, E.S., Li, R.J.: Fuzzy multiple objective programming and compromise programming with Pareto optimum. Fuzzy Sets Syst. 53(3), 275–288 (1993)

    Article  MathSciNet  Google Scholar 

  16. Liang, T.F.: Fuzzy multi-objective project management decisions using two-phase fuzzy goal programming approach. Comput. Ind. Eng. 57(4), 1407–1416 (2009)

    Article  Google Scholar 

  17. Liu, X., Gong, D.: A comparative study of A-star algorithms for search and rescue in perfect maze. In: 2011 International Conference on Electric Information and Control Engineering, pp. 24–27. IEEE, April 2011

    Google Scholar 

  18. Lo, N., Berger, J., Noel, M.: Toward optimizing static target search path planning. In: 2012 IEEE Symposium on Computational Intelligence for Security and Defence Applications, pp. 1–7. IEEE, July 2012

    Google Scholar 

  19. Miettinen, K.: Nonlinear Multiobjective Optimization. Kluwer, Boston (1999)

    Google Scholar 

  20. Moon, I., Jeong, Y.J., Saha, S.: Fuzzy bi-objective production-distribution planning problem under the carbon emission constraint. Sustainability 8(8), 798 (2016)

    Article  Google Scholar 

  21. Nielsen, L.D., Sung, I., Nielsen, P.: Convex decomposition for a coverage path planning for autonomous vehicles: interior extension of edges. Sensors 19(19), 4165 (2019)

    Article  Google Scholar 

  22. Park, Y., Nielsen, P., Moon, I.: Unmanned aerial vehicle set covering problem considering fixed-radius coverage constraint. Comput. Oper. Res. 119, 104936 (2020)

    Article  MathSciNet  Google Scholar 

  23. Perez-Carabaza, S., Besada-Portas, E., Lopez-Orozco, J.A., Jesus, M.: Ant colony optimization for multi-UAV minimum time search in uncertain domains. Appl. Soft Comput. 62, 789–806 (2018)

    Article  Google Scholar 

  24. Pérez-Carabaza, S., Scherer, J., Rinner, B., López-Orozco, J.A., Besada-Portas, E.: UAV trajectory optimization for Minimum Time Search with communication constraints and collision avoidance. Eng. Appl. Artif. Intell. 85, 357–371 (2019)

    Article  Google Scholar 

  25. Raap, M., Meyer-Nieberg, S., Pickl, S., Zsifkovits, M.: Aerial vehicle search-path optimization: a novel method for emergency operations. J. Optim. Theory Appl. 172(3), 965–983 (2017)

    Article  MathSciNet  Google Scholar 

  26. Sakawa, M., Yano, H., Nishizaki, I., Nishizaki, I.: Linear and Multiobjective Programming with Fuzzy Stochastic Extensions. Springer, Cham (2013)

    Book  Google Scholar 

  27. San Juan, V., Santos, M., Andújar, J.M.: Intelligent UAV map generation and discrete path planning for search and rescue operations. Complexity 6879419, 17 p. (2018)

    Google Scholar 

  28. Sanyal, S.N., Nielsen, I., Saha, S.: Multi-objective human resource allocation approach for sustainable traffic management. Int. J. Environ. Res. Public Health 17(7), 2470 (2020)

    Article  Google Scholar 

  29. Sitek, P., Wikarek, P.: A hybrid method for modeling and solving constrained search problems. FedCSIS 2013, 385–392 (2013)

    Google Scholar 

  30. Sitek, P., Wikarek, J.: A multi-level approach to ubiquitous modeling and solving constraints in combinatorial optimization problems in production and distribution. Appl. Intell. 48(5), 1344–1367 (2018)

    Google Scholar 

  31. Sitek, P., Wikarek, J.: Capacitated Vehicle Routing Problem with Pick-up and Alternative Delivery (CVRPPAD) - model and implementation using hybrid approach. Ann. Oper. Res. 273(1–2), 257–277 (2019)

    Article  MathSciNet  Google Scholar 

  32. Stone, L.D.: Theory of Optimal Search. Elsevier (1976)

    Google Scholar 

  33. Thibbotuwawa, A., Nielsen, P., Zbigniew, B., Bocewicz, G.: Energy consumption in unmanned aerial vehicles: a review of energy consumption models and their relation to the UAV routing. Adv. Intell. Syst. Comput. 853, 173–184 (2019)

    Article  Google Scholar 

  34. Thunberg, J., Ögren, P.: A mixed integer linear programming approach to pursuit evasion problems with optional connectivity constraints. Auton. Robots 31(4), 333 (2011)

    Article  Google Scholar 

  35. Trummel, K.E., Weisinger, J.R.: The complexity of the optimal searcher path problem. Oper. Res. 34(2), 324–327 (1986)

    Article  MathSciNet  Google Scholar 

  36. Wu, Y.K., Liu, C.C., Lur, Y.Y.: Pareto-optimal solution for multiple objective linear programming problems with fuzzy goals. Fuzzy Optim. Decis. Making 14(1), 43–55 (2015)

    Article  MathSciNet  Google Scholar 

  37. Xiong, C., Chen, D., Lu, D., Zeng, Z., Lian, L.: Path planning of multiple autonomous marine vehicles for adaptive sampling using Voronoi-based ant colony optimization. Robot. Auton. Syst. 115, 90–103 (2019)

    Article  Google Scholar 

  38. Zadeh, L.A.: Fuzzy sets. Inf. Control 8(3), 338–353 (1965)

    Article  Google Scholar 

  39. Zimmermann, H.J.: Fuzzy programming and linear programming with several objective functions. Fuzzy Sets Syst. 1(1), 45–55 (1978)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Materials and Production, Aalborg University, Fibigerstræde 16, 9220, Aalborg, Denmark

    Izabela Nielsen & Subrata Saha

  2. Faculty of Electronics and Computer Science, Koszalin University of Technology, 75-453, Koszalin, Poland

    Grzegorz Bocewicz

Authors
  1. Izabela Nielsen
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Grzegorz Bocewicz
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Subrata Saha
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Subrata Saha .

Editor information

Editors and Affiliations

  1. IoT European Digital Innovation Hub, Bioinformatics Intelligent Systems and Educational Technology Research Group, Department of Computer Science, Faculty of Science, University of Salamanca, Salamanca, Spain

    Sara Rodríguez González

  2. GRASIA Research Group, Facultad de Informática, Universidad Complutense de Madrid, Madrid, Spain

    Alfonso González-Briones

  3. Faculty of Mechanical Engineering, Department of Production Computerisation and Robotisation, Lublin University of Technology, Lublin, Poland

    Arkadiusz Gola

  4. Cerca Trova Ltd, Sofia, Bulgaria

    George Katranas

  5. Department of Biology, Ecology and Earth Science, University of Calabria, Arcavacata di Rende, Cosenza, Italy

    Michela Ricca

  6. Department of Mathematics, Stockholm University, Stockholm, Sweden

    Roussanka Loukanova

  7. Institute of Mathematics and Informatics, Bulgarian Academy of Sciences, Sofia, Bulgaria

    Roussanka Loukanova

  8. IoT European Digital Innovation Hub, Bioinformatics Intelligent Systems and Educational Technology Research Group, Department of Computer Science, Faculty of Science, University of Salamanca, Salamanca, Spain

    Javier Prieto

Rights and permissions

Reprints and permissions

Copyright information

© 2021 The Editor(s) (if applicable) and The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Cite this paper

Nielsen, I., Bocewicz, G., Saha, S. (2021). Multi-agent Path Planning Problem Under a Multi-objective Optimization Framework. In: Rodríguez González, S., et al. Distributed Computing and Artificial Intelligence, Special Sessions, 17th International Conference. DCAI 2020. Advances in Intelligent Systems and Computing, vol 1242. Springer, Cham. https://doi.org/10.1007/978-3-030-53829-3_1

Download citation

Publish with us

Policies and ethics