基于改进烟花算法的多目标多机器人任务分配

张涛, 刘天威, 李富章, 胡孟阳

张涛, 刘天威, 李富章, 胡孟阳. 基于改进烟花算法的多目标多机器人任务分配[J]. 信号处理, 2020, 36(8): 1243-1252. DOI: 10.16798/j.issn.1003-0530.2020.08.007
引用本文: 张涛, 刘天威, 李富章, 胡孟阳. 基于改进烟花算法的多目标多机器人任务分配[J]. 信号处理, 2020, 36(8): 1243-1252. DOI: 10.16798/j.issn.1003-0530.2020.08.007
shu
Zhang Tao, Liu Tianwei, Li Fuzhang, Hu Mengyang. Multi-objective Multi-robot Mission Planning Based on Improved Fireworks Algorithm[J]. JOURNAL OF SIGNAL PROCESSING, 2020, 36(8): 1243-1252. DOI: 10.16798/j.issn.1003-0530.2020.08.007
Citation: Zhang Tao, Liu Tianwei, Li Fuzhang, Hu Mengyang. Multi-objective Multi-robot Mission Planning Based on Improved Fireworks Algorithm[J]. JOURNAL OF SIGNAL PROCESSING, 2020, 36(8): 1243-1252. DOI: 10.16798/j.issn.1003-0530.2020.08.007
shu

基于改进烟花算法的多目标多机器人任务分配

  • 天津大学电气自动化与信息工程学院

详细信息

  • 中图分类号: TK448.21

Multi-objective Multi-robot Mission Planning Based on Improved Fireworks Algorithm

  • School of Electrical Automation and Information Engineering, Tianjin University

HTML全文

    摘要
  • 摘要: 多机器人任务规划是多机器人系统研究的主要问题之一，多目标多机器人任务规划是指同时对多机器人系统的多个指标进行优化。近年来，启发式算法越来越多地被用来解决多目标问题。本文提出了一种基于改进烟花算法的多目标多机器人任务分配方法，并详细讨论了多目标解的排序方法和选择策略。为了验证该方法的性能，对7个实例进行了实验，并对该方法和其他四种多目标算法，Non-dominated Sorting Genetic Algorithm II (NSGA-II), Strength Pareto Evolutionary Algorithm 2 (SPEA2)，Pareto Envelope-based Selection Algorithm (PESA ) 和一种改进的Strength Pareto Genetic Algorithm 2 (SPGA2)在S-metric指标上进行了比较。实验结果表明，在解集质量、解集覆盖度方面，基于改进烟花算法的多目标多机器人任务分配方法具有明显的优势。
    Abstract: Multi-robot mission planning is one of the main problems in multi-robot system research. Multi-objective multi-robot mission planning refers to optimizing multiple indicators of the multi-robot system at the same time. In recent years, heuristic algorithms have increasingly been used to solve multi-objective prob-lems. In this paper, a multi-objective multi-robot mission planning method based on improved fireworks algorithm was proposed. In addition, the sorting method and selection strategy of the multi-objective so-lutions were discussed in detail. In order to verify the performance of the method, seven instances were tested, and the method was compared with other four multi-objective algorithms on the S-metric index. The other four multi-objective algorithms were Non-dominated Sorting Genetic Algorithm II (NSGA-II), Strength Pareto Evolutionary Algorithm 2 (SPEA2)，Pareto Envelope-based Selection Algorithm (PESA) and an Improved Strength Pareto Genetic Algorithm 2 (SPGA2). Experimental results shown that the proposed multi-objective multi-robot mission planning method based on improved fireworks algorithm has obvious advantages both in Pareto solution set quality and solution set scale.
    • HTML全文
    • 参考文献(24)
  • [1] Wei C, Hindriks K V, Jonker C M.Dynamic task allocation for multi-robot search and retrieval tasks[J].Applied Intelligence, 2016, 45(2):1-19
    [2] Juan Jesús Roldán, Miguel A Olivares-Méndez, Cerro J D, et al.Analyzing and improving multi-robot missions by using process mining[J].Autonomous Robots, 2018, 42(6):1187-1205
    [3] Luo L, Chakraborty N, Sycara K.Provably-Good Distributed Algorithm for Constrained Multi-Robot Task Assignment for Grouped Tasks[J].IEEE Transactions on Robotics, 2015, 31(1):19-30
    [4] Chopra S, Notarstefano G, Rice M, et al.Distributed Version of the Hungarian Method for a Multirobot Assignment[J].IEEE Transactions on Robotics, 2017, PP(99):1-16
    [5] Itziar L T, Diana M, Sonia B, et al.Underwater Robot Task Planning Using Multi-Objective Meta-Heuristics[J].Sensors, 2017, 17(4):762-
    [6] Janakiraman N, Kumar P N.Multi-objective hardware/software partitioning technique for dynamic and partial reconfigurable system-on-chip using genetic algorithm[J]. International Journal of Engineering & Technology, 2014, 6(2).
    [7] Govil N, Shrestha R, Chowdhury S R.A New Multi-objective Hardware-Software-Partitioning Algorith-mic Approach for High Speed Applications[C]//Hsinchu, Taiwan, 2017 International Symposium on VlSI Design & Test. Springer, Singapore, 2017.
    [8] Tan Y, Zhu Y.Fireworks Algorithm for Optimization[C]//Beijing, China, 2010 International Conference on Advances in Swarm Intelligence. Springer-Verlag, 2010:355-364.
    [9] van den Berg, Ewout, Friedlander, Michael P.Probing the Pareto Frontier for Basis Pursuit Solutions[J].Siam Journal on Scientific Computing, 2008, 31(2):890-912
    [10] Deb, Kalyanmoy, Pratap, et al.A fast and elitist multiobjective genetic algorithm: NSGA-II[J].IEEE Transactions on Evolutionary Computation, 2002, 6(2):182-197
    [11] Kim M, Hiroyasu T, Miki M, et al.SPEA2+: Improving the Performance of the Strength Pareto Evolu-tionary Algorithm 2[J].Parallel Problem Solving from Nature-PPSN VIII, 2004, 3242(4):742-751
    [12] Corne D W, Knowles J D, Oates M J.The Pareto Envelope-Based Selection Algorithm for Multiobjec-tive Optimization[C]//Paris, France, 2000 International Conference on Parallel Problem Solving From Nature. Springer-Verlag, 2000:839-848.
    [13] 束柬, 梁昌勇, 徐健.基于信任的云服务系统多目标任务分配模型[J].计算机研究与发展, 2018, v.55(06):53-65
    [14] Shu Jian, Liang Changyong, Xujian, et al.Trust-Based Multi-Objectives Task Assignment Model in Cloud Service System[J]. Journal of Computer Research and Development. 2018, v.55(06):53-65.(in Chinese)
    [15] Gerkey B P, Matari?, Maja J.A Formal Analysis and Taxonomy of Task Allocation in Multi-Robot Sys-tems[J].International Journal of Robotics Research, 2004, 23(9):939-954
    [16] Li J, Zheng S, Ying T.The Effect of Information Utilization: Introducing a Novel Guiding Spark in the Fireworks Algorithm[J].IEEE Transactions on Evolutionary Computation, 2017, 21(1):153-166
    [17] 王芳, 饶运清, 唐秋华, 等.多目标决策下非支配解的快速构造方法[J].系统工程理论与实践, 2016, 36(2):454-463
    [18] Wang Fang, Rao Yunqing, Tang Qiuhua, et al.Fast construction method of Pareto non-dominated solu-tion for multi-objective decision-making problem[J].Systems Engineering-Theory & Practice, 2016, 36(2):454-463
    [19] Bazgan C, Jamain F, Vanderpooten D.Approximate Pareto sets of minimal size for multi-objective op-timization problems[J].Operations Research Letters, 2015, 43(1):1-6
    [20] Wang Z, Rangaiah G P .Application and Analysis of Methods for Selecting an Optimal Solution from the Pareto-Optimal Front obtained by Multi-Objective Optimization[J]. Industrial & Engineering Chem-istry Research, 2016, 56(2).
    [21] Ishibuchi H, Yu S, Masuda H, et al.Performance of Decomposition-Based Many-Objective Algorithms Strongly Depends on Pareto Front Shapes[J].IEEE Transactions on Evolutionary Computation, 2017, 21(2):169-190
    [22] Jaszkiewicz A, Lust T.Proper balance between search towards and along Pareto front: biobjective TSP case study[J].Annals of Operations Research, 2017, 254(1-2):1-20
    [23] Naujoks B, Beume N, Emmerich M.Multi-objective optimization using S-metric selection: application to three-dimensional solution spaces[C]// Edinburgh, UK, 2005 IEEE Congress on Evolutionary Compu-tation. IEEE, 2005: 1282-1289.
    [24] Beume N.S-Metric calculation by considering dominated hypervolume as Klee's measure problem[J].Evolutionary Computation, 2014, 17(4):477-492
    • 相关文章
    • 施引文献
    • 资源附件(0)
计量
  • 文章访问数:  146
  • HTML全文浏览量:  21
  • PDF下载量:  248
  • 被引次数: 0
出版历程
  • 收稿日期:  2020-05-11
  • 修回日期:  2020-06-18
  • 发布日期:  2020-08-24

目录

摘要
HTML全文
    参考文献(24)
    相关文章
    施引文献
    资源附件(0)

    /

    返回文章
    返回

    版权所有 © 2009 《信号处理》 编辑部  京ICP备12041980号-1

    地址：北京市西城区鼓楼西大街41号  电话：010-64010656  Email：xhcl@signal.org.cn

    本系统由 北京仁和汇智信息技术有限公司 开发  百度统计