Research On Conflict Search Oriented Path Planning For Multiple Robots

The path planning of Automated Guided Vehicle(AGV)is an important component of intelligent warehousing.With the popularization of automation and intelligent warehousing systems,intelligent devices such as mobile robots and sorting robots have been applied to warehousing systems,participating in warehouse tasks such as inbound and outbound logistics warehousing,improving warehouse operational efficiency and reducing transportation costs.With the continuous improvement of the capacity of relevant facilities for intelligent logistics warehousing operations,stable workshop operations can be achieved,and the development of Digital transformation and artificial intelligence industry in various regions can be promoted.The problem of conflicts caused by paths between multiple robots needs to be combined with the actual working environment of the robot and the logical handling of the storage system in order to maximize the planning of outbound,inbound,and inbound operations.The Multi Agent Path Finding(MAPF)is a problem of searching paths for multiple robots.This article focuses on the goal of multiple robots moving along the planned path without collision.Based on the Conflict Based Search(CBS)algorithm,a method is studied to effectively plan paths for multiple robots on maps such as workshops.This article designs a conflict based bidirectional A ~* search method and a conflict based increased cost search algorithm,respectively.The main job responsibilities are as follows:Aiming at the problem that the path search of a single robot at the lower level of the algorithm is slow,a bidirectional A ~* search algorithm is proposed,which optimizes the unidirectional search of A ~* to bidirectional search,and introduces focus search at the lower level,so that it can expand from the node that is least prone to collision,expand the speed of node search,and thus accelerate the path search.Based on the CBS algorithm,the Enhanced Conflict Based Search(ECBS)algorithm is optimized by using focused search at the highlevel to ensure that the cost of its solution is within the given optimal factor,thereby improving the computational efficiency of the CBS algorithm;In order to verify the effectiveness of this method,this article uses Octomap for map modeling on a Linux system,taking into account the characteristics of the warehouse environment,designs corresponding map information,and completes the construction of the simulation map environment.100 robots were set up in the warehouse map for simulation experiments,and the motion trajectories of multi robot path planning were simulated using C++under Linux.The optimized A ~* algorithm and classic A ~* algorithm were compared and verified Improve the parameter indicators of ECBS algorithm and traditional ECBS algorithm.From the experimental results,it can be seen that the total running time of the optimized algorithm is reduced by 10.63% compared to before optimization,and the path cost is reduced by 14.82%.The optimized ECBS algorithm returns a solution that is close to the optimal solution.In response to the exponential expansion of the number of nodes when dealing with symmetry conflicts in the high-level of CBS,and the robustness of the increased cost search algorithm when dealing with symmetry conflicts,a conflict based increased cost search has been developed by combining the high-level of CBS algorithm with the increased cost search.Utilizing the advantages of CBS and Increasing Cost Tree Search(ICTS)algorithms,a Cost Range Constraint Tree(CRCT)is searched at the high-level of the algorithm.Based on the initial mutually exclusive objects,the propagated mutually exclusive objects are searched,and each robot is created with its own multivalued decision graph and corresponding vertex constraint conditions.By using Pairwise Constraint Search(PCS),the problem of excessive number of extended nodes in symmetric conflicts during continuous time periods was solved.PCS searched the entire paired space,jointly planned two conflicting robots,discovered motion constraints and cost constraints,and found feasible solutions.The optimized CBS algorithm dynamically uses conjunction and disjunction splitting in high-level search,increasing costs while resolving symmetry conflicts.The test results show that compared with other similar optimal algorithms,the improved CBS algorithm can reduce the density of expanded nodes by deleting redundant nodes at the same path cost compared to traditional CBS algorithms,which can reduce a lot of algorithm work.On the Linux system,the simulation map is selected as the city map,and the number of robots is set to 50.According to the simulation results,the conflict based increased cost search path planning algorithm studied can quickly plan the path.