KR-102964454-B1 - Method and apparatus for creating driving route of multi-mobile robot based on target conflict

KR102964454B1KR 102964454 B1KR102964454 B1KR 102964454B1KR-102964454-B1

Abstract

The present invention relates to a method and apparatus for generating a driving path for multiple mobile robots based on target collision, wherein a starting point corresponding to the starting position and an ending point corresponding to the ending position of each mobile robot are designated among multiple vertices of a driving map, a driving path for each mobile robot corresponding to the minimum length from the starting point of each mobile robot to the ending point of each mobile robot is generated, each mobile robot moves along the driving path and, after reaching the ending point of each mobile robot and while in a stationary state, checks whether a target collision corresponding to a collision with another mobile robot has occurred, and regenerates the driving path of each mobile robot according to whether a target collision has occurred.

Inventors

박성기
김창환
김효정

Assignees

한국과학기술연구원

Dates

Publication Date: 20260513
Application Date: 20231027

Claims (9)

A step of generating a driving map consisting of a plurality of vertices and edges connecting each of the plurality of vertices and a neighboring vertex of each vertex; A step of designating a starting point corresponding to the starting position and an arrival point corresponding to the arrival position of each of the multiple mobile robots among the multiple vertices of the above driving map; A step of generating a driving path for each mobile robot corresponding to the minimum length from the starting point of each mobile robot to the destination point of each mobile robot within the driving map; A step of checking whether a target collision corresponding to a collision with another mobile robot occurs while the mobile robot moves along the driving path of each mobile robot generated above, reaches the destination of each mobile robot, and then stands still; and It includes a step of regenerating the driving path of each mobile robot depending on whether the above target collision occurs, If it is confirmed that the above target collision has occurred, the method further includes the step of generating a driving constraint indicating the above target collision, and The step of regenerating the driving path of each of the above mobile robots regenerates the driving path of each of the above mobile robots to satisfy the driving constraints indicating the target collision, and A step of checking whether there exists at least one vertex where a collision of multiple mobile robots occurs when each mobile robot moves along the driving path of each mobile robot generated above; and If it is confirmed that there exists at least one vertex where a collision of the multiple mobile robots occurs, the method further includes the step of generating a driving constraint representing at least one vertex where a collision of the multiple mobile robots occurs. The step of regenerating the driving path of each of the above mobile robots regenerates the driving path of each of the above mobile robots to satisfy a driving constraint indicating the target collision and a driving constraint indicating at least one vertex where the collision of the multiple mobile robots occurs, and The method further includes a step of determining whether a collision occurs between multiple mobile robots at each of the multiple pairs of vertices that can be combined from a plurality of vertices of the driving map, based on the size information of each of the multiple mobile robots. A method for generating a driving path for multiple mobile robots, characterized in that the step of checking whether there is at least one vertex where a collision of the multiple mobile robots occurs is to check whether there is at least one vertex where a collision of the multiple mobile robots occurs when each mobile robot moves along the driving path of each mobile robot generated based on whether a collision of the multiple mobile robots occurs at the determined pair of pairs of vertices.
delete
In Article 1, The step of generating a driving constraint representing the target collision comprises generating a driving constraint representing the target collision, comprising the ID of each of the multiple mobile robots where the target collision occurred, the location where the target collision occurred, and the time of occurrence of the target collision. A method for generating a driving path for multiple mobile robots, characterized in that the step of regenerating the driving path of each mobile robot is to regenerate the driving path of each mobile robot in a manner that determines the minimum length path from the starting point of one mobile robot to the destination point of one mobile robot under the condition that one of the multiple mobile robots in which the target collision occurred avoids the location where the target collision occurred at the time of the target collision.
delete
delete
In Article 1, A step of checking whether there is at least one edge where a collision of multiple mobile robots occurs when each mobile robot moves along the driving path of each mobile robot generated above; and If it is confirmed that there exists at least one edge where a collision of the multiple mobile robots occurs, the method further includes the step of generating a driving constraint representing the at least one edge where a collision of the multiple mobile robots occurs. A method for generating a driving path for multiple mobile robots, characterized in that the step of regenerating the driving path of each mobile robot above regenerates the driving path of each mobile robot to satisfy a driving constraint representing a target collision and a driving constraint representing at least one edge where a collision of multiple mobile robots occurs.
In Article 6, The method further includes a step of determining whether a collision occurs between multiple mobile robots on a plurality of pairs of edges when each of the multiple mobile robots is moving along each of a plurality of pairs of edges that can be combined from a plurality of edges of a driving map based on the size information of each of the multiple mobile robots. A method for generating a driving path for multiple mobile robots, characterized in that the step of checking whether there is at least one edge where a collision of multiple mobile robots occurs is based on whether a collision of multiple mobile robots occurs in the determined pair of edges, and when each mobile robot moves along the driving path of each mobile robot generated above, the method checks whether there is at least one edge where a collision of multiple mobile robots occurs.
A computer-readable recording medium storing a program for executing the method of claim 1 on a computer.
A driving map generating unit that generates a driving map consisting of a plurality of vertices and edges connecting each of the plurality of vertices and a neighboring vertex of each vertex; and It includes a driving path generation unit that designates a starting point corresponding to the starting position and an ending point corresponding to the ending position of each of the multiple mobile robots among a plurality of vertices of the driving map, and generates a driving path for each mobile robot corresponding to the minimum length from the starting point of each mobile robot to the ending point of each mobile robot within the driving map. The above driving path generation unit checks whether a target collision corresponding to a collision with another mobile robot occurs while the mobile robot is in a stationary state after reaching the destination of the mobile robot along the driving path of each mobile robot generated above, and regenerates the driving path of each mobile robot according to whether the target collision occurs. When the driving path generation unit confirms that the target collision has occurred, it generates a driving constraint condition indicating the target collision, and The above driving path generation unit regenerates the driving path of each mobile robot to satisfy the driving constraint indicating the target collision, and The above driving path generation unit checks whether there exists at least one vertex where a collision of multiple mobile robots occurs when each mobile robot moves along the driving path of each mobile robot generated above, and If the driving path generation unit confirms that there exists at least one vertex where a collision of the multiple mobile robots occurs, it generates a driving constraint representing at least one vertex where a collision of the multiple mobile robots occurs, and The above driving path generation unit regenerates the driving path of each mobile robot to satisfy a driving constraint indicating the target collision and a driving constraint indicating at least one vertex where the collision of the multiple mobile robots occurs, and The driving path generation unit determines whether a collision occurs between the multiple mobile robots at each of the multiple pairs of vertices when each of the multiple mobile robots is located at each of the multiple pairs of vertices that can be combined from the multiple vertices of the driving map based on the size information of each of the multiple mobile robots. A multi-mobile robot driving path generation device characterized by the above driving path generation unit confirming whether there is at least one vertex where a collision of the multi-mobile robots occurs when each mobile robot moves along the driving path of each mobile robot generated above, based on whether a collision of the multi-mobile robots occurs at the determined plurality of pairs of vertices.

Description

Method and apparatus for creating driving route of multi-mobile robot based on target conflict The present invention relates to a method and apparatus for generating a driving path for multiple mobile robots to prevent collisions between multiple mobile robots. Mobile robots are frequently used in logistics environments, playing the role of transporting dozens or hundreds of items. Unlike robots used in industrial settings such as manufacturing, mobile robots are characterized by the simultaneous movement of dozens or more units. The most critical consideration when using mobile robots in the field is preventing collisions among multiple robots during movement. Collisions are dangerous accidents that can cause not only damage to the robots and the goods but also explosions, potentially leading to human casualties. To prevent such accidents, active technological development is underway to enable mobile robots to avoid collisions with various obstacles along their paths. This primarily involves measuring the distance between the robot and the obstacle to assess the likelihood of a collision and then evading it. Korean Patent Publication No. 10-2017-0140561, "Driving Control Device and Method for Multi-Robots," discloses a method for minimizing the time required to perform a mission by calculating an optimal path for the efficient movement of multiple moving robots. However, while it discloses the possibility of collision and avoidance measures for stationary obstacles, it had a problem in that it did not consider the situation of collision between multiple robots. FIG. 1 is a configuration diagram of a driving path generation device according to one embodiment of the present invention. FIG. 2 is a flowchart of a driving path generation method according to one embodiment of the present invention. Figure 3 is a diagram illustrating two collisions between multiple mobile robots. Figure 4 is a detailed flowchart of the 40 steps illustrated in Figure 2. Figure 5 is an example of a target collision between multiple mobile robots. Embodiments of the present invention will be described in detail below with reference to the drawings. The embodiments of the present invention described below relate to a method and apparatus for efficiently generating a driving path in which collisions between multiple mobile robots do not occur by separating only target collisions from vertex collisions, verifying their occurrence, and generating driving constraints. Hereinafter, the method for generating such a driving path will be briefly referred to as the "driving path generation method," and the apparatus for generating the driving path will be briefly referred to as the "driving path generation apparatus." FIG. 1 is a configuration diagram of a driving path generation device according to an embodiment of the present invention. Referring to FIG. 1, the driving path generation device according to an embodiment of the present invention comprises a driving map generation unit (100), a storage unit (200), a user interface (300), a collision determination unit (400), and a path generation unit (500). The multiple mobile robots of this embodiment refer to a plurality of mobile robots that drive along different driving paths within the same driving map. Hereinafter, this embodiment will be described by specifying that the multiple mobile robots consist of a pair of mobile robots, namely a first mobile robot and a second mobile robot that are different from each other. The multiple mobile robots may also consist of three or more different mobile robots. The driving map generation unit (100) generates a driving map consisting of a plurality of vertices and edges connecting each of the plurality of vertices to a surrounding vertex of each vertex. The driving map generated by the driving map generation unit (100) is stored in the storage (200), and the driving map stored in the storage (200) is read out by the collision determination unit (400). The user interface (300) receives information for each of the multiple mobile robots, that is, information for each of the multiple mobile robots, from the user. As information for each of the multiple mobile robots, the user interface (300) receives the size information of each mobile robot, the starting time of each mobile robot, the movement speed of each mobile robot, and the starting point and ending point of each mobile robot. The collision determination unit (400) determines whether a collision occurs between the multiple mobile robots based on the size information of each of the multiple mobile robots. The path generation unit (500) generates a driving path for the multiple mobile robots within the driving map based on whether a collision occurs between the multiple mobile robots. FIG. 2 is a flowchart of a driving path generation method according to an embodiment of the present invention. Referring to FIG. 2, the driving path generation method according to the present embodiment consists of t