[go: up one dir, main page]

CN115268429A - Path planning and control method - Google Patents

Path planning and control method Download PDF

Info

Publication number
CN115268429A
CN115268429A CN202210756476.2A CN202210756476A CN115268429A CN 115268429 A CN115268429 A CN 115268429A CN 202210756476 A CN202210756476 A CN 202210756476A CN 115268429 A CN115268429 A CN 115268429A
Authority
CN
China
Prior art keywords
time
robot
node
time window
list
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Pending
Application number
CN202210756476.2A
Other languages
Chinese (zh)
Inventor
周航
葛翔
杨晓光
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Suzhou Agv Robot Co ltd
Original Assignee
Suzhou Agv Robot Co ltd
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Suzhou Agv Robot Co ltd filed Critical Suzhou Agv Robot Co ltd
Priority to CN202210756476.2A priority Critical patent/CN115268429A/en
Publication of CN115268429A publication Critical patent/CN115268429A/en
Pending legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G05—CONTROLLING; REGULATING
    • G05D—SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
    • G05D1/00—Control of position, course, altitude or attitude of land, water, air or space vehicles, e.g. using automatic pilots
    • G05D1/02—Control of position or course in two dimensions
    • G05D1/021—Control of position or course in two dimensions specially adapted to land vehicles
    • G05D1/0212—Control of position or course in two dimensions specially adapted to land vehicles with means for defining a desired trajectory
    • G05D1/0214—Control of position or course in two dimensions specially adapted to land vehicles with means for defining a desired trajectory in accordance with safety or protection criteria, e.g. avoiding hazardous areas

Landscapes

  • Engineering & Computer Science (AREA)
  • Aviation & Aerospace Engineering (AREA)
  • Radar, Positioning & Navigation (AREA)
  • Remote Sensing (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Automation & Control Theory (AREA)
  • Manipulator (AREA)

Abstract

The invention discloses a path planning and control method, which comprises the steps of firstly finding out all road sections taking an initial point as a starting point, checking and calculating an idle time window of each road section, and finding out a node N with the minimum cost from an OPEN listlastNode NlastRemove from the OPEN list, add to the CLOSE list, and occupy node NlastThe idle time window of (c); find node NlastSelecting a child node N from the listnextIf child node NnextThe destination of the road section is a target point; judging child node NnextWhether the child node N is already in the OPEN list or notnextAdd to OPEN list; and successfully planning the path and adding a safe time window for the end point. According to the invention, a time window principle is added in a path planning algorithm, so that the robot is prevented from generating path conflict with other robots in the driving process, and if the terminal point of the robot is a narrow roadway, a reverse reservation path is also carried out on the terminal point.

Description

一种路径规划及管制方法A route planning and control method

技术领域technical field

本发明涉及移动机器人领域，特别涉及一种路径规划及管制方法。The invention relates to the field of mobile robots, in particular to a path planning and control method.

背景技术Background technique

在多辆移动机器人行驶过程中，为确保小车不会相撞，首先会对车辆行驶的路径进行规划，现阶段经常使用的方法为交通管制方法，交通管制基本原则是小车如果要驶入下一路段，那么下一路段的所有关联站点和所有关联路段不能被其他小车占用。现阶段主要采用A*路径规划方法，但在很多实际应用过程中，仍会出现路径死锁、车辆碰撞等现象。During the driving process of multiple mobile robots, in order to ensure that the cars will not collide, the path of the vehicles will be planned first. The method often used at this stage is the traffic control method. The basic principle of traffic control is that if the cars want to drive into the next section, then all associated sites and all associated sections of the next section cannot be occupied by other cars. At this stage, the A* path planning method is mainly used, but in many practical applications, there will still be path deadlocks, vehicle collisions and other phenomena.

发明内容Contents of the invention

本发明目的是：提供一种路径规划及管制方法，在路径规划算法中添加时间窗原理，防止机器人在行驶过程中与其他机器人发生路径冲突。The purpose of the present invention is to provide a path planning and control method, adding the time window principle to the path planning algorithm, so as to prevent the robot from conflicting with other robots during the driving process.

本发明的技术方案是：Technical scheme of the present invention is:

一种路径规划及管制方法，包括步骤：A path planning and control method, comprising the steps of:

S1、初始化：找出以初始点为起点的所有路段，并且验算每条路段的空闲时间窗，将时间窗Tstar＝0,

Figure RE-GDA0003874036330000011
的路段放入OPEN列表，其中path.lenth 为路段长度，v表示机器人行走的速度；S1. Initialization: find out all road sections starting from the initial point, and check the free time window of each road section, set the time window T star = 0,
Figure RE-GDA0003874036330000011
Put the road section into the OPEN list, where path.lenth is the length of the road section, and v represents the walking speed of the robot;

S2、从OPEN列表中找到代价最小的节点Nlast，代价包括到达时间、是否有空闲时间窗；将节点Nlast从OPEN列表中移除，加入到CLOSE列表中，并占用节点Nlast的空闲时间窗；S2. Find the node N last with the lowest cost from the OPEN list. The cost includes arrival time and whether there is an idle time window; remove node N last from the OPEN list, add it to the CLOSE list, and occupy the idle time of node N last window;

S3、找到节点Nlast的所有不发生冲突的子节点列表，从列表中选择一个子节点Nnext，若子节点Nnext的路段终点为目标点，跳到步骤S6；否则，继续下一步；若子节点列表为空，跳到步骤S2；S3. Find the list of all non-conflicting child nodes of node N last , select a child node N next from the list, if the end point of the road section of child node N next is the target point, skip to step S6; otherwise, continue to the next step; if the child node The list is empty, skip to step S2;

S4、判断子节点Nnext是否已在OPEN列表中，若不在，继续下一步；若在，再比较子节点Nnext的代价是否比原有的要小，若是，移除原有的节点，继续下一步，若不是，返回步骤S3；S4. Determine whether the child node N next is already in the OPEN list, if not, continue to the next step; if it is, then compare whether the cost of the child node N next is smaller than the original one, if so, remove the original node, and continue Next step, if not, return to step S3;

S5、将子节点Nnext添加至OPEN列表中，返回步骤S2；S5. Add child node N next to the OPEN list, and return to step S2;

S6、路径规划成功，并为终点添加一个安全时间窗。S6. The path planning is successful, and a safety time window is added to the end point.

优选的，如果机器人的终点为一个窄巷道，对终点进行反向预约路径：Preferably, if the end point of the robot is a narrow aisle, perform a reverse reservation path for the end point:

首先获取小车生成路径的终点所生成的节点，获取该节点对应的反向预约路径，预约到巷道出口点；First obtain the node generated by the end point of the path generated by the car, obtain the reverse reservation path corresponding to the node, and make a reservation to the roadway exit point;

再以小车终点所在的时间窗结束时间为起始时间，依次为预约路径添加时间窗。Then take the end time of the time window where the end point of the car is located as the starting time, and add time windows for the reservation path in turn.

优选的，子节点列表找寻方法包括：Preferably, the method for finding the child node list includes:

(1)通过地图，找到所有以当前机器人站点为起点的所有子路段列表，从中选择一条路段P_next执行以下操作；(1) Through the map, find all the sub-section lists starting from the current robot site, and select a section P_next to perform the following operations;

(2)判断P_next路段的终点是否与路径的起始点和目标点的区域类型相同，若不同，返回第(1)步，若相同，继续下一步；(2) Determine whether the end point of the P_next road section is the same as the starting point of the path and the area type of the target point, if different, return to step (1), if the same, continue to the next step;

(3)从P_next路段的空闲时间窗中选择一个时间窗TW进行以下操作， TW＝[a,b]，若已选择完毕，跳到第(1)步；(3) Select a time window TW from the free time window of the P_next road section to carry out the following operations, TW=[a, b], if the selection has been completed, jump to the (1) step;

(4)判断空闲时间窗TW的开始时间a是否小于机器人到达路段P_next 起始节点的时间c，如果小于，继续第(5)步；如果不小于，跳转第(6)步；(4) Determine whether the start time a of the free time window TW is less than the time c for the robot to reach the starting node of the road section P_next, if less, continue to step (5); if not less, skip to step (6);

(5)判断时间窗TW_1是否被时间窗TW包含：如果包含，即机器人通过P_next不被其他机器人干扰，进行第(9)步；如果不包含，即机器人通过 P_next会被其他机器人干扰，则返回第(3)步；(5) Determine whether the time window TW_1 is included in the time window TW: if it is included, that is, the robot will not be disturbed by other robots through P_next, go to step (9); if it is not included, that is, the robot will be interfered by other robots through P_next, then return step (3);

时间窗TW_1＝[c,d]，TW_1的起始时间c为机器人到达路段P_next起始节点的时间，时间长度d-c为机器人通过P_next路段的时间，其中机器人通过 P_next路段的时间＝P_next路段的长度/机器人行驶的速度；Time window TW_1=[c,d], the starting time c of TW_1 is the time when the robot arrives at the starting node of the road section P_next, and the time length d-c is the time for the robot to pass the road section P_next, where the time for the robot to pass the road section P_next=the length of the road section P_next / The speed at which the robot travels;

(6)判断时间窗TW_2是否能被TW包含，若是，即机器人在等待一段时间后，通过路段P_next，不被其他机器人干扰；若不是，即机器人在等待一段时间后，仍然无法通过路段P_next，会被其他机器人干扰，返回第(3)步；(6) Determine whether the time window TW_2 can be included in TW. If so, the robot will pass the road section P_next after waiting for a period of time without being disturbed by other robots; if not, that is, the robot will still be unable to pass the road section P_next after waiting for a period of time. Will be interfered by other robots, return to step (3);

时间窗TW_2＝[a,a+d-c],时间窗TW_2的起始时间为空闲时间窗TW的起始时间a，时间长度为机器人通过P_next路段的时间，即d-c，其中机器人通过P_next路段的时间＝P_next路段的长度/机器人行驶的速度；Time window TW_2=[a, a+d-c], the start time of time window TW_2 is the start time a of the free time window TW, and the time length is the time for the robot to pass through the P_next road section, that is, d-c, where the time for the robot to pass through the P_next road section ＝The length of P_next road section/the speed that robot travels;

(7)判断时间窗TW_3是否被机器人停靠的站点的空闲时间窗N_TW包含，若是，即机器人在站点等待时，不会与其他机器人发生干扰，进行下一步；若不是，即机器人在站点等待时，会与其他机器人发生干扰，返回第(3)步；(7) Determine whether the time window TW_3 is included by the idle time window N_TW of the station where the robot stops, if so, the robot will not interfere with other robots when it is waiting at the station, and proceed to the next step; if not, the robot is waiting at the station , will interfere with other robots, return to step (3);

时间窗TW_3＝[c,a]，即机器人在站点等待的时间窗，时间窗TW_3的起始时间为机器人到达路段P_next起始节点的时间，时间窗TW_3的结束时间为空闲时间窗TW的起始时间；Time window TW_3=[c, a], that is, the time window for the robot to wait at the station. The start time of time window TW_3 is the time when the robot arrives at the start node of road segment P_next, and the end time of time window TW_3 is the start of the idle time window TW start time;

(8)以(P_next,TW_2)生成节点Node_next,将Node_next添加至节点列表；(8) Generate node Node_next with (P_next, TW_2), add Node_next to the node list;

(9)以(P_next,TW_1)生成节点Node_next,将Node_next添加至节点列表；(9) Generate node Node_next with (P_next, TW_1), add Node_next to the node list;

(10)返回节点列表。(10) Return the node list.

步骤(6)中，机器人到达P_next路段起始节点时，P_next路段还有其他机器人通过，等待一段时间，其他机器人行驶过后，该机器人再行走。In step (6), when the robot arrives at the starting node of the P_next section, there are other robots passing through the P_next section. After waiting for a period of time, the robot will walk again after the other robots have passed.

本发明的优点是：The advantages of the present invention are:

本发明的路径规划及管制方法，在路径规划算法中添加时间窗原理，防止机器人在行驶过程中与其他机器人发生路径冲突，如果机器人的终点为一个窄巷道，还对终点进行反向预约路径，获取小车生成路径的终点所生成的节点，获取该节点对应的反向预约路径，预约到巷道出口点，以小车终点所在的时间窗结束时间为起始时间，依次为预约路径添加时间窗。In the path planning and control method of the present invention, the principle of time window is added to the path planning algorithm to prevent the robot from conflicting with other robots during the driving process. Obtain the node generated by the end point of the path generated by the car, obtain the reverse reservation path corresponding to the node, make a reservation to the exit point of the roadway, start with the end time of the time window where the end point of the car is located, and add time windows to the reservation path in turn.

具体实施方式Detailed ways

发明提出的路径规划及管制方法，其整体路径规划方法包括步骤：In the path planning and control method proposed by the invention, the overall path planning method includes steps:

S1、初始化：找出以初始点为起点的所有路段，并且验算每条路段的空闲时间窗，将时间窗Tstar＝0,

Figure RE-GDA0003874036330000031
的路段放入OPEN列表，其中path.lenth 为路段长度，v表示机器人行走的速度；S1. Initialization: find out all road sections starting from the initial point, and check the free time window of each road section, set the time window T star = 0,
Figure RE-GDA0003874036330000031
Put the road section into the OPEN list, where path.lenth is the length of the road section, and v represents the walking speed of the robot;

S2、从OPEN列表中找到代价最小的节点Nlast，代价包括到达时间、是否有空闲时间窗；将节点Nlast从OPEN列表中移除，加入到CLOSE列表中，并占用节点Nlast的空闲时间窗；S2. Find the node N last with the lowest cost from the OPEN list. The cost includes arrival time and whether there is an idle time window; remove node N last from the OPEN list, add it to the CLOSE list, and occupy the idle time of node N last window;

S3、找到节点Nlast的所有不发生冲突的子节点列表，从列表中选择一个子节点Nnext，若子节点Nnext的路段终点为目标点，跳到步骤S6；否则，继续下一步；若子节点列表为空，跳到步骤S2；S3. Find the list of all non-conflicting child nodes of node N last , select a child node N next from the list, if the end point of the road section of child node N next is the target point, skip to step S6; otherwise, continue to the next step; if the child node The list is empty, skip to step S2;

S4、判断子节点Nnext是否已在OPEN列表中，若不在，继续下一步；若在，再比较子节点Nnext的代价是否比原有的要小，若是，移除原有的节点，继续下一步，若不是，返回步骤S3；S4. Determine whether the child node N next is already in the OPEN list, if not, continue to the next step; if it is, then compare whether the cost of the child node N next is smaller than the original one, if so, remove the original node, and continue Next step, if not, return to step S3;

S5、将子节点Nnext添加至OPEN列表中，返回步骤S2；S5. Add child node N next to the OPEN list, and return to step S2;

S6、路径规划成功，并为终点添加一个安全时间窗，以防机器人停靠时，与其他机器行驶路径相冲突。S6. The path planning is successful, and a safety time window is added to the end point to prevent the robot from colliding with the driving path of other machines when it stops.

如果机器人的终点为一个窄巷道，对终点进行反向预约路径：If the end point of the robot is a narrow aisle, make a reverse reservation path for the end point:

首先获取小车生成路径的终点所生成的节点，获取该节点对应的反向预约路径，预约到巷道出口点；First obtain the node generated by the end point of the path generated by the car, obtain the reverse reservation path corresponding to the node, and make a reservation to the roadway exit point;

再以小车终点所在的时间窗结束时间为起始时间，依次为预约路径添加时间窗。Then take the end time of the time window where the end point of the car is located as the starting time, and add time windows for the reservation path in turn.

本实施例的子节点列表找寻方法，包括以下步骤：The child node list finding method of the present embodiment includes the following steps:

(1)通过地图，找到所有以当前机器人站点为起点的所有子路段列表，从中选择一条路段P_next执行以下操作；(1) Through the map, find all the sub-section lists starting from the current robot site, and select a section P_next to perform the following operations;

(2)判断P_next路段的终点是否与路径的起始点和目标点的区域类型相同，若不同，返回第(1)步，若相同，继续下一步；(2) Determine whether the end point of the P_next road section is the same as the starting point of the path and the area type of the target point, if different, return to step (1), if the same, continue to the next step;

(3)从P_next路段的空闲时间窗中选择一个时间窗TW进行以下操作， TW＝[a,b]，若已选择完毕，跳到第(1)步；(3) Select a time window TW from the free time window of the P_next road section to carry out the following operations, TW=[a, b], if the selection has been completed, jump to the (1) step;

(4)判断空闲时间窗TW的开始时间a是否小于机器人到达路段P_next 起始节点的时间c，如果小于，继续第(5)步；如果不小于，跳转第(6)步；(4) Determine whether the start time a of the free time window TW is less than the time c for the robot to reach the starting node of the road section P_next, if less, continue to step (5); if not less, skip to step (6);

(5)判断时间窗TW_1是否被时间窗TW包含：如果包含，即机器人通过P_next不被其他机器人干扰，进行第(9)步；如果不包含，即机器人通过 P_next会被其他机器人干扰，则返回第(3)步；(5) Determine whether the time window TW_1 is included in the time window TW: if it is included, that is, the robot will not be interfered by other robots through P_next, go to step (9); if it is not included, that is, the robot will be interfered by other robots through P_next, then return step (3);

时间窗TW_1＝[c,d]，TW_1的起始时间c为机器人到达路段P_next起始节点的时间，时间长度d-c为机器人通过P_next路段的时间，其中机器人通过 P_next路段的时间＝P_next路段的长度/机器人行驶的速度；Time window TW_1=[c,d], the starting time c of TW_1 is the time when the robot arrives at the starting node of the road section P_next, and the time length d-c is the time for the robot to pass the road section P_next, where the time for the robot to pass the road section P_next=the length of the road section P_next / The speed at which the robot travels;

(6)判断时间窗TW_2是否能被TW包含，若是，即机器人在等待一段时间后，通过路段P_next，不被其他机器人干扰；若不是，即机器人在等待一段时间后，仍然无法通过路段P_next，会被其他机器人干扰，返回第(3)步；(6) Determine whether the time window TW_2 can be included in TW. If so, the robot will pass the road section P_next after waiting for a period of time without being disturbed by other robots; if not, that is, the robot will still be unable to pass the road section P_next after waiting for a period of time. Will be interfered by other robots, return to step (3);

时间窗TW_2＝[a,a+d-c],时间窗TW_2的起始时间为空闲时间窗TW的起始时间a，时间长度为机器人通过P_next路段的时间，即d-c，其中机器人通过P_next路段的时间＝P_next路段的长度/机器人行驶的速度；Time window TW_2=[a, a+d-c], the start time of time window TW_2 is the start time a of the free time window TW, and the time length is the time for the robot to pass through the P_next road section, that is, d-c, where the time for the robot to pass through the P_next road section ＝The length of P_next road section/the speed that robot travels;

(7)判断时间窗TW_3是否被机器人停靠的站点的空闲时间窗N_TW包含，若是，即机器人在站点等待时，不会与其他机器人发生干扰，进行下一步；若不是，即机器人在站点等待时，会与其他机器人发生干扰，返回第(3)步；(7) Determine whether the time window TW_3 is included by the idle time window N_TW of the station where the robot stops, if so, the robot will not interfere with other robots when it is waiting at the station, and proceed to the next step; if not, the robot is waiting at the station , will interfere with other robots, return to step (3);

时间窗TW_3＝[c,a]，即机器人在站点等待的时间窗，时间窗TW_3的起始时间为机器人到达路段P_next起始节点的时间，时间窗TW_3的结束时间为空闲时间窗TW的起始时间；Time window TW_3=[c, a], that is, the time window for the robot to wait at the station. The start time of time window TW_3 is the time when the robot arrives at the start node of road segment P_next, and the end time of time window TW_3 is the start of the idle time window TW start time;

机器人到达P_next路段起始节点时，P_next路段还有其他机器人通过，等待一段时间，其他机器人行驶过后，该机器人再行走。When the robot reaches the starting node of the P_next section, there are other robots passing through the P_next section. After waiting for a period of time, the robot will walk again after the other robots have passed.

(8)以(P_next,TW_2)生成节点Node_next,将Node_next添加至节点列表；(8) Generate node Node_next with (P_next, TW_2), add Node_next to the node list;

(9)以(P_next,TW_1)生成节点Node_next,将Node_next添加至节点列表；(9) Generate node Node_next with (P_next, TW_1), add Node_next to the node list;

(10)返回节点列表。(10) Return the node list.

为方便理解，本实施例假设空闲时间窗TW＝[5,8]；For the convenience of understanding, this embodiment assumes that the idle time window TW=[5,8];

如果机器人到达路段P_next起始节点的时间为6，即c＝6，则进行第(5) 步；If the time when the robot arrives at the starting node of road section P_next is 6, i.e. c=6, then proceed to step (5);

如果机器人到达路段P_next起始节点的时间为4，即c＝4，则进行第(6) 步；If the time when the robot arrives at the starting node of road section P_next is 4, i.e. c=4, then proceed to step (6);

由第(4)步，机器人到达路段P_next起始节点的时间为6，即c＝6；By the (4) step, the time for the robot to arrive at the starting node of road section P_next is 6, i.e. c=6;

如果机器人通过P_next路段的时间为2，则TW_1＝[6,8]，TW_1被TW包含，即机器人通过P_next不被其他机器人干扰，跳转第(9)步；If the time for the robot to pass the P_next section is 2, then TW_1=[6,8], TW_1 is included in TW, that is, the robot will not be disturbed by other robots through P_next, and jump to step (9);

如果机器人通过P_next路段的时间为4，则TW_1＝[6,10]，TW_1不被TW 包含，即机器人通过P_next会被其他机器人干扰，返回第(3)步；If the time for the robot to pass the P_next section is 4, then TW_1=[6,10], TW_1 is not included in TW, that is, the robot will be disturbed by other robots when passing P_next, and return to step (3);

由第(4)步，机器人到达路段P_next起始节点的时间为4，即c＝4；By the (4) step, the time for the robot to arrive at the starting node of road section P_next is 4, i.e. c=4;

如果机器人通过P_next路段的时间为2，则TW_2＝[5,7]，TW_2被TW包含，即机器人可以在等待一段时间后，通过路段P_next，不被其他机器人干扰，跳转下一步；If the time for the robot to pass the P_next road section is 2, then TW_2=[5,7], TW_2 is included by TW, that is, the robot can pass the road section P_next after waiting for a period of time without being disturbed by other robots, and jump to the next step;

如果机器人通过P_next路段的时间为4，则TW_1＝[5,9]，TW_2不被TW 包含，即机器人在等待一段时间后，仍然无法通过路段P_next，会被其他机器人干扰，返回第(3)步。If the time for the robot to pass the P_next road section is 4, then TW_1=[5,9], TW_2 is not included in TW, that is, the robot still cannot pass the road section P_next after waiting for a period of time, and will be interfered by other robots, return to (3) step.

TW_3＝[4,5]为机器人等待时间。TW_3=[4,5] is the waiting time of the robot.

如果站点空闲时间窗N_TW＝[3,10],TW_3被N_TW包含，机器人在站点等待时，不会与其他机器人发生干扰，跳转下一步；If the station idle time window N_TW=[3,10], TW_3 is included by N_TW, the robot will not interfere with other robots while waiting at the station, and jump to the next step;

如果站点空闲时间窗N_TW＝[3,4],TW_3不被N_TW包含，机器人在站点等待时，会与其他机器人发生干扰，返回第(3)步。If the station idle time window N_TW=[3,4], TW_3 is not included in N_TW, the robot will interfere with other robots while waiting at the station, and return to step (3).

上述实施例只为说明本发明的技术构思及特点，其目的在于让熟悉此项技术的人能够了解本发明的内容并据以实施，并不能以此限制本发明的保护范围。凡根据本发明主要技术方案的精神实质所做的修饰，都应涵盖在本发明的保护范围之内。The above-mentioned embodiments are only to illustrate the technical conception and characteristics of the present invention, and its purpose is to enable those skilled in the art to understand the content of the present invention and implement it accordingly, and not to limit the protection scope of the present invention. All modifications made according to the spirit of the main technical solutions of the present invention shall fall within the protection scope of the present invention.

Claims (4)

1. A path planning and control method is characterized by comprising the following steps:
s1, initialization: finding out all road sections with the initial point as the starting point, checking the idle time window of each road section, and checking the time window
Figure FDA0003719704590000011
Put into OPEN list, where path is the length of the road section and v represents the speed of the robot walking;
s2, finding out the node N with the minimum cost from the OPEN listlastThe cost comprises arrival time and whether an idle time window exists; node NlastRemove from the OPEN list, add to the CLOSE list, and occupy node NlastThe idle time window of (c);
s3, finding out a node NlastSelecting a child node N from the listnextIf child node NnextThe road section terminal point of (1) is a target point, and the step S6 is skipped; otherwise, continuing the next step; if the child node list is empty, jumping to the step S2;
s4, judging the child node NnextWhether the current position is in the OPEN list or not, if not, continuing the next step; if so, the child node N is compared againnextIf the cost is lower than the original cost, removing the original node, continuing the next step, and if not, returning to the step S3;
s5, enabling child node NnextAdding the data into an OPEN list, and returning to the step S2;
and S6, successfully planning the path, and adding a safe time window for the end point.
2. The path planning and control method according to claim 1, wherein if the terminal point of the robot is a narrow roadway, the terminal point is subjected to a reverse reservation path:
firstly, acquiring a node generated at the end point of a path generated by a trolley, acquiring a reverse reservation path corresponding to the node, and reserving to a tunnel exit point;
and then, taking the time window ending time of the terminal point of the trolley as the starting time, and sequentially adding time windows for the reserved paths.
3. The path planning and policing method of claim 2, wherein in step S3, the method for searching the child node list comprises:
(1) Finding all sub-road section lists taking the current robot station as a starting point through a map, and selecting a road section P _ next from the sub-road section lists to execute the following operations;
(2) Judging whether the end point of the P _ next road section is the same as the area types of the starting point and the target point of the path or not, if so, returning to the step (1), and if so, continuing the next step;
(3) Selecting a time window TW from the idle time windows of the P _ next road sections to perform the following operations, wherein TW = [ a, b ], and if the selection is finished, jumping to the step (1);
(4) Judging whether the starting time a of the free time window TW is less than the time c of the robot reaching the P _ next starting node of the road section, and if so, continuing the step (5); if not, jumping to the step (6);
(5) Determining whether time window TW _1 is included in time window TW: if yes, the robot passes the P _ next without being interfered by other robots, and the step (9) is carried out; if not, the robot is interfered by other robots through P _ next, and then the step (3) is returned;
the time window TW _1= [ c, d ], a start time c of TW _1 is a time when the robot reaches a start node of the P _ next link, and a time length d-c is a time when the robot passes through the P _ next link, wherein the time when the robot passes through the P _ next link = the length of the P _ next link/the speed at which the robot travels;
(6) Judging whether the time window TW _2 can be contained by the TW or not, if so, namely the robot passes through the road segment P _ next after waiting for a period of time and is not interfered by other robots; if not, namely the robot still cannot pass through the road section P _ next after waiting for a period of time, the robot is interfered by other robots, and the step (3) is returned;
time window TW _2= [ a, a + d-c ], where the starting time of the time window TW _2 is the starting time a of the idle time window TW, and the time length is the time when the robot passes through the P _ next road segment, i.e., d-c, where the time when the robot passes through the P _ next road segment = the length of the P _ next road segment/the speed at which the robot travels;
(7) Judging whether the time window TW _3 is contained by an idle time window N _ TW of a station where the robot stops, if so, namely the robot does not interfere with other robots when waiting at the station, and carrying out the next step; if not, namely the robot is in the station waiting, the robot interferes with other robots, and the step (3) is returned;
time window TW _3= [ c, a ], i.e. the time window in which the robot waits at the station, the start time of the time window TW _3 is the time when the robot reaches the starting node of the road segment P _ next, and the end time of the time window TW _3 is the start time of the idle time window TW;
(8) Generating a Node _ next by (P _ next, TW _ 2), and adding the Node _ next to the Node list;
(9) Generating a Node _ next by (P _ next, TW _ 1), and adding the Node _ next to the Node list;
(10) A list of nodes is returned.
4. The method for route planning and control as claimed in claim 3, wherein in step (6), when the robot reaches the starting node of the P _ next segment, the P _ next segment is passed by other robots, waiting for a period of time, and after the other robots have traveled, the robot walks again.
CN202210756476.2A 2022-06-29 2022-06-29 Path planning and control method Pending CN115268429A (en)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN202210756476.2A CN115268429A (en) 2022-06-29 2022-06-29 Path planning and control method

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN202210756476.2A CN115268429A (en) 2022-06-29 2022-06-29 Path planning and control method

Publications (1)

Publication Number Publication Date
CN115268429A true CN115268429A (en) 2022-11-01

Family

ID=83762491

Family Applications (1)

Application Number Title Priority Date Filing Date
CN202210756476.2A Pending CN115268429A (en) 2022-06-29 2022-06-29 Path planning and control method

Country Status (1)

Country Link
CN (1) CN115268429A (en)

Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN110174111A (en) * 2019-05-31 2019-08-27 山东华锐智能技术有限公司 More AGV path planning algorithms of task segmented based on time window
WO2019228081A1 (en) * 2018-06-01 2019-12-05 上海西井信息科技有限公司 Time window-based multi-vehicle path planning method, system, and device, and storage medium
CN113821039A (en) * 2021-09-27 2021-12-21 歌尔股份有限公司 Path planning method, device, device and storage medium based on time window

Patent Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2019228081A1 (en) * 2018-06-01 2019-12-05 上海西井信息科技有限公司 Time window-based multi-vehicle path planning method, system, and device, and storage medium
CN110174111A (en) * 2019-05-31 2019-08-27 山东华锐智能技术有限公司 More AGV path planning algorithms of task segmented based on time window
CN113821039A (en) * 2021-09-27 2021-12-21 歌尔股份有限公司 Path planning method, device, device and storage medium based on time window

Non-Patent Citations (2)

* Cited by examiner, † Cited by third party
Title
徐海军;潘迪;: "基于A~*算法的无冲突路由多路AGV控制策略", 工业控制计算机, no. 08, 25 August 2018 (2018-08-25) *
许卫卫;张启钱;邹依原;张洪海;陈雨童;: "改进A~*算法的物流无人机运输路径规划", 华东交通大学学报, no. 06, 15 December 2019 (2019-12-15) *

Similar Documents

Publication Publication Date Title
CN111301409A (en) Parking path planning method and device, vehicle and storage medium
CN114077254B (en) AGV path conflict processing method
CN113821039A (en) Path planning method, device, device and storage medium based on time window
JP2005524061A (en) Method and system for dynamically navigating a car to a destination
KR101010718B1 (en) Dynamic Driving Method of Unmanned Carrier Occupying Multiple Resources
CN110751334A (en) AGV (automatic guided vehicle) scheduling method and device based on intersection region prediction
CN114819420A (en) Overhead traveling crane transportation path planning method based on conflict resolution
CN118083804B (en) Path selection method and device based on reduction of track busyness
US20240370038A1 (en) Traffic control system for mining trucks and method for same
CN114281080B (en) Method for deadlock removal in AMR scheduling system
CN114264313B (en) Potential energy-based lane-level path planning method, system, equipment and storage medium
CN114527751B (en) Robot path planning method and device and electronic equipment
US20220089372A1 (en) Systems and methods for managing movement of materials handling vehicles
WO2021189882A1 (en) Vehicle scheduling method, apparatus and system
CN115752478A (en) Open-pit mine area multi-vehicle cooperative loading path planning method based on road side guidance
CN115402344A (en) Parking scene simulation method and device
CN114265705A (en) A Method of Preventing Deadlock in AMR Scheduling System
Escudero et al. A satellite navigation system to improve the management of intermodal drayage
CN115268429A (en) Path planning and control method
CN116252814A (en) Method, device, electronic equipment and medium for planning speed of automatic driving vehicle
CN116940911A (en) System and method for managing movement of a materials handling vehicle
CN118331258A (en) A method, system, storage medium and device for vehicle automatic driving path planning and control
JP2021524574A (en) Devices and methods for outputting navigation information and automobiles
CN116429138A (en) Path planning method, path planning device, vehicle and storage medium
CN116719312A (en) A multi-AGV unlocking method based on turnaround and avoidance in a one-way street scenario

Legal Events

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