基于蚁群算法的多机协同作业任务规划
|
摘要
为了实现对农田动态环境中多机协同导航作业的调度管理,开展了基于蚁群算法的多机协同作业任务规划研究。将多机协同作业任务规划分为2个环节:任务分配和任务序列规划。首先,采用全局与局部相结合的方法,综合考虑路径代价和任务执行能力,建立了多机协同作业任务分配模型;然后,通过对比分析任务序列规划问题和旅行商问题,利用蚁群算法建立了农机作业的任务序列规划模型;最后,利用Matlab平台对基于蚁群算法的任务序列规划进行了仿真试验,根据涿州试验农场的实际地块信息,设置多组不同的任务集合,分析蚁群算法优化路径、各代最佳路径长度和平均长度以及适应度进化曲线。仿真结果表明,基于蚁群算法进行任务序列优化可以有效地降低路径代价,提高作业效率,算法运行时间均小于1 s,满足多机协同作业的实时性需求。
In order to realize the dispatching management of multi-machine cooperative navigation operation in dynamic farmland environment,the task planning of multi-machine cooperative navigation operation based on ant colony algorithm was studied. The task planning of multi-machine cooperative operation was divided into two parts: task allocation and task sequence planning. Firstly,a task allocation model of multi-machine cooperative operation was established by combining global and local methods,considering both path cost and task execution ability. Then,by comparing and analyzing the task sequence planning problem and traveling salesman problem,the task sequence planning model of agricultural machinery operation was established by using ant colony algorithm. Finally,the simulation experiment of task sequence planning based on ant colony algorithm was carried out by using Matlab platform. According to the actual land information of Zhuozhou experimental farm,different groups of task sets were set to analyze the optimization path,the shortest and average distance of each generation and the fitness evolution curve of ant colony algorithm. The simulation results showed that the task sequence optimization based on ant colony algorithm can effectively reduce the cost of path and improve the efficiency of operation. The running time of the algorithm was less than 1 s,which preliminarily met the real-time requirements of multi-machine cooperative operation,and provided a basis for further solving the multi-machine cooperative navigation operation in the field environment.
In order to realize the dispatching management of multi-machine cooperative navigation operation in dynamic farmland environment,the task planning of multi-machine cooperative navigation operation based on ant colony algorithm was studied. The task planning of multi-machine cooperative operation was divided into two parts: task allocation and task sequence planning. Firstly,a task allocation model of multi-machine cooperative operation was established by combining global and local methods,considering both path cost and task execution ability. Then,by comparing and analyzing the task sequence planning problem and traveling salesman problem,the task sequence planning model of agricultural machinery operation was established by using ant colony algorithm. Finally,the simulation experiment of task sequence planning based on ant colony algorithm was carried out by using Matlab platform. According to the actual land information of Zhuozhou experimental farm,different groups of task sets were set to analyze the optimization path,the shortest and average distance of each generation and the fitness evolution curve of ant colony algorithm. The simulation results showed that the task sequence optimization based on ant colony algorithm can effectively reduce the cost of path and improve the efficiency of operation. The running time of the algorithm was less than 1 s,which preliminarily met the real-time requirements of multi-machine cooperative operation,and provided a basis for further solving the multi-machine cooperative navigation operation in the field environment.
引文
[1]姬长英,周俊.农业机械导航技术发展分析[J].农业机械学报,2014,45(9):44-54.JI Changying,ZHOU Jun.Current situation of navigation technologies for agricultural machinery[J].Transactions of the Chinese Society for Agricultural Machinery,2014,45(9):44-54.(in Chinese)
[2]贾全.拖拉机自动导航系统关键技术研究[D].北京:中国农业机械化科学研究院,2013.JIA Quan.Study on key technology of tractor auto-navigation system[D].Beijing:Chinese Academy of Agricultural Mechanization Sciences,2013.(in Chinese)
[3]胡静涛,高雷,白晓平,等.农业机械自动导航技术研究进展[J].农业工程学报,2015,31(10):1-10.HU Jingtao,GAO Lei,BAI Xiaoping,et al.Review of research on automatic guidance of agricultural vehicles[J].Transactions of the CSAE,2015,31(10):1-10.(in Chinese)
[4]LIDA M,KUDOU M,ONO K,et al.Automatic following control for agricultural vehicle[C]∥6th International Workshop on Advanced Motion Control Proceedings.Nagoya:Institute of Electrical and Electronics Engineers,2000:158-162.
[5]NOGUCHI N,WILL J,REID J,et al.Development of amaster-slave robot system for farm operations[J].Computers and Electronics in Agriculture,2004,44(1):1-19.
[6]ZHANG P,QIAO J F,ZHANG H Y.Path planning and tracking for agricultural master-slave robot system[C]∥2010International Conference on Computer and Communication Technologies in Agriculture Engineering.Chengdu:Institute of Electrical and Electronics Engineers,2010:55-58.
[7]李世超.跟随式农机主从导航系统设计与开发[D].北京:中国农业大学,2018.LI Shichao.Design of development of a follow agricultural machinery master-slave navigation system[D].Beijing:China Agricultural University,2018.(in Chinese)
[8]刘婷.多机器人任务规划方法研究[D].南京:南京理工大学,2004.LIU Ting.Research on multi-robot task planning method[D].Nanjing:Nanjing University of Science and Technology,2004.(in Chinese)
[9]魏铁涛,屈香菊.多机协同与多目标分配任务规划方法[J].北京航空航天大学学报,2009,35(8):917-920,924.WEI Tietao,QU Xiangju.Route planning method for multiple vehicles coordinated target assignment[J].Journal of Beijing University of Aero-nautics and Astronautics,2009,35(8):917-920,924.(in Chinese)
[10]余伶俐,焦继乐,蔡自兴.一种多机器人任务规划算法及其系统实现[J].计算机科学,2010,37(6):252-255.YU Lingli,JIAO Jile,CAI Zixing.Multi-robot mission planning algorithm and its system implementation[J].Computer Science,2010,37(6):252-255.(in Chinese)
[11]李智.智能优化算法研究及应用展望[J].武汉轻工大学学报,2016,35(4):1-9,131.LI Zhi.Survey on intelligent optimization algorithms[J].Journal of Wuhan Polytechnic University,2016,35(4):1-9,131.(in Chinese)
[12]EUN Y,BANG H.Cooperative task assignment/path planning of multiple unmanned aerial vehicles using genetic algorithms[J].Journal of Aircraft,2009,46(1):338-343.
[13]HO S Y,LIN H S,LIAUH W H,et al.OPSO:orthogonal particle swarm optimization and its application to task assignment problems[J].IEEE Trans on Systems,Man and Cybernetics,Part A:System and Humans,2008,38(2):288-298.
[14]张磊.轮式机器人路径规划及任务调度算法研究与设计[D].广州:华南理工大学,2016.ZHANG Lei.Research and design in algorithm of path planning and task scheduling for wheeled robot[D].Guangzhou:South China University of Technology,2016.(in Chinese)
[15]蔡标.基于蚁群算法的多机器人任务分配研究[D].齐齐哈尔:齐齐哈尔大学,2015.CAI Biao.Research of multi-robot task allocation based on ant colony algorithm[D].Qiqihar:Qiqihar University,2015.(in Chinese)
[16]何建华,王安龙,陈松,等.基于改进MOSFLA的多机协同任务分配[J].西北工业大学学报,2014,32(4):630-636.HE Jianhua,WANG Anlong,CHEN Song,et al.Cooperative task assignment for multiple fighters using improved MOSFLAalgorithm[J].Journal of Northwestern Polytechnical University,2014,32(4):630-636.(in Chinese)
[17]刘晓莹.混沌蚁群算法在多机器人任务规划中的应用研究[D].长沙:中南大学,2010.LIU Xiaoying.Application of chaos ant colony algorithm in multi-robots system mission planning[D].Changsha:Central South University,2010.(in Chinese)
[18]JIM P,ALCHERIO M.Distributed adaptation in multi-robot serachusing particle swarm optimization[C]∥The 10th International Conference on the Simulation of Adaptive Behavior.Berlin:Springer-Verlag,2008:393-402.
[19]曹如月,李世超,魏爽,等.基于Web-GIS的多机协同作业远程监控平台设计[J].农业机械学报,2017,48(增刊):52-57,14.CAO Ruyue,LI Shichao,WEI Shuang,et al.Remote monitoring platform for multi-machine cooperation based on Web-GIS[J].Transactions of the Chinese Society for Agricultural Machinery,2017,48(Supp.):52-57,14.(in Chinese)
[20]秦新立,宗群,李晓瑜,等.基于改进蚁群算法的多机器人任务分配[J].空间控制技术与应用,2018,44(5):55-59.QIN Xinli,ZONG Qun,LI Xiaoyu,et al.Task allocation of multi-robot based on improved ant colony algorithm[J].Aerospace Control and Application,2018,44(5):55-59.(in Chinese)
[21]张衡.基于蚁群算法的多农业机器人路径规划研究[J].数字技术与应用,2017(6):147-149.ZHANG Heng.Research on path planning of multi farm robot based on ant colony algorithm[J].Digital Technology and Application,2017(6):147-149.(in Chinese)
[22]曹宗华,吴斌,黄玉清,等.基于改进蚁群算法的多机器人任务分配[J].组合机床与自动化加工技术,2013(2):34-37.CAO Zonghua,WU Bin,HUANG Yuqing,et al.The multi-robot task allocation study based on improved ant colony algorithm[J].Modular Machine Tool&Automatic Manufacturing Technique,2013(2):34-37.(in Chinese)
[23]袁豪.旅行商问题的研究与应用[D].南京:南京邮电大学,2017.YUAN Hao.Research and application of traveling salesman problem[D].Nanjing:Nanjing University of Posts and Telecommunications,2017.(in Chinese)
[24]乔东平,裴杰,肖艳秋,等.蚁群算法及其应用综述[J].软件导刊,2017,16(12):217-221.QIAO Dongping,PEI Jie,XIAO Yanqiu,et al.Ageneral overview on ant colony algorithm and its application[J].Software Guide,2017,16(12):217-221.(in Chinese)
[2]贾全.拖拉机自动导航系统关键技术研究[D].北京:中国农业机械化科学研究院,2013.JIA Quan.Study on key technology of tractor auto-navigation system[D].Beijing:Chinese Academy of Agricultural Mechanization Sciences,2013.(in Chinese)
[3]胡静涛,高雷,白晓平,等.农业机械自动导航技术研究进展[J].农业工程学报,2015,31(10):1-10.HU Jingtao,GAO Lei,BAI Xiaoping,et al.Review of research on automatic guidance of agricultural vehicles[J].Transactions of the CSAE,2015,31(10):1-10.(in Chinese)
[4]LIDA M,KUDOU M,ONO K,et al.Automatic following control for agricultural vehicle[C]∥6th International Workshop on Advanced Motion Control Proceedings.Nagoya:Institute of Electrical and Electronics Engineers,2000:158-162.
[5]NOGUCHI N,WILL J,REID J,et al.Development of amaster-slave robot system for farm operations[J].Computers and Electronics in Agriculture,2004,44(1):1-19.
[6]ZHANG P,QIAO J F,ZHANG H Y.Path planning and tracking for agricultural master-slave robot system[C]∥2010International Conference on Computer and Communication Technologies in Agriculture Engineering.Chengdu:Institute of Electrical and Electronics Engineers,2010:55-58.
[7]李世超.跟随式农机主从导航系统设计与开发[D].北京:中国农业大学,2018.LI Shichao.Design of development of a follow agricultural machinery master-slave navigation system[D].Beijing:China Agricultural University,2018.(in Chinese)
[8]刘婷.多机器人任务规划方法研究[D].南京:南京理工大学,2004.LIU Ting.Research on multi-robot task planning method[D].Nanjing:Nanjing University of Science and Technology,2004.(in Chinese)
[9]魏铁涛,屈香菊.多机协同与多目标分配任务规划方法[J].北京航空航天大学学报,2009,35(8):917-920,924.WEI Tietao,QU Xiangju.Route planning method for multiple vehicles coordinated target assignment[J].Journal of Beijing University of Aero-nautics and Astronautics,2009,35(8):917-920,924.(in Chinese)
[10]余伶俐,焦继乐,蔡自兴.一种多机器人任务规划算法及其系统实现[J].计算机科学,2010,37(6):252-255.YU Lingli,JIAO Jile,CAI Zixing.Multi-robot mission planning algorithm and its system implementation[J].Computer Science,2010,37(6):252-255.(in Chinese)
[11]李智.智能优化算法研究及应用展望[J].武汉轻工大学学报,2016,35(4):1-9,131.LI Zhi.Survey on intelligent optimization algorithms[J].Journal of Wuhan Polytechnic University,2016,35(4):1-9,131.(in Chinese)
[12]EUN Y,BANG H.Cooperative task assignment/path planning of multiple unmanned aerial vehicles using genetic algorithms[J].Journal of Aircraft,2009,46(1):338-343.
[13]HO S Y,LIN H S,LIAUH W H,et al.OPSO:orthogonal particle swarm optimization and its application to task assignment problems[J].IEEE Trans on Systems,Man and Cybernetics,Part A:System and Humans,2008,38(2):288-298.
[14]张磊.轮式机器人路径规划及任务调度算法研究与设计[D].广州:华南理工大学,2016.ZHANG Lei.Research and design in algorithm of path planning and task scheduling for wheeled robot[D].Guangzhou:South China University of Technology,2016.(in Chinese)
[15]蔡标.基于蚁群算法的多机器人任务分配研究[D].齐齐哈尔:齐齐哈尔大学,2015.CAI Biao.Research of multi-robot task allocation based on ant colony algorithm[D].Qiqihar:Qiqihar University,2015.(in Chinese)
[16]何建华,王安龙,陈松,等.基于改进MOSFLA的多机协同任务分配[J].西北工业大学学报,2014,32(4):630-636.HE Jianhua,WANG Anlong,CHEN Song,et al.Cooperative task assignment for multiple fighters using improved MOSFLAalgorithm[J].Journal of Northwestern Polytechnical University,2014,32(4):630-636.(in Chinese)
[17]刘晓莹.混沌蚁群算法在多机器人任务规划中的应用研究[D].长沙:中南大学,2010.LIU Xiaoying.Application of chaos ant colony algorithm in multi-robots system mission planning[D].Changsha:Central South University,2010.(in Chinese)
[18]JIM P,ALCHERIO M.Distributed adaptation in multi-robot serachusing particle swarm optimization[C]∥The 10th International Conference on the Simulation of Adaptive Behavior.Berlin:Springer-Verlag,2008:393-402.
[19]曹如月,李世超,魏爽,等.基于Web-GIS的多机协同作业远程监控平台设计[J].农业机械学报,2017,48(增刊):52-57,14.CAO Ruyue,LI Shichao,WEI Shuang,et al.Remote monitoring platform for multi-machine cooperation based on Web-GIS[J].Transactions of the Chinese Society for Agricultural Machinery,2017,48(Supp.):52-57,14.(in Chinese)
[20]秦新立,宗群,李晓瑜,等.基于改进蚁群算法的多机器人任务分配[J].空间控制技术与应用,2018,44(5):55-59.QIN Xinli,ZONG Qun,LI Xiaoyu,et al.Task allocation of multi-robot based on improved ant colony algorithm[J].Aerospace Control and Application,2018,44(5):55-59.(in Chinese)
[21]张衡.基于蚁群算法的多农业机器人路径规划研究[J].数字技术与应用,2017(6):147-149.ZHANG Heng.Research on path planning of multi farm robot based on ant colony algorithm[J].Digital Technology and Application,2017(6):147-149.(in Chinese)
[22]曹宗华,吴斌,黄玉清,等.基于改进蚁群算法的多机器人任务分配[J].组合机床与自动化加工技术,2013(2):34-37.CAO Zonghua,WU Bin,HUANG Yuqing,et al.The multi-robot task allocation study based on improved ant colony algorithm[J].Modular Machine Tool&Automatic Manufacturing Technique,2013(2):34-37.(in Chinese)
[23]袁豪.旅行商问题的研究与应用[D].南京:南京邮电大学,2017.YUAN Hao.Research and application of traveling salesman problem[D].Nanjing:Nanjing University of Posts and Telecommunications,2017.(in Chinese)
[24]乔东平,裴杰,肖艳秋,等.蚁群算法及其应用综述[J].软件导刊,2017,16(12):217-221.QIAO Dongping,PEI Jie,XIAO Yanqiu,et al.Ageneral overview on ant colony algorithm and its application[J].Software Guide,2017,16(12):217-221.(in Chinese)