Path Planning Method of Bidirectional Robot Based on Time Window Model

doi:10.3778/j.issn.1002-8331.2005-0286

Abstract

Abstract:

With the development of intelligence and automation, robots are more and more widely used; multi-robot path planning and collaboration issues have become the focus of current attention. In response to the above problems, an improved genetic algorithm is proposed. When initializing the total group, the selection range is expanded by selecting the adjacent points of the midpoint to ensure the continuity of the line. The path fitness is improved by the population fitness function to prevent excessive turning times. Some non-optimal individuals are guaranteed through roulette, which can effectively prevent the algorithm from falling into the local optimal solution. Based on the optimized genetic algorithm, according to the priority order, combined with the proposed time window model, the conflict types are classified and the corresponding coordination plan is formulated. The simulation results show that this method can effectively solve the path conflict problem of multi-robots, and improve the system efficiency through reasonable route planning.

Key words: path planning, time window, automatic handling, robot

摘要：

随着智能化与自动化的发展，机器人应用越来越广泛；多机器人路径规划和协作问题就成为当前关注的焦点。针对以上问题，提出了一种改进的遗传算法。在初始化总群时，通过选择中点的相邻点扩大选择范围确保线路连续。通过种群适应度函数改进路径平滑度防止转向次数过多。为了防止遗传算法陷入局部最优解，通过轮盘赌的方法确保一部分非最优个体。在优化后的遗传算法基础上根据优先级顺序，并结合提出的时间窗模型，对冲突类型进行分类处理并制定对应的协调方案。仿真结果表明，该方法可以有效地解决多机器人的路径冲突问题，通过合理地规划线路提高系统效率。

关键词: 路径规划, 时间窗, 自动搬运, 机器人

WANG Chen, MAO Jian. Path Planning Method of Bidirectional Robot Based on Time Window Model[J]. Computer Engineering and Applications, 2021, 57(23): 287-294.

王琛，茅健. 基于时间窗模型的双向机器人路径规划方法[J]. 计算机工程与应用, 2021, 57(23): 287-294.

References

[1] 颜灿明，张程.基于MQTT的AGV自动导航机器人[J].单片机与嵌入式系统应用，2020，20（4）：22-24.
YAN Canming，ZHANG Cheng.AGV automatic navigation robot based on MQTT[J].Microcontrollers & Embedded Systems，2020，20（4）：22-24.
[2] 陈亚，张栗铭，张雪峰，等.基于SAPI的双驱双向AGV语音控制系统的设计[J].北京石油化工学院学报，2020，28（1）：54-58.
CHEN Ya，ZHANG Liming，ZHANG Xuefeng，et al.Design of speech control system of double drive two-way AGV based on SAPI[J].Journal of Beijing Institute of Petrochemical Technology，2020，28（1）：54-58.
[3] 范厚明，岳丽君，李荡，等.考虑路径冲突的AGV配置与调度优化[J].运筹与管理，2020，29（5）：43-51.
FAN Houming，YUE Lijun，LI Dang，et al.Optimization of AGV dispatching and configuration considering path conflict[J].Operations Research and Management Science，2020，29（5）：43-51.
[4] 齐权.混入U型框架车的某装配车间多AGV路径优化问题研究[D].沈阳：沈阳工业大学，2019.
QI Quan.Research on multi-AGV path optimization of an assembly workshop mixed with U-frame vehicles[D].Shenyang：Shenyang University of Technology，2019.
[5] 宋宇，王志明.基于改进遗传算法的移动机器人路径规划[J].现代电子技术，2019，42（24）：172-175.
SONG Yu，WANG Zhiming.Path planning of mobile robot based on improved genetic algorithm[J].Modern Electronic Technology，2019，42（24）：172-175.
[6] 党宏社，孙心妍.基于遗传算法的工厂AGV路径优化研究[J].电子产品世界，2020，27（1）：48-51.
DANG Hongshe，SUN Xinyan.Research on path optimization of AGV in factory based on genetic algorithm[J].Electronic Engineering & Product World，2020，27（1）：48-51.
[7] 李天童，宁平凡，牛萍娟.基于改进遗传算法的工厂AGV安全路径规划[J].组合机床与自动化加工技术，2020（3）：160-163.
LI Tiantong，NING Pingfan，NIU Pingjuan.Factory AGV safety path planning based on improved genetic algorithm[J].Modular Machine Tool & Automatic Manufacturing Technique，2020（3）：160-163.
[8] 刘庆周，吴锋.多智能体路径规划研究进展综述[J].计算机工程，2020：1-13.
LIU Qingzhou，WU Feng.Research progress of multi-agent path planning[J].Computer Engineering，2020：1-13.
[9] FANTI M P，MANGINI A M，PEDRONCELLI G，et al.A decentralized control strategy for the coordination of AGV systems[J].Control Engineering Practice，2018，70：86．
[10] 王云常，戴朱祥，李涛.基于A星算法与人工势场法的无人机路径规划[J].扬州大学学报（自然科学版），2019，22（3）：36-38.
WANG Yunchang，DAI Zhuxiang，LI Tao.UAV path planning based on A-star algorithm and artificial potential field method[J].Journal of Yangzhou University（Natural Science Edition），2019，22（3）：36-38.
[11] 林娜，李天啸.基于双向A*算法的城市无人机航路规划[J].沈阳航空航天大学学报，2016，33（4）：55-60.
LIN Na，LI Tianxiao.Urban UAV route planning based on bidirectional A* algorithm[J].Journal of Shenyang University of Aeronautics and Astronautics，2016，33（4）：55-60.
[12] 李少波，宋启松，李志昂，等.遗传算法在机器人路径规划中的研究综述[J].科学技术与工程，2020，20（2）：423-431.
LI Shaobo，SONG Qisong，LI Zhi’ang，et al.Review of genetic algorithm in robot path planning[J].Science Technology and Engineering，2020，20（2）：423-431.
[13] NAZARAHARI M，KHANMIRZA E，DOOSTIE S.Multi-objective multi-robot path planning in continuous environment using an enhanced genetic algorithm[J].Expert Systems with Applications，2018，115：106-120.
[14] 杨志龙.模拟退火算法在室内定位中的应用[J].北京测绘，2020，34（3）：356-360.
YANG Zhilong.Application of simulated annealing algorithm in indoor location[J].Beijing Surveying and Mapping，2020，34（3）：356-360.
[15] LIU Qinghe，LIU Haiwei，WEN Yao，et al.An optimal trajectory planning for autonomous vehicles based on vehicle dynamics constraints[C]//2019 3rd Conference on Vehicle Control and Intelligence（CVCI），2020.
[16] 孟祥忠，刘健，李鹏.多AGV定位和路径规划方法研究[J].工业仪表与自动化装置，2019（5）：7-10.
MENG Xiangzhong，LIU Jian，LI Peng.Research on multi-AGV location and path planning method[J].Industrial Instrumentation & Automation，2019（5）：7-10.
[17] 袁洋，叶峰，赖乙宗，等.结合负载均衡与A*算法的多AGV路径规划[J].计算机工程与应用，2020，56（5）：251-256.
YUAN Yang，YE Feng，LAI Yizong，et al.Multi-AGV path planning combined with load balancing and A* algorithm[J].Computer Engineering and Applications，2020，56（5）：251-256.
[18] 齐权，张新敏.基于改进克隆选择算法的多AGV路径规划研究[J].物流工程与管理，2019，41（8）：96-99.
QI Quan，ZHANG Xinmin.Path planning for multiple AGV system based on improved clonal selection algorithm[J].Logistics Engineering and Management，2019，41（8）：96-99.
[19] 孙炜，吕云峰，唐宏伟，等.基于一种改进 A*算法的移动机器人路径规划[J].湖南大学学报（自然科学版），2017，44（4）：94-101.
SUN Wei，LV Yunfeng，TANG Hongwei，et al.Mobile robot path planning based on an improved A* algorithm[J].Journal of Hunan University（Natural Sciences），2017，44（4）：94-101.
[20] 李靖，杨帆.区域多任务安全隐患排除的机器人调度策略[J].电讯技术，2020，60（1）：97-105.
LI Jing，YANG Fan.Robot scheduling strategy for removing hidden dangers of regional multi-task security[J].Telecommunication Engineering，2020，60（1）：97-105.