KR102695353B1 - Method for robot path finding - Google Patents

Abstract

In an embodiment of the present disclosure, a path search method is disclosed, including a step of searching a virtual path through which each of a plurality of robots passes through a specific point and moves to a target location, a step of deleting a path for a specific robot among the plurality of robots and re-searching a path for the specific robot to move from a current location to the target location, a step of updating the path for the specific robot using the re-searched path, and a step of determining the path of the plurality of robots using the updated path.

Description

{METHOD FOR ROBOT PATH FINDING}

The present disclosure relates to a path search method for a plurality of robots. More specifically, it relates to a path search method using local search or simulated annealing.

Recently, as technology for robot automation and unmanned operation is being developed, robot automatic path search technology is also being developed. Developments have been made from technology for repeatedly driving a set path to robot location recognition, and recently, in addition to developments for robot location recognition, developments for path search and movement are also being actively made. As a result of this technology development, robots are being utilized in actual intelligent logistics centers, and interest in the actual application of technology is increasing, such as the appearance of serving robots in general restaurants.

Meanwhile, in response to this interest, various challenges for robot path finding also exist, and challenges are constantly being held to find an optimized path in a situation where arbitrary geometric structures are placed.

The present disclosure is intended to derive an optimal robot path from a starting point to a target point in an environment in which arbitrary structures are placed.

The present disclosure discloses a path search method including a step of searching a virtual path through which each of a plurality of robots passes through a specific point and moves to a target location, a step of deleting a path for a specific robot among the plurality of robots and re-searching a path for the specific robot to move from a current location to the target location, a step of updating the path for the specific robot using the re-searched path, and a step of determining the path of the plurality of robots using the updated path.

Additionally, the path search method of the robot can be performed on a two-dimensional coordinate grid.

Additionally, the specific point may include an intermediate point outside a bounding box that includes the current location and target location of each of the plurality of robots.

In addition, the step of searching a virtual path along which each of the plurality of robots passes through a specific point and moves to the target position may include (1) a step of determining at least one movable direction of the robot and moving in the movable direction, (2) a step of deriving at least one first path by repeating (1) until the robot reaches the specific point, (3) a step of deriving at least one second path by repeating (1) until the robot reaches the target position, and (4) a step of determining, when the robot reaches the target position, a path that is the minimum of the sum of the first path and the second path as the path of the robot.

In addition, the step of re-searching the path for the specific robot to move from the current location to the target location may include the step of determining at least one movable direction for the robot and moving in the movable direction, the step of deriving at least one path until the target location is reached by repeating the step of moving in the movable direction, and the step of determining, when the robot reaches the target location, the path with the minimum length among the derived paths as the path of the robot.

Additionally, the movable direction may include up, down, left, right, and in place on a two-dimensional grid.

In addition, the step of searching a virtual path for each of the plurality of robots to pass through a specific point and move to the target location includes the step of determining a path search order for each of the plurality of robots, and the order can be determined based on a path distance from a current location of each of the plurality of robots to an arbitrary point outside a bounding box that includes the current location and target location of each of the plurality of robots.

In addition, the step of deleting a path for a specific robot among the plurality of robots and re-searching a path for the specific robot to move from a current location to the target location may include the step of deleting a path between a first time and a second time among virtual paths of the specific robot, the step of extracting a candidate location at which the specific robot may be located at a third time between the first time and the second time, and the step of searching for a shortest distance between a path from the first time location of the specific robot to the candidate location and a path from the candidate location to the second time location.

In addition, the step of determining the path of the plurality of robots using the updated path for each of the plurality of robots may select the path with the minimum sum of the path lengths of each of the plurality of robots or the path search time as the final path.

In addition, as a computer program stored in a computer-readable medium, the computer program includes commands for causing one or more processors to perform path search for a robot, and the commands may include a computer program stored in a computer-readable medium to execute the steps of: searching for a virtual path through which each of a plurality of robots passes through a specific point and moves to a target location; deleting a path for a specific robot among the plurality of robots and re-searching a path through which the specific robot moves from a current location to the target location; updating the path for the specific robot using the re-searched path; and determining the paths of the multiple robots using the updated paths for each of the multiple robots.

The above computer program can be implemented as a program including the method described above.

According to various embodiments of the present invention, by deriving an optimized path from a starting point to a target point in an environment where arbitrary structures are arranged, all robots can move without collision.

Figure 1 illustrates a path search method of a robot according to one embodiment of the present invention.
Figure 2 illustrates a data structure according to one embodiment of the present invention.
Figure 3 shows a flowchart according to one embodiment of the present invention.
FIG. 4 illustrates a path insertion and deletion method according to one embodiment of the present invention.
Figure 5 illustrates a robot order determination method according to one embodiment of the present invention.
Figure 6 illustrates a path optimization method according to one embodiment of the present invention.

Hereinafter, embodiments disclosed in this specification will be described in detail with reference to the attached drawings. Regardless of the drawing symbols, identical or similar components will be given the same reference numerals and redundant descriptions thereof will be omitted. The suffixes 'module' and 'part' used for components in the following description are assigned or used interchangeably only for the convenience of writing the specification, and do not have distinct meanings or roles in themselves. In addition, when describing embodiments disclosed in this specification, if it is determined that a specific description of a related known technology may obscure the gist of the embodiments disclosed in this specification, the detailed description thereof will be omitted. In addition, the attached drawings are only intended to facilitate easy understanding of the embodiments disclosed in this specification, and the technical ideas disclosed in this specification are not limited by the attached drawings, and should be understood to include all modifications, equivalents, and substitutes included in the spirit and technical scope of the present invention.

Terms that include ordinal numbers, such as first, second, etc., may be used to describe various components, but the components are not limited by the terms. The terms are used only to distinguish one component from another.

When it is said that a component is 'connected' or 'connected' to another component, it should be understood that it may be directly connected or connected to that other component, but that there may be other components in between. On the other hand, when it is said that a component is 'directly connected' or 'directly connected' to another component, it should be understood that there are no other components in between.

Each component of the present disclosure is independently illustrated to indicate different characteristic functions, and does not mean that each component is formed as a separate hardware or software configuration unit. That is, each component is listed and included as a separate component for convenience of explanation, and at least two components among each component may be combined to form a single component, or one component may be divided into multiple components to perform a function, and such integrated and separated embodiments of each component are also included in the scope of the present invention as long as they do not deviate from the essence of the present invention.

In addition, some components may not be essential components that perform essential functions in the present invention, but may be optional components that are merely used to improve performance. The present invention may be implemented by including only essential components for implementing the essence of the present invention, excluding components that are merely used to improve performance, and a structure that includes only essential components, excluding optional components that are merely used to improve performance, is also included in the scope of the present invention.

The present disclosure relates to a path search method for a robot, and as a specific path search condition of the present disclosure, a path search method is disclosed that enables movement from a start point on a two-dimensional coordinate grid to a target point without collision between robots or between a robot and an obstacle in each grid.

As a result of measuring performance using the path search method according to an embodiment of the present invention, a path of the robots was derived that shortens the time of the robot arriving last among a plurality of robots or minimizes the sum of the paths of each of the plurality of robots.

The path search method of the present disclosure is described in FIG. 1 below.

FIG. 1 illustrates a path search method of a robot according to an embodiment of the present invention. FIG. 2 is a diagram illustrating a data structure in a path search method according to an embodiment of the present disclosure.

Referring to Figure 1, there are multiple robots existing on a two-dimensional grid, and each

Each robot included in the modeled N robot set must move from a start position s1 to sN to a target position d1 to dN. (Figure 1 illustrates the case where N = 3 as an example.)

For example, among multiple robots, the first robot must move from the current position s1 to the target position d1, the second robot must move from the current position s2 to the target position d2, and the third robot must move from the current position s3 to the target position d3. An obstacle (201) may also exist on the two-dimensional grid.

According to an embodiment of the present disclosure, if the position of each robot included in a set of N robots is denoted as pi(t) at any time t, the position coordinates of the robots can be expressed as pi(t) = (xi(t), yi(t)), and since the robots at time t either stay at the same position or move to one of the four adjacent squares, it can be expressed as pi(t + 1) - pi(t) ∈ {(0, 0), (1, 0), (0,-1), (0, 1) , (1, 0)}. That is, in FIG. 2, each of the plurality of robots can stay in place or move in the up, down, left, and right directions over time on a two-dimensional grid.

Referring to Fig. 2, a spatial coordinate of size WxWxW exists on the data grid (20), and the data grid (20) can store a path according to the flow of position (x, y) and time (t).

For example, Fig. 2 shows a case where two robots move from a specific time t(i)(21) to t(i+1)(22) and then stay at t(i+1). Referring to Fig. 2, at t(i), the first robot moves 1 in the positive y-coordinate direction and reaches the position at t(i+1), so it is mapped to the value of '4', and the other robot moves 1 in the positive x-coordinate direction and reaches the position at t(i+1), so it can be mapped to '1'.

And the corresponding path data can be stored according to the flow of time (t). Afterwards, when the path of any robot is 'inserted' or 'deleted', it can be updated on the data structure of said arbitrary robot.

Below, we will specifically explain the path search method of the robot using the movement method described above.

FIG. 3 is a flowchart illustrating a path search method of a robot according to an embodiment of the present disclosure.

Referring to FIG. 3, in a method for searching for a path of a plurality of robots according to an embodiment of the present invention, a step of searching for a virtual path in which each of the plurality of robots passes through a specific point and moves to a target location may be included (S201).

Each of the multiple robots exists at a different location, and the location of each robot can be defined as the current location (s1, s2, s3). Each of the multiple robots moves toward a different target location (d1, d2, d3) on a two-dimensional grid, and can move over time on the two-dimensional grid.

The coordinates that have moved over the above time flow can be stored in a data structure as shown in Fig. 2, thereby generating a path.

Specifically, a path search method of a robot according to an embodiment of the present disclosure allows each of a plurality of robots to pass through a specific point and move to a target location.

Referring to Fig. 1, each of a plurality of robots can search a path to a target location by passing through a specific point (102) outside a pre-determined boundary (B, 10).

This is because when moving directly from the starting position (sN) to the target position (dN), there are cases where multiple robots each interfere with the path, and path interference may occur between multiple robots and obstacles.

At this time, the specific point (102) may include an intermediate point outside a bounding box including the current location and target location of each of the plurality of robots.

More specifically, each of the plurality of robots can move to a target location via different intermediate points, and the intermediate points can be points on a two-dimensional grid that searches the paths of the robots where the sum of the distances from the current location to the intermediate point and the distances from the intermediate point to the target point is minimized.

A path search method according to an embodiment of the present disclosure can be achieved by 'inserting' or 'deleting' a path in the data structure.

At this time, 'insertion' corresponds to 'Insertion', and can mean a method of finding the shortest distance by displaying all points that the robot can move from the current location of each of multiple robots existing on a two-dimensional grid to the target point.

For example, 'insertion' may include (1) a step of determining at least one movable direction of the robot and moving in the movable direction, and (2) a step of deriving a path by repeatedly performing the operation of determining at least one movable direction of the robot and moving in the movable direction until the robot reaches the specific point.

In addition, 'delete' corresponds to 'deletion' and can mean a method of deleting the paths of each of multiple robots existing on a two-dimensional grid created through the 'insert' process from the data structure.

For example, referring to Fig. 4, the robot wants to move from the current location (31) to the target location (33). For convenience of explanation, the movement path of the robot is represented as '4', '3', '2', and '1' in the up, down, left, and right directions, respectively, and the case of maintaining the current location is represented as '5'. At this time, it is the same as t2, which represents all points to which the robot can move at time t1. The locations (14, 12, 13) shown at t2 represent candidate locations to which the robot existing at time t1 can move. In addition, the location shown at t3 represents candidate locations to which the robot existing at time t2 can move.

The above robot can store the remaining direction information at the corresponding location after reaching the target point (33) through insertion and returning backward to the starting point (31). For example, the direction information can be '4-1-5' according to the time flow from t1 to t3.

That is, the direction that is ultimately stored in the data grid through insertion can represent the direction from the current location to the next location. At time t1, it moves north and reaches the location at time t2, so 4 can be stored at t1. At time t3, it has already reached the target point, so the next location will be the same. Therefore, 5 can be stored.

As described above, according to the embodiment of the present disclosure, the path search method of the robot can display all points to which the robot can move, and then display all points to which the robot can move from all the displayed points to the next point. If the robot reaches the target position from the current position by repeating the above process, the shortest path among the paths can be stored in the data structure.

In an embodiment of the present disclosure, the step of searching a virtual path along which each of the plurality of robots passes through a specific point and moves to the target position may include: (1) the step of determining at least one movable direction of the robot and moving in the movable direction, (2) the step of deriving at least one first path by repeating (1) until the robot reaches the specific point, (3) the step of deriving at least one second path by repeating (1) until the robot reaches the target position, and (4) the step of determining, when the robot reaches the target position, a path that is the minimum of the sum of the first path and the second path as the path of the robot.

That is, a first path can be derived by performing insertion from the current position of each of multiple robots to an intermediate point, and a second path can be derived by performing insertion from the intermediate point to a target position, so that the virtual path that minimizes the sum of the first path and the second path can be determined.

Meanwhile, in the process of deriving the first path and the first path, each of a plurality of robots must move simultaneously over time. At this time, since the path that a specific robot can move may be blocked by another robot, there was a need to move the robots in an appropriate order.

According to an embodiment of the present disclosure, the step of searching a virtual path along which each of the plurality of robots passes through a specific point and moves to the target position may include a step of determining a path search order of each of the plurality of robots, and the order may include a path search method in which the path distance is determined based on a path distance from a current position of each of the plurality of robots to an arbitrary point outside a bounding box including the current position and the target position of each of the plurality of robots.

Specifically, the present invention can determine the movement order of multiple robots by using the geodesic distance of the robots, and perform 'insertion' in the said order. Through the said process, it can be guaranteed that there is always a feasible path from the current location (si) to the intermediate point (mi).

And referring to Fig. 5, the movement order of the robots can be determined based on the geodesic distance from an arbitrary point (o,51) outside the bounding box to the target point (di), and 'insertion' can be performed in the above order. Through this, a feasible path solution for each of multiple robots can be found.

Below we describe how to optimize a virtual path.

Referring again to FIG. 3, the path search method according to an embodiment of the present disclosure may include a step of deleting a path for a specific robot among the plurality of robots and re-searching a path for the specific robot to move from the current location to the target location (S203).

As described above, the path search method according to an embodiment of the present disclosure can be accomplished by 'inserting' or 'deleting' a path into the data structure.

Specifically, after each of a plurality of robots searches for a virtual path through a specific point and moves to a target location, the following process can be performed to derive an optimal path for the robots.

According to an embodiment of the present disclosure, the step of searching a virtual path along which each of a plurality of robots passes through a specific point and moves to the target location may include the step of determining at least one movable direction for the robot at a specific time and moving in the movable direction, the step of deriving at least one path by repeating the steps of determining the movable direction and moving until the target location is reached, and the step of determining a path with a minimum length among the derived paths as the path of the robot when the robot reaches the target location.

Additionally, the movable direction of each of the plurality of robots may include up, down, left, right, and in place on a two-dimensional grid.

At this time, the direction in which the robot can move may mean a case in which there is no path obstruction between robots or between robots and obstacles.

The above process corresponds to a local search in which ‘insertion’ and ‘deletion’ are repeated for each of multiple robots, and may be a path tightening process.

The path tightening process according to an embodiment of the present disclosure may be performed after a path has already been obtained from a start position of each of a plurality of robots to a target position, and may be repeatedly performed until each of the plurality of robots reaches a predetermined target position from its current position.

The above process can be repeated for each of multiple robots to derive an optimized path. The quality of the solution can be improved because the robots no longer need to pass through intermediate points.

Meanwhile, when using local search, there were cases where a local minimum occurred where the path was no longer updated, and accordingly, we attempted to overcome the limitations of local search through simulated annealing.

According to an embodiment of the present disclosure, the step of deleting a path for a specific robot among the plurality of robots and re-searching a path for the specific robot to move from a current location to the target location may include the step of deleting a path between a first time and a second time among virtual paths of the specific robot, the step of extracting a candidate location at which the specific robot may be located at a third time between the first time and the second time, and the step of searching for a shortest distance between a path from the first time location of the specific robot to the candidate location and a path from the candidate location to the second time location.

The above step may be a path stretching step. By intentionally lengthening the path through the above path stretching, the problem of being trapped in a local minimum in path contraction can be solved.

FIG. 6 illustrates an example of a path search process based on simulated annealing according to an embodiment of the present disclosure.

Specifically, according to an embodiment of the present disclosure, in order to escape from the above-mentioned local minimum, the simulated annealing method can intentionally generate a non-optimal path (worse solution) and probabilistically reflect it (accept it).

At this time, a path stretch can be used to generate a non-optimized path (worse solution).

Referring to Fig. 6, an example is shown to explain which path is derived when path tightening and path stretching are applied respectively to (61). That is, if path tightening is used in a virtual generated path (61) stored in a data structure, a better optimized path (62) can be derived than the current one, and if path stretching is used, a path (64) that is intentionally not optimized can be derived.

Specifically, the process of deriving a path (64) that is intentionally not optimized through path stretching is described.

63 of Fig. 6 illustrates a path stretching process. The path search method according to an embodiment of the present disclosure can delete the path of a specific robot i between a first time (t1) and a second time (t2). pi(tm) may correspond to a position of robot i that may exist at a specific time randomly selected between t1 and t2. Robot i can calculate all candidate positions (x, y, tm) of the data structure (G) that can be reached from pi(t1) and can be reached from pi(t2).

That is, the above path search method can calculate all candidate locations (x, y, tm) of the data structure (G) that can be reached from pi(t1) and can be reached from pi(t2) by using any one of all candidate locations (x, y, tm) of the data structure (G) that can be reached from pi(t1) and can be reached from pi(t2).

According to an embodiment of the present disclosure, one of the candidate locations can be randomly extracted. After that, the shortest path can be derived by connecting pi(tm) to pi(t1) and pi(t2) through the shortest path calculated through 'insertion' in the same manner.

The above example illustrates a specific robot i among multiple robots, and the above method for deriving the shortest path can be applied to each of the multiple robots.

Additionally, the above process may be a simulated annealing.

That is, simulated annealing may mean a model that intentionally reflects a robot's path that is not an optimal path in order to prevent overfitting from occurring due to the local search.

Specifically, you can set a rate (accept rate) that reflects the robot's path rather than the optimal path.

The method for searching for an optimized path according to an embodiment of the present disclosure may be performed repeatedly multiple times. At this time, each time the simulated annealing is performed multiple times, the ratio reflecting the path of the robot that is not the optimal path may have a smaller value than the previous process. Through this, the error range can be reduced.

The above method may improve the quality of the solution since the robot no longer needs to pass through intermediate points.

Let's explain Figure 3 again.

A path search method according to an embodiment of the present disclosure may include a step (S205) of updating a path for the specific robot using the re-searched path and a step (S207) of determining paths for the plurality of robots using the updated path.

Specifically, the re-searched path through S203 can be updated in the data structure of Fig. 2. In addition, the step of determining the path of the plurality of robots using the updated path for each of the plurality of robots can select the path with the minimum sum of the path lengths of each of the plurality of robots or the path search time as the final path.

Those skilled in the art will appreciate that the various illustrative logical blocks, modules, processors, means, circuits, and algorithm steps described in connection with the embodiments disclosed herein may be implemented as electronic hardware, various forms of programs or design code (for convenience, referred to herein as software), or a combination of both.

The above-described present invention can be implemented as a computer-readable code on a medium in which a program is recorded. The computer-readable medium includes all kinds of recording devices that store data that can be read by a computer system. Examples of the computer-readable medium include a hard disk drive (HDD), a solid state disk (SSD), a silicon disk drive (SDD), a ROM, a RAM, a CD-ROM, a magnetic tape, a floppy disk, an optical data storage device, etc.

Claims (13)

A step of searching for a virtual path in which each of a plurality of robots moves to a target position by passing through a specific point including an intermediate point outside a bounding box including the current position and target position of each of the plurality of robots;
A step of deleting the virtual path for a specific robot, which is a robot that can exist at a specific time randomly selected between a first time and a second time among the plurality of robots, and re-searching the path for the specific robot to move from the current location to the target location;
A step of updating the path for the specific robot using the above re-searched path, and
comprising a step of determining the path of said plurality of robots using the updated path;
Path finding method. In paragraph 1,
The above robot's path search method is performed on a two-dimensional coordinate grid.
Path finding method. delete In paragraph 1,
The step of searching for a virtual path through which each of the above multiple robots passes a specific point and moves to the target location is as follows:
(1) a step in which the robot determines at least one movable direction and moves in the movable direction;
(2) a step of deriving at least one first path by repeating the above (1) until reaching the specific point;
(3) When the robot reaches the specific point, the step of repeating (1) until reaching the target position to derive at least one second path; and
(4) a step of determining, when the robot reaches the target position, the path that is the minimum of the sum of the first path and the second path as the path of the robot;
How to find a path. In paragraph 1,
The step of re-searching the path for the above specific robot to move from the current location to the target location is
(1) a step in which the robot determines at least one movable direction and moves in the movable direction;
(2) a step of deriving at least one path by repeating the above (1) until reaching the target location; and
(3) a step of determining a path with the minimum length among the derived paths as the path of the robot when the robot reaches the target position;
How to find a path. In paragraph 4 or 5,
The above movable directions include up, down, left, right and in place on a two-dimensional grid.
How to find a path. In paragraph 1,
The step of searching for a virtual path through which each of the above multiple robots passes a specific point and moves to the target location is as follows:
Comprising a step of determining the path search order of each of the plurality of robots,
The above order is determined based on the path distance from the current position of each of the plurality of robots to an arbitrary point outside the bounding box that includes the current position and target position of each of the plurality of robots.
How to find a path. In paragraph 1,
The step of deleting the virtual path for a specific robot among the above multiple robots and re-searching the path for the specific robot to move from the current location to the target location is as follows.
A step of deleting a virtual path between a first time and a second time among the virtual paths of the specific robot;
A step of extracting a candidate location where the specific robot can be located at a third time between the first time and the second time, and
A step of searching for the shortest distance of a path from the first time position of the specific robot to the candidate position and a path from the candidate position to the second time position,
How to find a path. In paragraph 1,
The step of determining the path of the plurality of robots using the updated path for each of the plurality of robots is:
The final path is selected when the sum of the path lengths of each of the above multiple robots or the path search time is minimum.
How to find a path. A computer program stored in a computer-readable medium, wherein the computer program includes instructions for causing one or more processors to perform path finding of a robot, the instructions comprising:
A step of searching for a virtual path in which each of a plurality of robots moves to a target position by passing through a specific point including an intermediate point outside a bounding box including the current position and target position of each of the plurality of robots;
A step of deleting the virtual path for a specific robot, which is a robot that can exist at a specific time randomly selected between a first time and a second time among the plurality of robots, and re-searching the path for the specific robot to move from the current location to the target location;
A step of updating the path for the specific robot using the above re-searched path, and
A computer program stored in a computer-readable medium for executing a step of determining a path of said plurality of robots using the updated path for each of said plurality of robots. In Article 10,
The step of searching for a virtual path through which each of the above multiple robots passes a specific point and moves to the target location is as follows:
(1) a step in which the robot determines at least one movable direction and moves in the movable direction;
(2) a step of deriving at least one first path by repeating the above (1) until reaching the specific point;
(3) When the robot reaches the specific point, the step of repeating (1) until reaching the target position to derive at least one second path; and
(4) a step of determining, when the robot reaches the target position, the path that is the minimum of the sum of the first path and the second path as the path of the robot;
A computer program stored on a computer-readable medium. In Article 10,
The step of re-searching the path for the above specific robot to move from the current location to the target location is
(1) a step in which the robot determines at least one movable direction and moves in the movable direction;
(2) a step of deriving at least one path by repeating the above (1) until reaching the target location; and
(3) a step of determining a path with the minimum length among the derived paths as the path of the robot when the robot reaches the target position;
A computer program stored on a computer-readable medium. In Article 10,
The step of deleting the virtual path for a specific robot among the above multiple robots and re-searching the path for the specific robot to move from the current location to the target location is as follows.
A step of deleting the first and second time paths among the virtual paths of the specific robot;
A step of extracting a candidate location where the specific robot can be located at a third time between the first time and the second time, and
A step of searching for the shortest distance of a path from the first time position of the specific robot to the candidate position and a path from the candidate position to the second time position,
A computer program stored on a computer-readable medium.