技术领域technical field
本发明属于协同控制技术领域，尤其涉及一种采用离散化方法的多机器人协同轨迹信息处理方法。The invention belongs to the technical field of cooperative control, and in particular relates to a multi-robot cooperative trajectory information processing method using a discretization method.
背景技术Background technique
目前，最接近的现有技术：机器人的诞生使得传统的生产行业发生了翻天覆地的变化，人们研制出了可在各种环境下作业的移动机器人，如无人驾驶汽车(UnmannedGround Vehicle)，无人驾驶飞机(Unmanned Ariel Vehicle)，无人潜航器(UnmannedUnderwater Vehicle)等。移动机器人不仅在工业生产、医疗、航天、交通等领域具有广泛应用，并且在辐射、搜捕、灾后救援和军事行动等危险领域具有重要的应用价值。随着作业量的增加和作业复杂度的增强，系统对于任务的并行性、协调性的要求也在不断增强，单个机器人难以胜任。多机器人系统由于多个机器人的相互协作而具有一系列显著的优点，例如多机器人系统可以降低任务求解的复杂性、提升任务完成的高效性、增加系统的可靠性、简化系统的设计等。由于多机器人系统的这些优越性，吸引了全球各国的众多学者的研究兴趣。近年来，随着计算机技术以及自动化控制领域的快速发展，让机器人的性能特征更加的智能化、让机器人间的协同工作更加的灵活化都是技术发展和社会生产的一个新方向和新标准。At present, the closest existing technology: the birth of robots has brought about earth-shaking changes in the traditional production industry. People have developed mobile robots that can work in various environments, such as unmanned vehicles (Unmanned Ground Vehicle), unmanned Flying aircraft (Unmanned Ariel Vehicle), unmanned submarine vehicle (Unmanned Underwater Vehicle), etc. Mobile robots are not only widely used in industrial production, medical treatment, aerospace, transportation and other fields, but also have important application value in dangerous fields such as radiation, search and arrest, post-disaster rescue and military operations. As the workload increases and the complexity of the job increases, the system's requirements for parallelism and coordination of tasks are also increasing, and a single robot is difficult to do. Multi-robot systems have a series of significant advantages due to the mutual cooperation of multiple robots. For example, multi-robot systems can reduce the complexity of task solving, improve the efficiency of task completion, increase system reliability, and simplify system design. Due to these advantages of multi-robot systems, it has attracted the research interests of many scholars from all over the world. In recent years, with the rapid development of computer technology and automation control, making the performance characteristics of robots more intelligent and making the collaborative work between robots more flexible is a new direction and new standard for technological development and social production.
多机器人系统的轨迹规划是实现其自主导航的重要环节，其任务是为在同一工作环境中的多个机器人寻求无碰的最优路径，保证多个机器人均以最小代价安全到达目标点。实现并改善多移动机器人轨迹规划的性能，提高系统的实时性、自治性和准确性，已经成为移动机器人自主导航的主要研究方向。传统的机器人运动控制利用数学规划法对机器人轨迹进行规划，然而随着系统中机器人数量的增多和作业复杂度的提升，系统模型变得高度耦合、高度复杂，不易求解，无法解决逻辑上的故障，如避碰、死锁等。而基于监督控制理论的离散化方法在处理这些顶层逻辑问题上有显著的优势和便利性。通过离散化方法对多机器人系统的运动进行建模，获得激活的事件序列，使得系统在该事件序列的状态变迁下不会产生碰撞、死锁等问题。The trajectory planning of a multi-robot system is an important part of realizing its autonomous navigation. Its task is to find the optimal path without collision for multiple robots in the same working environment, so as to ensure that multiple robots can safely reach the target point at the minimum cost. Realizing and improving the performance of multi-robot trajectory planning, improving the real-time performance, autonomy and accuracy of the system has become the main research direction of mobile robot autonomous navigation. Traditional robot motion control uses mathematical programming to plan robot trajectories. However, as the number of robots in the system increases and the complexity of operations increases, the system model becomes highly coupled and complex, which is difficult to solve and cannot solve logical faults. , such as collision avoidance, deadlock, etc. The discretization method based on supervisory control theory has obvious advantages and convenience in dealing with these top-level logic problems. The movement of the multi-robot system is modeled by the discretization method, and the activated event sequence is obtained, so that the system will not produce collisions, deadlocks and other problems under the state transition of the event sequence.
目前，已有大量的文献对移动机器人运动控制的轨迹规划问题进行了研究，根据现阶段的研究成果分析，移动机器人的轨迹控制大致有以下几种控制思想：(1)离线控制。有文献通过iSCP算法为机器人多次规划运行轨迹，直到找到一条避开静态障碍物的平滑轨迹，该算法思想使得其在非凸域中也能规划出一条避开静态障碍物的最优轨迹，但其规划是离线的，无法运用在动态环境中；(2)预测控制MPC(Mode Predictive Control)，主要采用多步预测、滚动窗口和反馈校正等控制策略。因其较好的控制效果和较强的鲁棒性等优势，预测控制在多机器人控制领域得到了广泛应用。有文献使用iSCP算法和MPC控制策略相结合，在每一次轨迹运行的时域内进行预测控制达到实时轨迹规划的目的，但该算法计算量大、时域多，容易出现无解。还有文献使用滚动窗口预测避碰策略，为机器人在当前窗口进行局部规划，使得规划结果很难跳出局部最优的短板；(3)滑模控制(Sliding ModeControl)。其基本思想是将从任一点出发的状态轨线通过控制作用拉到某一指定的直线，然后沿此直线滑动到原点。在机器人避碰过程中，若沿直线滑动到的某一点出现障碍物再绕障碍物运行。该算法思想具有物理实现简单、抗干扰能力强以及反应速度快等特性，滑模控制也在机器人控制理论方面得到了广泛研究，但因其对障碍物缺少一个提前预测和感知，运行轨迹在障碍物处转角度数大、对机器人的冲击力大、性能损坏严重。At present, there have been a large number of literatures on the trajectory planning of mobile robot motion control. According to the analysis of the research results at this stage, the trajectory control of mobile robots generally has the following control ideas: (1) Off-line control. In the literature, the iSCP algorithm is used to plan the running trajectory for the robot multiple times until a smooth trajectory avoiding static obstacles is found. This algorithm idea enables it to plan an optimal trajectory avoiding static obstacles even in non-convex domains. But its planning is off-line and cannot be used in a dynamic environment; (2) MPC (Mode Predictive Control) mainly uses control strategies such as multi-step prediction, rolling window and feedback correction. Because of its good control effect and strong robustness, predictive control has been widely used in the field of multi-robot control. There are literatures that combine the iSCP algorithm and the MPC control strategy to perform predictive control in the time domain of each trajectory operation to achieve the purpose of real-time trajectory planning. However, this algorithm has a large amount of calculation and a large number of time domains, and it is prone to no solutions. There are also literatures that use the rolling window to predict the collision avoidance strategy to perform local planning for the robot in the current window, making it difficult for the planning result to jump out of the short board of the local optimum; (3) Sliding Mode Control (Sliding Mode Control). The basic idea is to pull the state trajectory starting from any point to a specified straight line through control, and then slide along this straight line to the origin. During the collision avoidance process of the robot, if an obstacle appears at a certain point slid along a straight line, it will then run around the obstacle. The algorithm idea has the characteristics of simple physical realization, strong anti-interference ability, and fast response speed. The object has a large rotation angle, a large impact on the robot, and serious performance damage.
机器人的轨迹规划作为机器人控制领域的一个重点，各国研究人员提出了很多常用的方法，如栅格法、遗传算法、蚁群算法和人工势场法等。应用栅格法实现路径规划的搜索具有盲目性，在复杂的环境中，搜索效率较低；有的学者使用遗传算法和蚁群算法进行动态环境下的路径规划，但都存在不同程度的实时性差的问题；还有的学者通过对人工势场法的拓展，使其可以进行动态环境下的路径规划，但人工势场法原始的一些问题未解决，如存在局部最优等。D*算法是在A*算法的基础上发展而来，它是动态的，因为弧成本参数可以在问题解决过程中发生变化。具有计算量小、实时性强和复杂程度低等优点，如果机器人运动正确地耦合到算法，则D*生成最优轨迹。Robot trajectory planning is a key point in the field of robot control. Researchers from various countries have proposed many commonly used methods, such as grid method, genetic algorithm, ant colony algorithm and artificial potential field method. The search for path planning using the grid method is blind, and the search efficiency is low in complex environments; some scholars use genetic algorithms and ant colony algorithms for path planning in dynamic environments, but they all have varying degrees of poor real-time performance. Some scholars have expanded the artificial potential field method to enable path planning in a dynamic environment, but some original problems of the artificial potential field method have not been resolved, such as the existence of local optima. The D* algorithm is developed on the basis of the A* algorithm, and it is dynamic because the arc cost parameter can change during the problem solving process. With the advantages of small amount of calculation, strong real-time performance and low complexity, D* generates the optimal trajectory if the robot motion is properly coupled to the algorithm.
综上所述，现有技术存在的问题是：现有技术中多个时域内预测控制策略的计算量大及轨迹局部最优。To sum up, the problems existing in the prior art are: the large amount of calculation of multiple time-domain predictive control strategies in the prior art and the local optimum of the trajectory.
解决上述技术问题的难度：The difficulty of solving the above technical problems:
多机器人系统能够提升任务完成的高效性、增加系统的可靠性、简化系统的设计等。然而随着系统中机器人数量的增多和作业复杂度的提升，使系统模型变得高度耦合、高度复杂，不易求解。同时传统的数学规划方法难以解决逻辑上的故障，如死锁、避碰等。Multi-robot systems can improve the efficiency of task completion, increase system reliability, and simplify system design. However, as the number of robots in the system increases and the complexity of operations increases, the system model becomes highly coupled, highly complex, and difficult to solve. At the same time, traditional mathematical programming methods are difficult to solve logical faults, such as deadlock and collision avoidance.
解决上述技术问题的意义：The significance of solving the above technical problems:
离散化方法的监督控制理论在处理这些顶层逻辑问题上有显著的优势和便利性。通过离散化方法对多机器人系统的运动进行建模，获得激活的事件序列，使得系统在该事件序列的状态变迁下不会产生碰撞、死锁等问题。多机器人系统的控制是分布式的实时在线控制，每个机器人在避碰的前提下自主规划全局最优的运行轨迹，实现了多机器人轨迹规划过程中的计算量小、实时性强和复杂度低。The supervisory control theory of discretization method has obvious advantages and convenience in dealing with these top-level logic problems. The movement of the multi-robot system is modeled by the discretization method, and the activated event sequence is obtained, so that the system will not produce collisions, deadlocks and other problems under the state transition of the event sequence. The control of the multi-robot system is a distributed real-time online control. Each robot independently plans the globally optimal trajectory under the premise of collision avoidance, which realizes the small amount of calculation, strong real-time performance and complexity in the multi-robot trajectory planning process. Low.
发明内容Contents of the invention
针对现有技术存在的问题，本发明提供了一种采用离散化方法的多机器人协同轨迹信息处理方法。Aiming at the problems existing in the prior art, the present invention provides a multi-robot cooperative trajectory information processing method using a discretization method.
本发明是这样实现的，一种采用离散化方法的多机器人协同轨迹信息处理方法，所述采用离散化方法的多机器人协同轨迹信息处理方法包括：The present invention is achieved in this way, a multi-robot collaborative trajectory information processing method using a discretization method, the multi-robot collaborative trajectory information processing method using a discretization method includes:
第一步，多机器人系统里的每一个机器人在运行前通过改进的D*算法得到一条最优的预规划轨迹，机器人提前预测碰撞点的位置；In the first step, each robot in the multi-robot system obtains an optimal pre-planning trajectory through the improved D* algorithm before running, and the robot predicts the position of the collision point in advance;
第二步，在机器人的通信范围内发现其他机器人后通过协同控制算法进行环境的实时更新，机器人自主判断当前位置到目标点的最优路径的再规划。In the second step, after finding other robots within the communication range of the robot, the environment is updated in real time through the collaborative control algorithm, and the robot independently judges the re-planning of the optimal path from the current position to the target point.
进一步，所述改进的D*算法引入pass列表，该列表用于存储机器人已运行轨迹的最新的N步位置，随着机器人的不断前进，pass列表进行实时更新；Further, the improved D* algorithm introduces a pass list, which is used to store the latest N-step position of the robot's running track, and as the robot continues to advance, the pass list is updated in real time;
while机器人Ri沿着最优轨迹前进do；//机器人Ri沿着最优轨迹前进while robot Ri advances along the optimal trajectory do; //robot Ri advances along the optimal trajectory
iflength(Pi)≤Nthen；//如果机器人Ri已经运行的轨迹步数小于等于N步iflength(Pi )≤Nthen;//If the number of trajectory steps that robot Ri has been running is less than or equal to N steps
pass＝add(Pi(now))；//将机器人Ri当前运行的轨迹位置添加进pass列表pass＝add(Pi (now));//Add the track position of the robot Ri currently running to the pass list
else pass＝add(Pi(end-N:end))；else pass = add(Pi (end-N:end));
//否则将机器人已运行轨迹的最新的N步位置更新进pass列表// Otherwise, update the latest N-step position of the robot's running trajectory into the pass list
endwhile。endwhile.
进一步，所述采用离散化方法的多机器人协同轨迹信息处理方法的单个机器人在自身的通信范围内发现可以与之进行通信的其他机器人后，尝试与其进行信息交互来获取其他机器人未来三个时刻的运行位置，并与自身的同一时刻的运行位置进行比较，判断是否会发生碰撞；如果不会发生碰撞，机器人继续前行；若会发生碰撞，确定碰撞类型并实行机器人间的避碰策略。Further, after a single robot in the multi-robot collaborative trajectory information processing method adopts the discretization method finds other robots that can communicate with it within its own communication range, it tries to interact with it to obtain other robots' information at three moments in the future. The running position is compared with its own running position at the same time to determine whether a collision will occur; if no collision occurs, the robot continues to move forward; if a collision occurs, determine the type of collision and implement a collision avoidance strategy between robots.
进一步，当机器人Ri在其通信范围内发现与机器人Rj进行信息交互时，预测策略如下：Further, when the robot Ri finds information interaction with the robot Rj within its communication range, the prediction strategy is as follows:
(1)机器人Ri在t时刻与机器人Rj进行信息交互，获取到机器人Rj的Pj(t+1)、Pj(t+2)和Pj(t+3)，其中Pj(t+1)、Pj(t+2)和Pj(t+3)分别代表机器人Rj未来三个时刻的运行位置；(1) Robot Ri interacts with robot Rj at time t, and obtains Pj (t+1), Pj (t+2) and Pj (t+3) of robot Rj , where Pj (t+1), Pj (t+2) and Pj (t+3) respectively represent the running positions of the robot Rj at three moments in the future;
(2)机器人Ri将获取到的信息与Pi(t+1)、Pi(t+2)和Pi(t+3)进行比较，其中Pi(t+1)、Pi(t+2)和Pi(t+3)分别代表机器人Ri未来三个时刻的运行位置；(2) The robot Ri compares the acquired information with Pi (t+1), Pi (t+2) and Pi (t+3), where Pi (t+1), Pi ( t+2) and Pi (t+3) respectively represent the running positions of the robot Ri at three moments in the future;
(3)若判定结果为不会发生碰撞，则机器人继续沿着预规划轨迹前行；(3) If the judgment result is that no collision will occur, the robot continues to move forward along the pre-planned trajectory;
(4)若判定结果为会发生碰撞，则确定碰撞类型，并将对应的碰撞位置设定为静态障碍物，将其他机器人设置为动态障碍物，更新单个机器人的运行环境。同时启动机器人间的避碰策略。(4) If the judgment result is that a collision will occur, determine the type of collision, set the corresponding collision position as a static obstacle, set other robots as dynamic obstacles, and update the operating environment of a single robot. At the same time start the collision avoidance strategy between the robots.
进一步，所述采用离散化方法的多机器人协同轨迹信息处理方法在多机器人系统中，当机器人Ri和机器人Rj的运行距离越来越接近直至在彼此的通信范围内时，机器人之间通过信息交互判断未来的轨迹中是否存在碰撞点，通过碰撞点的搜索算法找到碰撞位置，将碰撞位置暂时标记为静态障碍物；发生碰撞的机器人Ri和机器人Rj进行轨迹的重新规划，规划一条从其各自的当前位置到其各自的目标位置的最优路径；Further, the multi-robot collaborative trajectory information processing method using the discretization method is in a multi-robot system, when the running distance of the robot Ri and the robot Rj is getting closer until they are within the communication range of each other, the robots pass through Information interaction judges whether there is a collision point in the future trajectory, finds the collision location through the collision point search algorithm, and temporarily marks the collision location as a static obstacle; the collision robot Ri and robot Rj re-plan the trajectory, and plan a optimal paths from their respective current locations to their respective goal locations;
计算各个机器人规划的新路径相对于其预规划路径的增量，确定按照新规划路径运动的机器人；机器人Ri的轨迹增量为ΔPi，机器人Rj的轨迹增量为ΔPj：若ΔPi＞ΔPj，则机器人Rj沿着新规划的轨迹运行，机器人Ri沿着预规划的轨迹继续运行；若ΔPi＜ΔPj，则机器人Ri沿着新规划的轨迹运行，机器人Rj沿着预规划的轨迹继续运行；若ΔPi＝ΔPj，则随机选取一个机器人沿着新规划的轨迹运行，而另一个机器人沿着预规划的轨迹继续运行。Calculate the increment of the new path planned by each robot relative to its pre-planned path, and determine the robot moving according to the newly planned path; the trajectory increment of robot Ri is ΔPi , and the trajectory increment of robot Rj is ΔPj : if ΔPi ＞ΔPj , then the robot Rj runs along the newly planned trajectory, and the robot Ri continues to run along the pre-planned trajectory; if ΔPi <ΔPj , then the robot Ri runs along the newly planned trajectory, and the robot Rj continues to run along the pre-planned trajectory; if ΔPi =ΔPj , then randomly select one robot to run along the newly planned trajectory, while the other robot continues to run along the pre-planned trajectory.
进一步，利用提出的机器人间的碰撞预测策略，预测到机器人Ri和机器人Rj在某一时刻t即将发生碰撞，此时机器人的避碰策略具体如下所示：Further, using the proposed collision prediction strategy between robots, it is predicted that the robot Ri and the robot Rj will collide at a certain moment t. At this time, the robot’s collision avoidance strategy is as follows:
(1)若碰撞点为其中一个机器人的终止位置，假设为机器人Ri，则执行(2)，否则依次执行(3)和(4)；(1) If the collision point is the end position of one of the robots, assuming it is the robot Ri , then execute (2), otherwise execute (3) and (4) sequentially;
(2)机器人Rj进行环境信息的实时更新和存储，将碰撞点视为静态障碍物，利用改进的D*算法规划当前位置到目标位置的最优轨迹；机器人Ri继续沿着预规划的轨迹前进；(2) The robot Rj updates and stores the environmental information in real time, regards the collision point as a static obstacle, and uses the improved D* algorithm to plan the optimal trajectory from the current position to the target position; the robot Ri continues to follow the pre-planned track forward;
(3)机器人Ri和机器人Rj进行环境信息的实时更新和存储，将其他机器人视为动态障碍物，将碰撞点视为静态障碍物，利用改进的D*算法规划当前位置到目标位置的最优轨迹；(3) Robot Ri and robot Rj update and store environmental information in real time, regard other robots as dynamic obstacles, regard collision points as static obstacles, and use the improved D* algorithm to plan the distance from the current position to the target position optimal trajectory;
(4)比较机器人的轨迹增量：(4) Compare the trajectory increment of the robot:
若ΔPi＞ΔPj，则机器人Rj沿着新规划的轨迹运行，而机器人Ri沿着预规划的轨迹继续运行；If ΔPi > ΔPj , the robot Rj runs along the newly planned trajectory, and the robot Ri continues to run along the pre-planned trajectory;
若ΔPi＜ΔPj，则机器人Ri沿着新规划的轨迹运行，而机器人Rj沿着预规划的轨迹继续运行；If ΔPi <ΔPj , the robot Ri runs along the newly planned trajectory, and the robot Rj continues to run along the pre-planned trajectory;
若ΔPi＝ΔPj，令ranNum＝random(0，1)，若ranNum∈[0,0.5]，则机器人Rj沿着新规划的轨迹运行，而机器人Ri沿着预规划的轨迹继续运行。If ΔPi =ΔPj , let ranNum=random(0,1), if ranNum∈[0,0.5], then the robot Rj runs along the newly planned trajectory, and the robot Ri continues to run along the pre-planned trajectory .
本发明的另一目的在于提供一种应用所述采用离散化方法的多机器人协同轨迹信息处理方法的机器人协同控制系统。Another object of the present invention is to provide a robot cooperative control system applying the multi-robot cooperative trajectory information processing method using the discretization method.
综上所述，本发明的优点及积极效果为：本发明将滑模控制和预测控制的思想相结合，核心算法使用改进后的D*算法，提出一种新的控制算法即Sliding Mode D*算法，简称SMD*。积极效果具体体现在：In summary, the advantages and positive effects of the present invention are: the present invention combines the ideas of sliding mode control and predictive control, the core algorithm uses the improved D* algorithm, and proposes a new control algorithm that is Sliding Mode D* Algorithm, referred to as SMD*. The positive effects are specifically reflected in:
本发明利用栅格法来离散多机器人系统的工作环境，将物理问题转换为数学问题，求解过程无需借助求解器；本发明实现多机器人的分布式协同控制，克服了中心化控制思想导致系统缺乏健壮性和可扩展性的问题；本发明针对动态未知的运行环境，单个机器人只需在各自的通信范围内进行信息交互以及环境更新，无需测距传感器时刻感知周围的环境，简化了机器人的位置感知；本发明提出的方法是实时在线的轨迹规划，克服了现有技术中多个时域内预测控制策略的计算量大及轨迹局部最优的问题。The present invention uses the grid method to discretize the working environment of the multi-robot system, converts the physical problem into a mathematical problem, and does not need a solver in the solving process; the present invention realizes the distributed collaborative control of the multi-robot, and overcomes the system's lack of control caused by the idea of centralized control. The problem of robustness and scalability; the present invention is aimed at the dynamic and unknown operating environment, and a single robot only needs to perform information interaction and environment update within its own communication range, without the need for ranging sensors to perceive the surrounding environment at all times, which simplifies the position of the robot Perception: The method proposed by the present invention is real-time online trajectory planning, which overcomes the problems of large amount of calculation and local optimal trajectory of multiple time-domain predictive control strategies in the prior art.
附图说明Description of drawings
图1是本发明实施例提供的采用离散化方法的多机器人协同轨迹信息处理方法流程图。Fig. 1 is a flowchart of a method for processing multi-robot cooperative trajectory information using a discretization method provided by an embodiment of the present invention.
图2是本发明实施例提供的SMD*算法流程图。Fig. 2 is a flow chart of the SMD* algorithm provided by the embodiment of the present invention.
图3是本发明实施例提供的D*算法流程图。Fig. 3 is a flowchart of the D* algorithm provided by the embodiment of the present invention.
图4是本发明实施例提供的机器人碰撞类型示意图。Fig. 4 is a schematic diagram of robot collision types provided by an embodiment of the present invention.
图5是本发明实施例提供的机器人环境更新示意图。Fig. 5 is a schematic diagram of robot environment update provided by an embodiment of the present invention.
图6是本发明实施例提供的单机器人的通信范围示意图。Fig. 6 is a schematic diagram of the communication range of a single robot provided by an embodiment of the present invention.
图7是本发明实施例提供的多机器人的预规划轨迹图。Fig. 7 is a pre-planned trajectory diagram of a multi-robot provided by an embodiment of the present invention.
图8是本发明实施例提供的多机器人沿预规划轨迹运行图。Fig. 8 is a diagram of multi-robots running along a pre-planned trajectory provided by an embodiment of the present invention.
图9是本发明实施例提供的机器人重新规划轨迹示意图。。Fig. 9 is a schematic diagram of a replanned trajectory of a robot provided by an embodiment of the present invention. .
图10是本发明实施例提供的t1时刻多机器人的轨迹示意图。。Fig. 10 is a schematic diagram of trajectories of multiple robots at time t1 provided by an embodiment of the present invention. .
图11是本发明实施例提供的t2时刻多机器人的轨迹示意图。Fig. 11 is a schematic diagram of multi-robot trajectories at time t2 provided by an embodiment of the present invention.
图12是本发明实施例提供的多机器人的完整轨迹示意图。Fig. 12 is a schematic diagram of a complete trajectory of a multi-robot provided by an embodiment of the present invention.
具体实施方式Detailed ways
为了使本发明的目的、技术方案及优点更加清楚明白，以下结合实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。In order to make the object, technical solution and advantages of the present invention more clear, the present invention will be further described in detail below in conjunction with the examples. It should be understood that the specific embodiments described here are only used to explain the present invention, not to limit the present invention.
针对现有技术存在的问题，本发明提供了一种采用离散化方法的多机器人协同轨迹信息处理方法，下面结合附图对本发明作详细的描述。Aiming at the problems existing in the prior art, the present invention provides a multi-robot collaborative trajectory information processing method using a discretization method. The present invention will be described in detail below in conjunction with the accompanying drawings.
如图1所示，本发明实施例提供的采用离散化方法的多机器人协同轨迹信息处理方法包括以下步骤：As shown in Figure 1, the multi-robot collaborative trajectory information processing method using the discretization method provided by the embodiment of the present invention includes the following steps:
S101：多机器人系统里的每一个机器人在运行前通过改进的D*算法得到一条最优的预规划轨迹，机器人提前预测碰撞点的位置；S101: Each robot in the multi-robot system obtains an optimal pre-planned trajectory through the improved D* algorithm before running, and the robot predicts the position of the collision point in advance;
S102：在机器人的通信范围内发现其他机器人后通过协同控制算法进行环境的实时更新，机器人自主判断当前位置到目标点的最优路径的再规划。S102: After discovering other robots within the communication range of the robot, the environment is updated in real time through the collaborative control algorithm, and the robot independently judges the re-planning of the optimal path from the current position to the target point.
下面结合附图对本发明的技术方案作进一步的描述。The technical scheme of the present invention will be further described below in conjunction with the accompanying drawings.
当多机器人系统在特定的工作环境中执行多个并行任务时，工作环境已经成为一个动态的、未知的环境。考虑多机器人的分布式控制，即系统中没有中心控制器去进行协调，每个机器人在运行过程中独立自主地进行轨迹规划。在机器人的运动过程中，其他机器人均可看做是动态障碍物，因而多机器人的轨迹规划问题可划分为单个机器人的轨迹规划问题。与传统的动态障碍物不同之处在于，充分利用机器人之间存在的信息交互来完成多机器人间的避碰。When a multi-robot system performs multiple parallel tasks in a specific work environment, the work environment has become a dynamic and unknown environment. Consider the distributed control of multi-robots, that is, there is no central controller to coordinate in the system, and each robot independently performs trajectory planning during operation. During the movement of the robot, other robots can be regarded as dynamic obstacles, so the trajectory planning problem of multi-robots can be divided into the trajectory planning problem of a single robot. The difference from traditional dynamic obstacles is that it makes full use of the information interaction between robots to complete the collision avoidance between multiple robots.
本发明将滑模控制和预测控制的思想相结合，核心算法使用改进后的D*算法，提出一种新的控制算法即Sliding Mode D*算法。多机器人系统里的每一个机器人在运行前通过改进的D*算法得到一条最优的预规划轨迹，机器人有一个通信范围便于提前预测碰撞点的位置，在机器人的通信范围内发现其他机器人后通过协同控制算法进行环境的实时更新，便于机器人自主判断并执行当前位置到目标点的最优路径的再规划。其中协同控制算法包括避碰预测策略和避碰协调策略。SMD*算法的流程图如图2所示：The invention combines the ideas of sliding mode control and predictive control, uses the improved D* algorithm as the core algorithm, and proposes a new control algorithm, that is, the Sliding Mode D* algorithm. Each robot in the multi-robot system obtains an optimal pre-planned trajectory through the improved D* algorithm before running. The robot has a communication range to predict the position of the collision point in advance. After finding other robots within the communication range of the robot, pass The collaborative control algorithm updates the environment in real time, which is convenient for the robot to independently judge and execute the replanning of the optimal path from the current position to the target point. The cooperative control algorithm includes collision avoidance prediction strategy and collision avoidance coordination strategy. The flowchart of the SMD* algorithm is shown in Figure 2:
1、D*算法具体描述：1. The specific description of the D* algorithm:
路径规划的目的是将机器人从起始位置移动到目标位置，使得它避免所有障碍并且最小化正成本度量标准(例如，遍历的长度、运行的时间)。问题空间可以表示为一组状态，表示通过方向弧连接的机器人位置，每个方向弧具有相关的成本。机器人在特定状态下启动并跨越弧线(产生遍历成本)移动到其他状态，直到到达目标状态，表示为G。除G以外，每个状态X具有指向下一个状态的反向指针，表示为b(X)＝Y。D*使用反向指针来表示指向目标的路径。从状态Y到状态X所穿过的弧成本是一个正数，由弧成本函数c(X,Y)给出。如果Y没有到达X的弧，则c(X,Y)是未定义的。如果c(X,Y)是定义的，则两个状态X和Y在空间中是相邻的。The goal of path planning is to move the robot from a starting position to a goal position such that it avoids all obstacles and minimizes a positive cost metric (eg, length of traversal, time to run). The problem space can be represented as a set of states representing robot positions connected by direction arcs, each with an associated cost. The robot starts at a particular state and moves across an arc (incurring a traversal cost) to other states until it reaches a goal state, denoted G. Each state X, except G, has a back pointer to the next state, denoted b(X)=Y. D* uses back pointers to represent paths to targets. The arc cost traversed from state Y to state X is a positive number given by the arc cost function c(X,Y). If Y has no arc to X, then c(X,Y) is undefined. If c(X,Y) is defined, then two states X and Y are adjacent in space.
与A*一样，D*算法的实际代价由两部分之和组成，即已经付出的代价和预估的代价，如式(1)所示：Like A*, the actual cost of the D* algorithm consists of the sum of two parts, that is, the cost already paid and the estimated cost, as shown in formula (1):
f(n)＝g(n)+h(n) (1)f(n)=g(n)+h(n) (1)
式中：f(n)是节点的估计代价函数，g(n)是从起始点S到当前节点n的实际代价值，h(n)是当前节点n到终止位置G的估计代价值。启发式函数h(n)要满足相容性条件：即不能高于当前节点n到终止位置的实际最小费用，确保可以得到最优路径。在本发明中，启发函数采用欧氏距离。H的计算过程，忽略了一切可能存在的障碍物，是对剩余距离的估算值。In the formula: f(n) is the estimated cost function of the node, g(n) is the actual cost value from the starting point S to the current node n, h(n) is the estimated cost value from the current node n to the end position G. The heuristic function h(n) must satisfy the compatibility condition: that is, it cannot be higher than the actual minimum cost from the current node n to the terminal position, so as to ensure that the optimal path can be obtained. In the present invention, the heuristic function adopts Euclidean distance. The calculation process of H, ignoring all possible obstacles, is an estimate of the remaining distance.
同时，D*算法维护一个状态的OPEN列表。该列表用于传播有关弧成本函数更改的信息，并计算空间中各个状态的路径成本。每一个状态X都有一个关联的标签记为t(X)，如式(2)所示：At the same time, the D* algorithm maintains an OPEN list of states. This list is used to propagate information about changes in arc cost functions and to compute path costs to states in the space. Each state X has an associated label denoted as t(X), as shown in equation (2):
对于每个状态X，D*维持从X到G的一个弧成本之和的估计值，由路径成本函数h(G,X)给出。在给定适当条件的情况下，该估计值相当于从X到G的最优(最小)成本，通过隐函数o(G,X)给出。对于OPEN列表中的每个状态X(t(X)＝OPEN)，键函数k(G,X)定义为修正前的h(G,X)的最小值，如式(3)所示。并且因为X在OPEN列表上，所有值都由h(G,X)假定；For each state X, D* maintains an estimate of the sum of the costs of an arc from X to G, given by the path cost function h(G,X). This estimate is equivalent to the optimal (minimum) cost from X to G, given the appropriate conditions, given by the implicit function o(G,X). For each state X (t(X)=OPEN) in the OPEN list, the key function k(G,X) is defined as the minimum value of h(G,X) before modification, as shown in formula (3). And since X is on the OPEN list, all values are assumed by h(G,X);
k(G,X)＝min[h(G,X),X∈OPEN] (3)k(G,X)=min[h(G,X),X∈OPEN] (3)
键函数将列表上的状态X分为两种类型：RAISE状态，如果k(G,X)＜h(G,X)；LOWER状态，如果k(G,X)＝h(G,X)。D*使用OPEN列表上的RAISE状态来传播关于路径成本增加的信息(例如，由于弧成本的增加)，用LOWER状态传播关于路径成本降低的信息的状态(例如，由于降低的弧成本或能够到达目标位置的新路径)。通过从OPEN列表中重复不断地去除状态来进行传播信息。每次从OPEN列表中移除一个状态时，就会通过成本更改扩展到邻居状态。这些邻居依次被放在OPEN列表上去继续该过程。The key function divides the state X on the list into two types: RAISE state, if k(G,X)<h(G,X); LOWER state, if k(G,X)=h(G,X). D* uses the RAISE state on the OPEN list to propagate information about path cost increases (e.g., due to increased arc costs), and the LOWER state to propagate information about path cost decreases (e.g., due to reduced arc costs or being reachable new path to the target location). Information is propagated by repeatedly removing state from the OPEN list. Every time a state is removed from the OPEN list, it is extended to neighbor states with a cost change. These neighbors are in turn placed on the OPEN list to continue the process.
OPEN列表中的状态按键函数值进行排序。参数kmin被定义为min(k(X))，对于OPEN列表中的所有X，即t(X)＝OPEN。参数kmin代表D*中一个重要的阈值：路径成本小于或等于kmin是最优的，而大于kmin的则可能不是最优的。参数kold被定义为等于最近从OPEN列表中移除状态之前的参数kmin。如果没有移除任何状态，则kold未定义。The states in the OPEN list are sorted by key function value. The parameter kmin is defined as min(k(X)), ie t(X)=OPEN for all X in the OPEN list. The parameter kmin represents an important threshold in D*: path costs less than or equal to kmin are optimal, while those greater than kmin may not be optimal. The parameter kold is defined to be equal to the parameter kmin before the state was most recently removed from the OPEN list. If no state is removed, kold is undefined.
D*算法的搜索方向与A*算法相反，其为从终止位置G开始搜索直到找到起始位置S。搜索之前进行初始化，将所有状态的标签设置为new，h(G)设置为0，并且将G放置在OPEN列表中。创建open列表，其算法流程图如图2所示，重复执行直到t(S)＝CLOSED。此时可能建立一个最优序列{Y}，机器人遵循序列中的后指针向着目标位置前进。The search direction of the D* algorithm is opposite to that of the A* algorithm, which starts searching from the end position G until finding the start position S. Initialize before searching, label all states Set to new, h(G) is set to 0, and G is placed in the OPEN list. Create an open list, the algorithm flow chart of which is shown in Figure 2, and execute repeatedly until t(S)=CLOSED. At this time, an optimal sequence {Y} may be established, and the robot follows the rear pointer in the sequence to move towards the target position.
1.1改进D*算法的思想1.1 Idea of Improving D* Algorithm
传统的D*算法维护一个状态的OPEN列表。该列表用于传播有关弧成本函数更改的信息，并计算空间中各个状态的路径成本。t(x)＝CLOSED,x∈{Y}的最优序列{Y}里的状态均是闭合的，避免了机器人走“回头路”。在多机器人系统中，工作环境相对更加复杂和多变。当两个机器人在通信范围内预测到会发生碰撞时，会启动避碰策略，机器人所有走过的栅格位置状态均是闭合的，若周围的其他栅格都不能通行时，则会导致两个机器人卡死在当前位置。The traditional D* algorithm maintains an OPEN list of states. This list is used to propagate information about changes in arc cost functions and to compute path costs to states in the space. t(x)=CLOSED, the states in the optimal sequence {Y} of x∈{Y} are all closed, which prevents the robot from going back. In a multi-robot system, the working environment is relatively more complex and changeable. When two robots predict that a collision will occur within the communication range, the collision avoidance strategy will be activated. All the grid positions that the robots have passed are closed. A robot is stuck at the current position.
针对多机器人轨迹规划过程中出现的局部无解的问题，对D*算法进行改进，引入一个pass列表，如算法1所示：该列表用于存储机器人已运行轨迹的最新的N步位置，随着机器人的不断前进，pass列表进行实时更新。Aiming at the local unsolvable problem in the process of multi-robot trajectory planning, the D* algorithm is improved, and a pass list is introduced, as shown in Algorithm 1: this list is used to store the latest N-step position of the robot’s trajectory, and then As the robot continues to advance, the pass list is updated in real time.
引入了pass列表的概念后，使得机器人在运行过程中有了“退路”，避免在复杂情况下出现两个机器人卡死在某个位置导致轨迹的实时规划失败。After introducing the concept of the pass list, the robot has a "retreat" during the operation process, avoiding the failure of real-time planning of the trajectory caused by two robots stuck in a certain position in complex situations.
2.机器人间的碰撞类型分析2. Analysis of collision types between robots
多机器人系统的工作环境利用栅格法进行了离散化，每个机器人的预规化轨迹可以用一个栅格序列Pi来表示。机器人之间不发生碰撞，则要保证在任一时刻t，不会出现两个或两个以上的机器人在同一个栅格内。即Pi(t)≠Pj(t)，其中Pi(t)表示t时刻机器人i的位置，Pj(t)表示t时刻机器人j的位置。用一维数组array[n1]和array[n2]分别存储机器人i和机器人j的预规划轨迹信息，数组内的每一个元素表示每一时刻机器人所处的位置。则机器人i和机器人j发生碰撞的充分必要条件可表示为：The working environment of the multi-robot system is discretized by the grid method, and the pre-planned trajectory of each robot can be represented by a grid sequence Pi . If there is no collision between robots, it must be ensured that at any time t, no two or more robots will appear in the same grid. That is, Pi (t)≠Pj (t), where Pi (t) represents the position of robot i at time t, and Pj (t) represents the position of robot j at time t. One-dimensional arrays array[n1] and array[n2] are used to store the pre-planned trajectory information of robot i and robot j respectively, and each element in the array represents the position of the robot at each moment. Then the sufficient and necessary conditions for robot i and robot j to collide can be expressed as:
对任一时刻t∈[0,max(n1,n2)]且t∈Z，存在Pi(t)＝Pj(t)。For any time t∈[0,max(n1,n2)] and t∈Z, there exists Pi (t)=Pj (t).
上述在同一个位置发生碰撞的类型简称为同位碰撞。The above type of collision at the same position is referred to as collocation collision.
针对栅格环境的特殊性，需要考虑另一种碰撞类型：交叉碰撞。交叉碰撞指两个机器人的运行速度方向夹角为90度，且正向延长线有交点。机器人两种碰撞类型示意图如图4所示：For the particularity of the grid environment, another type of collision needs to be considered: cross collision. Cross-collision means that the angle between the running speed directions of two robots is 90 degrees, and there is an intersection point between the forward extension lines. The schematic diagram of the two collision types of the robot is shown in Figure 4:
为了保证算法的可靠性，针对不同的碰撞类型采取不同的避碰策略。对于同位碰撞类型，将碰撞点设置为静态障碍物。对于交叉碰撞类型，至少将彼此交叉的四个栅格设置为静态障碍物，同时将交叉前一时刻的机器人位置设置为静态障碍物。示意图如图5所示：In order to ensure the reliability of the algorithm, different collision avoidance strategies are adopted for different types of collisions. For Collision Type, set the collision point to be a static obstacle. For the intersection collision type, at least four grids that intersect with each other are set as static obstacles, and the position of the robot at the moment before the intersection is set as a static obstacle. The schematic diagram is shown in Figure 5:
3.机器人间的碰撞预测策略3. Collision prediction strategy between robots
为了更好地实现机器人的避碰，在机器人会发生碰撞之前应该提前预测碰撞点的位置，进行环境信息的局部更新，便于单个机器人进行后续的轨迹规划。单个机器人在自己的通信范围内发现可以与之进行通信的其他机器人后，会尝试与其进行信息交互来获取其他机器人未来三个时刻的运行位置，并与自己的同一时刻的运行位置进行比较，判断是否会发生碰撞。如果不会发生碰撞，机器人继续前行；若会发生碰撞，确定碰撞类型并实行机器人间的避碰策略。下面详细描述该碰撞预测策略。In order to better realize the collision avoidance of the robot, the position of the collision point should be predicted in advance before the robot will collide, and the local update of the environmental information should be performed to facilitate the subsequent trajectory planning of a single robot. After a single robot finds other robots that can communicate with it within its own communication range, it will try to interact with it to obtain the running position of other robots at three moments in the future, and compare it with its own running position at the same time to judge Whether a collision will occur. If there will be no collision, the robot will continue to move forward; if there will be a collision, determine the type of collision and implement the collision avoidance strategy between the robots. The collision prediction strategy is described in detail below.
当机器人Ri在其通信范围内发现可以与机器人Rj进行信息交互时，其预测策略如下：When the robot Ri finds that it can interact with the robot Rj within its communication range, its prediction strategy is as follows:
Step1：机器人Ri在t时刻与机器人Rj进行信息交互，获取到机器人Rj的Pj(t+1)、Pj(t+2)和Pj(t+3)，其中Pj(t+1)、Pj(t+2)和Pj(t+3)分别代表机器人Rj未来三个时刻的运行位置；Step1: Robot Ri interacts with robot Rj at time t, and obtains Pj (t+1), Pj (t+2) and Pj (t+3) of robot Rj , where Pj ( t+1), Pj (t+2) and Pj (t+3) respectively represent the running positions of the robot Rj at three moments in the future;
Step2：机器人Ri将获取到的信息与Pi(t+1)、Pi(t+2)和Pi(t+3)进行比较，其中Pi(t+1)、Pi(t+2)和Pi(t+3)分别代表机器人Ri未来三个时刻的运行位置；Step2: The robot Ri compares the acquired information with Pi (t+1), Pi (t+2) and Pi (t+3), where Pi (t+1), Pi (t +2) and Pi (t+3) respectively represent the running positions of the robot Ri at three moments in the future;
Step3：若判定结果为不会发生碰撞，则机器人继续沿着预规划轨迹前行；Step3: If the judgment result is that there will be no collision, the robot will continue to move forward along the pre-planned trajectory;
Step4：若判定结果为会发生碰撞，则确定碰撞类型，并将对应的碰撞位置设定为静态障碍物，将其他机器人设置为动态障碍物，更新单个机器人的运行环境。同时启动机器人间的避碰策略。Step4: If the judgment result is that a collision will occur, determine the type of collision, set the corresponding collision position as a static obstacle, set other robots as dynamic obstacles, and update the operating environment of a single robot. At the same time start the collision avoidance strategy between the robots.
4.机器人间的避碰协调策略4. Collision avoidance coordination strategy between robots
在多机器人系统中，当机器人Ri和机器人Rj的运行距离越来越接近直至在彼此的通信范围内时，机器人之间通过信息交互判断未来的轨迹中是否存在碰撞点，通过碰撞点的搜索算法找到碰撞位置，将碰撞位置暂时标记为静态障碍物，针对会发生碰撞的机器人进行各自工作环境的实时更新并存储环境信息。考虑到的优化目标是轨迹长度，对传统的D*算法在动态环境中遇到路径成本变化后进行全局重规划的思想进行改进，发生碰撞的机器人Ri和机器人Rj进行轨迹的重新规划，规划一条从其各自的当前位置到其各自的目标位置的最优路径，这条轨迹保证了机器人路径的实时规划，并且在保证避碰的前提下依然是全局最优的。为了不浪费碰撞点位置的最优性，采取增量决策法再次进行机器人之间的信息交互。计算各个机器人规划的新路径相对于其预规划路径的增量，从而确定按照新规划路径运动的机器人。假设机器人Ri的轨迹增量为ΔPi，机器人Rj的轨迹增量为ΔPj：若ΔPi＞ΔPj，则机器人Rj沿着新规划的轨迹运行，而机器人Ri沿着预规划的轨迹继续运行；若ΔPi＜ΔPj，则机器人Ri沿着新规划的轨迹运行，而机器人Rj沿着预规划的轨迹继续运行；若ΔPi＝ΔPj，则随机选取一个机器人沿着新规划的轨迹运行，而另一个机器人沿着预规划的轨迹继续运行。In a multi-robot system, when the running distance of the robot Ri and the robot Rj is getting closer until they are within the communication range of each other, the robots judge whether there is a collision point in the future trajectory through information interaction, and through the collision point The search algorithm finds the collision location, temporarily marks the collision location as a static obstacle, and updates and stores the environment information in real time for the respective working environments of the robots that may collide. Considering that the optimization target is the trajectory length, the traditional D* algorithm is improved on the idea of global re-planning after encountering path cost changes in a dynamic environment. Robots Ri and Rj that collide perform trajectory re-planning, Plan an optimal path from their respective current positions to their respective target positions. This trajectory ensures the real-time planning of the robot path, and is still globally optimal under the premise of ensuring collision avoidance. In order not to waste the optimality of the position of the collision point, the incremental decision-making method is adopted to carry out the information interaction between the robots again. Calculate the increment of the new path planned by each robot relative to its pre-planned path, so as to determine the robot moving according to the newly planned path. Suppose the trajectory increment of robot Ri is ΔPi , and the trajectory increment of robot Rj is ΔPj : if ΔPi > ΔPj , then robot Rj runs along the newly planned trajectory, while robot Ri follows the pre-planned trajectory If ΔPi < ΔPj , the robot Ri will run along the newly planned trajectory, and the robot Rj will continue to run along the pre-planned trajectory; if ΔPi = ΔPj , a robot will be randomly selected along the The robot runs along the newly planned trajectory, while the other robot continues to run along the pre-planned trajectory.
考虑到碰撞位置为某一个机器人的终止位置时，改变上述策略。此时只需更新另一个机器人的工作环境，将碰撞点设置为静态障碍物，重新规划当前位置到终止位置的最优轨迹，碰撞点为终止位置的机器人沿着预规划的轨迹继续前进。下面详细描述该避碰策略。Considering that the collision position is the end position of a certain robot, change the above strategy. At this time, it is only necessary to update the working environment of another robot, set the collision point as a static obstacle, and re-plan the optimal trajectory from the current position to the end position, and the robot whose collision point is the end position continues to move forward along the pre-planned trajectory. The collision avoidance strategy is described in detail below.
利用提出的机器人间的碰撞预测策略，预测到机器人Ri和机器人Rj在某一时刻t即将发生碰撞，此时机器人的避碰策略具体如下所示：Using the proposed collision prediction strategy between robots, it is predicted that the robot Ri and the robot Rj will collide at a certain moment t. At this time, the robot’s collision avoidance strategy is as follows:
Step1：若碰撞点为其中一个机器人的终止位置，假设为机器人Ri，则执行Step2，否则依次执行Step3和Step4；Step1: If the collision point is the end position of one of the robots, assuming it is the robot Ri , then execute Step2, otherwise execute Step3 and Step4 in sequence;
Step2：机器人Rj进行环境信息的实时更新和存储，将碰撞点视为静态障碍物，利用改进的D*算法规划当前位置到目标位置的最优轨迹；机器人Ri继续沿着预规划的轨迹前进；Step2: The robot Rj updates and stores the environmental information in real time, regards the collision point as a static obstacle, and uses the improved D* algorithm to plan the optimal trajectory from the current position to the target position; the robot Ri continues to follow the pre-planned trajectory go ahead;
Step3：机器人Ri和机器人Rj进行环境信息的实时更新和存储，将其他机器人视为动态障碍物，将碰撞点视为静态障碍物，利用改进的D*算法规划当前位置到目标位置的最优轨迹；Step3: Robot Ri and robot Rj update and store environmental information in real time, regard other robots as dynamic obstacles, regard collision points as static obstacles, and use the improved D* algorithm to plan the shortest path from the current position to the target position. Excellent trajectory;
Step4:比较机器人的轨迹增量：Step4: Compare the trajectory increment of the robot:
若ΔPi＞ΔPj，则机器人Rj沿着新规划的轨迹运行，而机器人Ri沿着预规划的轨迹继续运行；If ΔPi > ΔPj , the robot Rj runs along the newly planned trajectory, and the robot Ri continues to run along the pre-planned trajectory;
若ΔPi＜ΔPj，则机器人Ri沿着新规划的轨迹运行，而机器人Rj沿着预规划的轨迹继续运行；If ΔPi <ΔPj , the robot Ri runs along the newly planned trajectory, and the robot Rj continues to run along the pre-planned trajectory;
若ΔPi＝ΔPj，令ranNum＝random(0，1)，若ranNum∈[0,0.5]，则机器人Rj沿着新规划的轨迹运行，而机器人Ri沿着预规划的轨迹继续运行。If ΔPi =ΔPj , let ranNum=random(0,1), if ranNum∈[0,0.5], then the robot Rj runs along the newly planned trajectory, and the robot Ri continues to run along the pre-planned trajectory .
考虑到一些复杂和特殊的情况，如其中一个机器人或是两个机器人出现当前位置到目标位置的轨迹再规划无解的问题，针对上述避碰策略进行完善：Considering some complex and special situations, such as the unsolvable problem of one robot or two robots having a trajectory from the current position to the target position, the above-mentioned collision avoidance strategy is improved:
若机器人Ri和机器人Rj中有一个未能规划出当前位置到目标位置的最优轨迹，则设置其增量为-1，再进行上述Step2的比较。If one of the robot Ri and the robot Rj fails to plan the optimal trajectory from the current position to the target position, set its increment to -1, and then perform the comparison of Step 2 above.
若两个机器人都未规划出当前位置到目标位置的最优轨迹，则随机选择一个机器人，读取pass列表的最新位置并沿此位置回退一步，并与环境中其他机器人进行信息交互确保回退操作不能与其他机器人发生碰撞。另一个机器人则沿着预规划的轨迹继续前进。If neither robot plans the optimal trajectory from the current position to the target position, a robot is randomly selected, reads the latest position in the pass list and takes a step back along this position, and interacts with other robots in the environment to ensure the return path. The retreat operation cannot collide with other robots. The other robot continues along the pre-planned trajectory.
下面结合具体实施例方式对本发明的技术方案作进一步的描述。The technical solutions of the present invention will be further described below in conjunction with specific embodiments.
1.机器人的通信范围1. The communication range of the robot
如图6所示，机器人R1在P25时，它的通信范围用栅格表示为P1～P24和P26～P49，即机器人R1可以与在栅格P1～P24和P26～P49位置的任意其他机器人进行信息交互。As shown in Figure 6, when robot R1 is at P25 , its communication range is represented by grids as P1 ~ P24 and P26 ~ P49 , that is, robot R1 can communicate with grids P1 ~ P24 and P26 Any other robot at position ~P49 performs information exchange.
单机器人具有以下特征：A single robot has the following characteristics:
(1)信息存储及更新能力：单机器人可以存储离散后的环境信息，以及更新后的环境信息；(1) Information storage and update capabilities: a single robot can store discrete environmental information and updated environmental information;
(2)轨迹规划能力：单机器人可以根据更新后的环境信息规划后续的运行轨迹；(2) Trajectory planning ability: A single robot can plan subsequent running trajectories according to the updated environmental information;
(3)通信能力：机器人之间需要进行协商，因此单个机器人应该具备信息交互能力。(3) Communication capability: Negotiation between robots is required, so a single robot should have information interaction capability.
2.实例分析2. Example analysis
在多机器人运动之前，工作环境是静态的，采用栅格法将工作区域离散为二维网格图，通过每个维度的块数指定工作空间的大小，每个块都有一个唯一的标识符Pi,j，其中i和j分表代表块的横纵坐标。如图7所示，工作环境被离散为30×20个小方格，空白方格为可行区域，黑色方格为不可行区域即静态障碍物。每个机器人在运动之前通过D*算法得到一条避开障碍物的最优的预规划轨迹。机器人R1的预规划轨迹序列为：Before multi-robot movement, the working environment is static. The grid method is used to discretize the working area into a two-dimensional grid map. The size of the working space is specified by the number of blocks in each dimension, and each block has a unique identifier. Pi,j , where i and j represent the horizontal and vertical coordinates of the block. As shown in Figure 7, the working environment is discretized into 30×20 small squares, the blank squares are feasible areas, and the black squares are infeasible areas, that is, static obstacles. Each robot obtains an optimal pre-planned trajectory avoiding obstacles through the D* algorithm before moving. The pre-planned trajectory sequence of robot R1 is:
P7,15→P8,15→P9,15→P10,15→P11,15→P12,15→P13,15→P14,15→P15,14→P16,13→P17,12→P7,15 →P8,15 →P9,15 →P10,15 →P11,15 →P12,15 →P13,15 →P14,15 →P15,14 →P16,13 → P17,12 →
P18,11→P19,10→P20,9→P21,9→P22,8→P23,7→P24,6→P25,5P18,11 →P19,10 →P20,9 →P21,9 →P22,8 →P23,7 →P24,6 →P25,5
机器人R2的预规划轨迹序列为：The pre-planned trajectory sequence of robot R2 is:
P7,5→P8,5→P9,5→P10,6→P11,7→P12,8→P13,9→P14,10→P15,11→P16,11→P17,11→P7,5 →P8,5 →P9,5 →P10,6 →P11,7 →P12,8 →P13,9 →P14,10 →P15,11 →P16,11 → P17,11 →
P18,12→P19,13→P20,14→P21,14→P22,14→P23,14→P24,14→P25,15P18,12 →P19,13 →P20,14 →P21,14 →P22,14 →P23,14 →P24,14 →P25,15
机器人R3的预规划轨迹序列为：The pre-planned trajectory sequence of robot R3 is:
P4,3→P5,3→P6,3→P7,3→P8,3→P9,3→P10,3→P11,3→P12,3→P13,3→P14,4P15,5→P16,5→P4,3 →P5,3 →P6,3 →P7,3 →P8,3 →P9,3 →P10,3 →P11,3 →P12,3 →P13,3 → P14,4 P15,5 →P16,5 →
P17,5→P18,5→P19,5→P20,5→P21,5→P22,5→P23,5→P24,5→P25,5→P26,5→P27,6→P28,7P17,5 →P18,5 →P19,5 →P20,5 →P21,5 →P22,5 →P23,5 →P24,5 →P25,5 →P26,5 → P27,6 →P28,7
图8所示为多机器人系统里的每一个机器人沿着自己预规划的轨迹开始前进，每运动一步都更新一下pass列表。在当前t时刻，机器人R1和R2在彼此的通信范围内可以进行信息交互提前预测是否会发生碰撞，其预测策略如下：Figure 8 shows that each robot in the multi-robot system starts to move forward along its pre-planned trajectory, and the pass list is updated at each movement step. At the current time t, the robots R1 and R2 can exchange information within the communication range of each other and predict whether a collision will occur in advance. The prediction strategy is as follows:
Step1：机器人R1在t时刻与机器人R2进行信息交互，获取到机器人R2的未来三个时刻的运行位置P2(t+1)、P2(t+2)和P2(t+3)分别为：P16,11、P17,11和P18,12；Step1: The robot R1 interacts with the robot R2 at time t, and obtains the operating positions P2 (t+1), P2 (t+2) and P2 (t+3) of the robot R2 at three moments in the future, respectively For: P16,11 , P17,11 and P18,12 ;
Step2：机器人R1将获取到的信息与自己未来三个时刻的运行位置P1(t+1)、P2(t+2)和P1(t+3)进行比较，其中P1(t+1)、P1(t+2)和P1(t+3)分别为：P16,13、P17,12和P18,11；Step2: The robot R1 compares the acquired information with its running positions P1 (t+1), P2 (t+2) and P1 (t+3) at three moments in the future, where P1 (t+ 1), P1 (t+2) and P1 (t+3) are respectively: P16,13 , P17,12 and P18,11 ;
Step3：机器人R2与机器人R1的通信同Step1和Step2，其信息交换是相互的、同步的。Step3: The communication between robot R2 and robot R1 is the same as Step1 and Step2, and the information exchange is mutual and synchronous.
Step4：经过判断，两个机器人在t+2和t+3时刻会发生交叉碰撞，则机器人R1和R2会更新各自的运行环境，将对应的碰撞位置和碰撞前一刻的位置均设定为静态障碍物，将其他机器人设置为动态障碍物。同时启动机器人间的避碰策略。Step4: After judging, the two robots will cross-collision at time t+2 and t+3, then robots R1 and R2 will update their respective operating environments, and set the corresponding collision position and the position immediately before the collision as static Obstacles, set other robots as dynamic obstacles. At the same time start the collision avoidance strategy between the robots.
图9所示，机器人R1与机器人R2在信息交互后更新了各自的工作环境。由于的多机器人系统是分布式的，没有任何中心控制器，因此每个机器人的轨迹规划都是相互独立的。机器人R1与机器人R2运用改进后的D*算法规划从当前t时刻所在位置到目标点的最优轨迹，图9展示了机器人各自进行规划轨迹的某两个时刻的位置。此轨迹相对于预规划轨迹是全局次优的，但避免了机器人间的碰撞，同时跳出了滚动窗口法局部最优的短板。此时机器人的避碰策略具体如下所示：As shown in FIG. 9 , the robot R1 and the robot R2 update their respective working environments after information interaction. Since the multi-robot system is distributed without any central controller, the trajectory planning of each robot is independent of each other. Robot R1 and robot R2 use the improved D* algorithm to plan the optimal trajectory from the current position at time t to the target point. Figure 9 shows the positions at two moments when the robots plan their respective trajectories. Compared with the pre-planned trajectory, this trajectory is globally suboptimal, but it avoids the collision between robots, and at the same time jumps out of the short board of the rolling window method's local optimum. At this time, the robot's collision avoidance strategy is as follows:
Step1：机器人R1和机器人R2进行环境信息的实时更新和存储，将其他机器人视为动态障碍物，将碰撞点视为静态障碍物，利用改进的D*算法规划当前位置到目标位置的最优轨迹；机器人R1规划的剩余轨迹序列为：Step1: Robot R1 and robot R2 update and store environmental information in real time, regard other robots as dynamic obstacles, regard collision points as static obstacles, and use the improved D* algorithm to plan the optimal trajectory from the current position to the target position ; The remaining trajectory sequence planned by robot R1 is:
P15,14→P16,14→P17,14→P18,14→P19,14→P20,14→P21,9→P21,14→P22,13→P23,12→P24,11→P15,14 →P16,14 →P17,14 →P18,14 →P19,14 →P20,14 →P21,9 →P21,14 →P22,13 →P23,12 → P24,11 →
P25,10→P25,9→P25,8→P25,7→P25,6→P25,5P25,10 →P25,9 →P25,8 →P25,7 →P25,6 →P25,5
机器人R2规划的剩余轨迹序列为：The remaining trajectory sequence planned by robot R2 is:
P15,11→P15,12→P15,13→P16,14→P17,14→P18,14→P19,15→P20,15→P21,15→P22,15→P23,15→P15,11 →P15,12 →P15,13 →P16,14 →P17,14 →P18,14 →P19,15 →P20,15 →P21,15 →P22,15 → P23,15 →
P24,15→P25,15P24,15 →P25,15
Step2:比较机器人的轨迹增量：ΔP1＞ΔP2，则机器人R2沿着新规划的轨迹运行，而机器人R1沿着预规划的轨迹继续运行。Step2: Compare the trajectory increment of the robot: ΔP1 > ΔP2 , then the robot R2 runs along the newly planned trajectory, and the robot R1 continues to run along the pre-planned trajectory.
图10所示为多机器人系统继续前进，更新pass列表。在t1时刻，机器人R3与R1在彼此的通信范围内，在进行信息交互后得知R3与R1在未来的3个时刻不会发生碰撞。此时机器人R3与R1继续沿着预规划的轨迹前进；Figure 10 shows that the multi-robot system continues to move forward and updates the pass list. At time t1, robots R3 and R1 are within the communication range of each other, and after information interaction, they know that R3 and R1 will not collide in the next three moments. At this time, the robots R3 and R1 continue to advance along the pre-planned trajectory;
图11所示为多机器人系统继续前进，更新pass列表。在t2时刻，机器人R3与R1依旧在彼此的通信范围内，在进行信息交互后得知R3与R1在t2+3时刻会发生同位碰撞。此时机器人的避碰策略具体如下所示：Figure 11 shows that the multi-robot system continues to move forward and updates the pass list. At time t2, robots R3 and R1 are still within the communication range of each other. After information interaction, it is known that R3 and R1 will collide at the same position at time t2+3. At this time, the robot's collision avoidance strategy is as follows:
Step1：碰撞位置P25,5是机器人R1的终止位置；Step1: Collision position P25,5 is the end position of robot R1;
Step2：机器人R3进行环境信息的实时更新和存储，将碰撞点视为静态障碍物，利用改进的D*算法规划当前位置到目标位置的最优轨迹；机器人R3规划的剩余轨迹序列为：Step2: The robot R3 updates and stores the environmental information in real time, regards the collision point as a static obstacle, and uses the improved D* algorithm to plan the optimal trajectory from the current position to the target position; the remaining trajectory sequence planned by the robot R3 is:
P23,5→P24,5→P25,6→P26,7→P27,7→P28,7P23,5 →P24,5 →P25,6 →P26,7 →P27,7 →P28,7
Step3：机器人R1继续沿着预规划的轨迹前进。Step3: Robot R1 continues to move forward along the pre-planned trajectory.
图12所示为多机器人系统运行的完整轨迹。在保证机器人间不发生碰撞的前提下，机器人的运行成本最优。Figure 12 shows the complete trajectory of the multi-robot system running. Under the premise of ensuring no collision between robots, the operating cost of the robot is optimal.
以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明的保护范围之内。The above descriptions are only preferred embodiments of the present invention, and are not intended to limit the present invention. Any modifications, equivalent replacements and improvements made within the spirit and principles of the present invention should be included in the protection of the present invention. within range.
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201910670027.4ACN110398967B (en) | 2019-07-24 | 2019-07-24 | A multi-robot cooperative trajectory information processing method using discretization method |
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201910670027.4ACN110398967B (en) | 2019-07-24 | 2019-07-24 | A multi-robot cooperative trajectory information processing method using discretization method |
| Publication Number | Publication Date |
|---|---|
| CN110398967Atrue CN110398967A (en) | 2019-11-01 |
| CN110398967B CN110398967B (en) | 2021-07-16 |
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201910670027.4AActiveCN110398967B (en) | 2019-07-24 | 2019-07-24 | A multi-robot cooperative trajectory information processing method using discretization method |
| Country | Link |
|---|---|
| CN (1) | CN110398967B (en) |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN111103887A (en)* | 2020-01-14 | 2020-05-05 | 大连理工大学 | Multi-sensor-based multi-mobile-robot scheduling system design method |
| CN111221318A (en)* | 2019-12-11 | 2020-06-02 | 中山大学 | Multi-robot state estimation method based on model predictive control algorithm |
| CN111317842A (en)* | 2020-03-31 | 2020-06-23 | 苏州酷卡环保科技有限公司 | A disinfection robot |
| CN111399543A (en)* | 2020-04-04 | 2020-07-10 | 西安爱生技术集团公司 | Same-region multi-collision-free air route planning method based on A-star algorithm |
| CN111474947A (en)* | 2020-05-07 | 2020-07-31 | 北京云迹科技有限公司 | Robot obstacle avoidance method, device and system |
| CN112327829A (en)* | 2020-10-15 | 2021-02-05 | 西安电子科技大学 | Distributed multi-robot cooperative motion control method, system, medium and application |
| CN112362063A (en)* | 2020-11-13 | 2021-02-12 | 四川大学 | Multi-robot path planning method and system based on collision type division |
| CN114326718A (en)* | 2021-12-14 | 2022-04-12 | 科沃斯商用机器人有限公司 | Map construction method, self-moving robot and storage medium |
| EP4141599A1 (en)* | 2021-08-30 | 2023-03-01 | Rapyuta Robotics Co., Ltd. | Multi-robot route planning |
| CN117863178A (en)* | 2023-12-29 | 2024-04-12 | 睿尔曼智能科技（北京）有限公司 | A multi-robot cascade system control method and device |
| CN119756408A (en)* | 2025-03-05 | 2025-04-04 | 云南农业大学 | Dynamic Programming Monitoring Method Based on Markov Model |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2011067621A1 (en)* | 2009-12-04 | 2011-06-09 | Toyota Jidosha Kabushiki Kaisha | Robot control system, motion data creation apparatus and its creating method |
| CN105094135A (en)* | 2015-09-03 | 2015-11-25 | 上海电机学院 | Distributed multi-robot map fusion system and fusion method |
| CN105302062A (en)* | 2015-10-15 | 2016-02-03 | 东南大学 | Task decoupling-based multi-robot collaboration welding path generation method |
| CN106325280A (en)* | 2016-10-20 | 2017-01-11 | 上海物景智能科技有限公司 | A multi-robot anti-collision method and system |
| CN106444739A (en)* | 2016-07-15 | 2017-02-22 | 鹿龙 | Multi-industrial-robot virtual offline co-simulation system and method |
| CN106777475A (en)* | 2016-11-17 | 2017-05-31 | 贵州大学 | A kind of injection machine arm dynamics synergy emulation method of confined space constraint |
| CN107728612A (en)* | 2017-09-12 | 2018-02-23 | 安徽胜佳和电子科技有限公司 | Identify that different crowd carries out method, storage device and the mobile terminal of advertisement pushing |
| CN108453746A (en)* | 2018-03-09 | 2018-08-28 | 齐齐哈尔大学 | Independently discovery techniques are cooperateed with the multirobot for negotiating to be combined |
| CN108469786A (en)* | 2018-01-26 | 2018-08-31 | 西安电子科技大学 | Extensive intelligent storage distribution radio frequency |
| CN108724188A (en)* | 2018-06-14 | 2018-11-02 | 西安电子科技大学 | A kind of multirobot cooperative motion control method |
| CN108776483A (en)* | 2018-08-16 | 2018-11-09 | 圆通速递有限公司 | AGV paths planning methods and system based on ant group algorithm and multiple agent Q study |
| CN108958235A (en)* | 2017-05-18 | 2018-12-07 | 库卡匈牙利有限责任公司 | robot motion planning |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2011067621A1 (en)* | 2009-12-04 | 2011-06-09 | Toyota Jidosha Kabushiki Kaisha | Robot control system, motion data creation apparatus and its creating method |
| CN105094135A (en)* | 2015-09-03 | 2015-11-25 | 上海电机学院 | Distributed multi-robot map fusion system and fusion method |
| CN105302062A (en)* | 2015-10-15 | 2016-02-03 | 东南大学 | Task decoupling-based multi-robot collaboration welding path generation method |
| CN106444739A (en)* | 2016-07-15 | 2017-02-22 | 鹿龙 | Multi-industrial-robot virtual offline co-simulation system and method |
| CN106325280A (en)* | 2016-10-20 | 2017-01-11 | 上海物景智能科技有限公司 | A multi-robot anti-collision method and system |
| CN106777475A (en)* | 2016-11-17 | 2017-05-31 | 贵州大学 | A kind of injection machine arm dynamics synergy emulation method of confined space constraint |
| CN108958235A (en)* | 2017-05-18 | 2018-12-07 | 库卡匈牙利有限责任公司 | robot motion planning |
| CN107728612A (en)* | 2017-09-12 | 2018-02-23 | 安徽胜佳和电子科技有限公司 | Identify that different crowd carries out method, storage device and the mobile terminal of advertisement pushing |
| CN108469786A (en)* | 2018-01-26 | 2018-08-31 | 西安电子科技大学 | Extensive intelligent storage distribution radio frequency |
| CN108453746A (en)* | 2018-03-09 | 2018-08-28 | 齐齐哈尔大学 | Independently discovery techniques are cooperateed with the multirobot for negotiating to be combined |
| CN108724188A (en)* | 2018-06-14 | 2018-11-02 | 西安电子科技大学 | A kind of multirobot cooperative motion control method |
| CN108776483A (en)* | 2018-08-16 | 2018-11-09 | 圆通速递有限公司 | AGV paths planning methods and system based on ant group algorithm and multiple agent Q study |
| Title |
|---|
| ANNETT CHILIAN等: "Stereo Camera Based Navigation of Mobile Robots on Rough Terrain", 《THE 2009 IEEE/RSJ INTERNATIONAL CONFERENCE ON INTELLIGENT ROBOTS AND SYSTEMS》* |
| YUAN ZHOU等: "A distributed approach to robust control of multi-robot systems", 《AUTOMATICA》* |
| 任玉洁等: "基于平滑A*人工势场法的机器人动态路径规划", 《软件导刊》* |
| 刘亮: "自主移动机器人的路径规划与避碰研究", 《中国优秀硕士学位论文全文数据库 信息科技辑》* |
| 周远等: "分布式多机器人运动控制的离散事件系统方法", 《控制理论与应用》* |
| 李树军等: "双并联机器人协作的运动学建模", 《东北大学学报(自然科学版)》* |
| 霍凤财等: "移动机器人路径规划算法综述", 《吉林大学学报(信息科学版)》* |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN111221318B (en)* | 2019-12-11 | 2023-03-28 | 中山大学 | Multi-robot state estimation method based on model predictive control algorithm |
| CN111221318A (en)* | 2019-12-11 | 2020-06-02 | 中山大学 | Multi-robot state estimation method based on model predictive control algorithm |
| CN111103887B (en)* | 2020-01-14 | 2021-11-12 | 大连理工大学 | Multi-sensor-based multi-mobile-robot scheduling system design method |
| CN111103887A (en)* | 2020-01-14 | 2020-05-05 | 大连理工大学 | Multi-sensor-based multi-mobile-robot scheduling system design method |
| CN111317842A (en)* | 2020-03-31 | 2020-06-23 | 苏州酷卡环保科技有限公司 | A disinfection robot |
| CN111399543A (en)* | 2020-04-04 | 2020-07-10 | 西安爱生技术集团公司 | Same-region multi-collision-free air route planning method based on A-star algorithm |
| CN111474947A (en)* | 2020-05-07 | 2020-07-31 | 北京云迹科技有限公司 | Robot obstacle avoidance method, device and system |
| CN112327829A (en)* | 2020-10-15 | 2021-02-05 | 西安电子科技大学 | Distributed multi-robot cooperative motion control method, system, medium and application |
| CN112362063A (en)* | 2020-11-13 | 2021-02-12 | 四川大学 | Multi-robot path planning method and system based on collision type division |
| EP4141599A1 (en)* | 2021-08-30 | 2023-03-01 | Rapyuta Robotics Co., Ltd. | Multi-robot route planning |
| CN114326718A (en)* | 2021-12-14 | 2022-04-12 | 科沃斯商用机器人有限公司 | Map construction method, self-moving robot and storage medium |
| CN114326718B (en)* | 2021-12-14 | 2024-10-18 | 科沃斯商用机器人有限公司 | Map construction method, self-moving robot, and storage medium |
| CN117863178A (en)* | 2023-12-29 | 2024-04-12 | 睿尔曼智能科技（北京）有限公司 | A multi-robot cascade system control method and device |
| CN117863178B (en)* | 2023-12-29 | 2024-09-10 | 睿尔曼智能科技（北京）有限公司 | Multi-mechanical arm cascade system control method and device |
| CN119756408A (en)* | 2025-03-05 | 2025-04-04 | 云南农业大学 | Dynamic Programming Monitoring Method Based on Markov Model |
| CN119756408B (en)* | 2025-03-05 | 2025-04-29 | 云南农业大学 | Dynamic Programming Monitoring Method Based on Markov Model |
| Publication number | Publication date |
|---|---|
| CN110398967B (en) | 2021-07-16 |
| Publication | Publication Date | Title |
|---|---|---|
| CN110398967A (en) | A multi-robot cooperative trajectory information processing method using discretization method | |
| AU2010237608B2 (en) | Drill hole planning | |
| Lai et al. | Enhanced center constraint weighted A* algorithm for path planning of petrochemical inspection robot | |
| CN111007862A (en) | Path planning method for cooperative work of multiple AGVs | |
| CN116551703B (en) | Motion planning method based on machine learning in complex environment | |
| CN106840169B (en) | Improved method for robot path planning | |
| Guo et al. | Intelligent path planning for automated guided vehicles system based on topological map | |
| Peddi et al. | A data-driven framework for proactive intention-aware motion planning of a robot in a human environment | |
| CN117490711A (en) | Obstacle avoidance path planning method integrating artificial potential field method and D X Lite | |
| Gupta et al. | Intention-aware navigation in crowds with extended-space POMDP planning | |
| Herrero-Perez et al. | Decentralized coordination of autonomous agvs in flexible manufacturing systems | |
| Li et al. | Conflict-free and energy-efficient path planning for multi-robots based on priority free ant colony optimization | |
| Saska et al. | Roads sweeping by unmanned multi-vehicle formations | |
| Li et al. | UGV navigation in complex environment: an approach integrating security detection and obstacle avoidance control | |
| Lee et al. | Multi-Robot Formation Planning in Maze-like Environments Consisting of Narrow Passages Using Graph Search | |
| CN116974277A (en) | Automatic guiding forklift motion control method based on hybrid algorithm | |
| Dong et al. | Path Planning Based on A-Star and Dynamic Window Approach Algorithm for Wild Environment | |
| Tang et al. | An improved fusion algorithm of path planning for automated guided vehicle in storage system | |
| Chang-an et al. | Mobile robot path planning based on an improved rapidly-exploring random tree in unknown environment | |
| Liu et al. | Path Planning Optimization for Obstacle Avoidance in Unknown Environment | |
| Li | Robot trajectory planning based on the energy management strategy | |
| Abi-Char et al. | A collision-free path planning algorithm for non-complex ASRS using heuristic functions | |
| Liu et al. | Novel approach of the best path selection based on prior knowledge reinforcement learning | |
| Hanqing et al. | A Novel 3-Dimensional Crane Lifting Path Planning Method Based on Reinforcement Learning | |
| Zhang et al. | Scene Modeling of Autonomous Vehicles Avoiding Stationary and Moving Vehicles on Narrow Roads |
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |