Abstract: To solve the path conflict problem of Automated Guided Vehicle (AGV) in warehousing and logistics transportation system,an A* algorithm based on space-time grid and conflict constraint was proposed.The time axis was added to the topological grid map to build the spatiotemporal map model.According to the characteristics of spatiotemporal map and the conflict constraints,the sub node extension rules and node evaluation functions of A* algorithm were redesigned.The improved A* algorithm was used to plan the path for each AGV according to the priority order.After planning a path,the node information in the spatiotemporal map was recorded with the mark table,and then the new path was searched with the improved A* algorithm and the mark table.The simulation results showed the effectiveness of the proposed algorith.

Key words: path conflict, spatiotemporal map model, conflict constraint, A* algorithm, automated guided vehicle

摘要： 针对自动导引小车（AGV）在仓储物流搬运系统中的路径冲突问题,提出一种基于时空冲突约束的A*算法。先在拓扑栅格地图的基础上加入时间轴建立时空地图模型,再针对时空地图的特点和冲突约束条件重新设计A*算法的子节点扩展规则和节点评估函数。利用改进后的A*算法按照优先级顺序为各个AGV规划路径,规划完成一条路径后,用mark表记录其在时空地图中的节点信息,再利用改进后的A*算法结合mark表搜索新路径。通过仿真实验证明了该算法的有效性。

关键词: 路径冲突, 时空地图模型, 冲突约束, A*算法, 自动导引小车