Search

US-12626595-B2 - Collision condition application device, method, program and path generation device

US12626595B2US 12626595 B2US12626595 B2US 12626595B2US-12626595-B2

Abstract

The present disclosure provides an extraction unit that extracts, in a case in which plural agents move on a road map including plural vertices and plural edges connecting the vertices, a vertex-edge pair and an edge-edge pair in which the agents are likely to collide with each other; a calculation unit that calculates a time interval in which a collision between both agents occurs; and an application unit that applies collision condition information.

Inventors

  • Kazumi Kasaura

Assignees

  • OMRON CORPORATION

Dates

Publication Date
20260512
Application Date
20230731
Priority Date
20220809

Claims (7)

  1. 1 . A collision condition application device, comprising: a memory; and a processor coupled to the memory, the processor being configured to execute processing, the processing including: in a case in which a plurality of agents move on a road map including a plurality of vertices and a plurality of edges connecting the plurality of vertices, extracting i) a first pair consisting of one vertex selected from the plurality of vertices and one edge selected from the plurality of edges along which there is a possibility of a first agent that exists at the one vertex and the second agent that moves along the one edge colliding with each other, and ii) a second pair consisting of two edges selected from the plurality of edges on which there is a possibility of a third agent that moves along one of the two edges and a fourth agent that moves along the other of the two edges colliding with each other; calculating i) a time interval a to b when the first agent and the second agent collision when the difference between time t 1 when the first agent is at the vertex of the first pair and time t 2 when the second agent starts to move from an end point of the edge of the first pair is within the range of the time interval a to b, and ii) a time interval c to d when the third agent and the fourth agent collision when the difference between time t 3 when the third agent starts to move from an end point of one edge of the second pair and time t 4 when the fourth agent starts to move from an end point of the other edge of the second pair is within the range of the time interval c to d; and applying, to the road map, i) information obtained by associating identification information of the vertices and the edges included in the first pair with the time interval a to b, and ii) information obtained by associating identification information of each of the two edges included in the second pair with the time interval c to d, as a condition in which a collision between agents occurs.
  2. 2 . The collision condition application device of claim 1 , wherein the extraction unit extracts the first pair and the second pair by using an algorithm that lists pairs of points, among a given set of points, each pair having an inter-point distance[s] equal to or less than a predetermined distance, an algorithm that lists points present in a given area among a given set of points, and an algorithm that lists pairs of line segments intersecting with each other among a given set of line segments.
  3. 3 . The collision condition application device of claim 1 , wherein, in a case in which an agent is assumed to be a circle having a diameter of a predetermined value, extracting a pair of a vertex and an edge that satisfies at least one of i) and ii) from the plurality of vertices and the plurality of edges, as the first pair; i) a case in which a distance between at least one of the end points of a edge and a vertex is less than the predetermined value, ii) a case in which a length of a perpendicular line drawn from a vertex to a edge is less than the predetermined value; and extracting a pair of edges that satisfies at least one of iii) and iv) from the plurality of edges, as the second pair; iii) a case in which a distance between at least one of the end points of one edge and the other edge is less than the predetermined value, iv) a case in which edges intersect with each other.
  4. 4 . A path generation device comprising: the collision condition application device of claim 1 ; and generating a path of each of the plurality of agents moving on the road map to which a condition in which the plurality of agents collide with each other is applied by the collision condition application device, in which a time at which an agent is present at a vertex included in the path and a time at which the agent starts to move from an end point of an edge are not included in a time interval of the condition.
  5. 5 . The path generation device of claim 4 , wherein, in a case in which paths of the plurality of agents are sequentially generated one by one, generating a path, in which a first path for agent A is generated first, and then, when a second path for agent B is generated, the second path is generated so as to satisfy conditions i) and ii); i) the difference between the time ta when one of agent A and agent B exists at the vertex of the first pair included in the first path and the time tb when the other of agent A and agent B starts moving from the end point of the edge of the first pair included in the first path is not included in the time interval a to b, ii) the difference between the time tc when one of agent A and agent B starts moving from the end point of one edge of the second pair included in the first path and the time td when the other of agent A and agent B starts moving from the end point of the other edge of the second pair included in the first path is not included in the time interval c to d.
  6. 6 . A collision condition application method, comprising: in a case in which a plurality of agents move on a road map including a plurality of vertices and a plurality of edges connecting the plurality of vertices, extracting i) a first pair consisting of one vertex selected from the plurality of vertices and one edge selected from the plurality of edges along which there is a possibility of a first agent that exists at the one vertex and the second agent that moves along the one edge colliding with each other, and ii) a second pair consisting of two edges selected from the plurality of edges on which there is a possibility of a third agent that moves along one of the two edges and a fourth agent that moves along the other of the two edges colliding with each other; calculating i) a time interval a to b when the first agent and the second agent collision when the difference between time t 1 when the first agent is at the vertex of the first pair and time t 2 when the second agent starts to move from an end point of the edge of the first pair is within the range of the time interval a to b, and ii) a time interval c to d when the third agent and the fourth agent collision when the difference between time t 3 when the third agent starts to move from an end point of one edge of the second pair and time t 4 when the fourth agent starts to move from an end point of the other edge of the second pair is within the range of the time interval c to d; and applying, to the road map, i) information obtained by associating identification information of the vertices and the edges included in the first pair with the time interval a to b, and ii) information obtained by associating identification information of each of the two edges included in the second pair with the time interval c to d, as a condition in which a collision between agents occurs, by an application unit.
  7. 7 . A collision condition application program for causing a computer to function to: in a case in which a plurality of agents move on a road map including a plurality of vertices and a plurality of edges connecting the plurality of vertices, extract i) a first pair consisting of one vertex selected from the plurality of vertices and one edge selected from the plurality of edges along which there is a possibility of a first agent that exists at the one vertex and the second agent that moves along the one edge colliding with each other, and ii) a second pair consisting of two edges selected from the plurality of edges on which there is a possibility of a third agent that moves along one of the two edges and a fourth agent that moves along the other of the two edges colliding with each other; calculate i) a time interval a to b when the first agent and the second agent collision when the difference between time t 1 when the first agent is at the vertex of the first pair and time t 2 when the second agent starts to move from an end point of the edge of the first pair is within the range of the time interval a to b, and ii) a time interval c to d when the third agent and the fourth agent collision when the difference between time t 3 when the third agent starts to move from an end point of one edge of the second pair and time t 4 when the fourth agent starts to move from an end point of the other edge of the second pair is within the range of the time interval c to d; and apply, to the road map, i) information obtained by associating identification information of the vertices and the edges included in the first pair with the time interval a to b, and ii) information obtained by associating identification information of each of the two edges included in the second pair with the time interval c to d, as a condition in which a collision between agents occurs.

Description

CROSS-REFERENCE TO RELATED APPLICATION This application is based on and claims the benefit of priority of the prior Japanese Patent Application No. 2022-127476, filed on Aug. 9, 2022, the entire contents of which are incorporated herein by reference. BACKGROUND Technical Field The present disclosure relates to a collision condition application device, a collision condition application method, a collision condition application program, and a path generation device. Related Art A problem of searching for paths in which a plurality of agents having a size move from respective start points to respective target points without colliding with each other in one environment is referred to as multi-agent path finding (MAPF). In a general MAPF problem, the movement of each agent is determined under discrete time on a grid graph or road map representing a path along which the agent can move within the environment. As a technology related to the MAPF problem, for example, an operation management control device that plans an operation and a path for efficiently moving a plurality of unmanned vehicles to a destination node in consideration of conflict of traveling paths and adjacent nodes is proposed (Japanese Patent Application Laid-Open (JP-A) No. H10-312217). In this device, the movement path and the node reservation sequence of each unmanned vehicle, the position and the conveyance destination of the conveyance object, the current position and the movement direction of each unmanned vehicle, the coordinates of each node on the traveling path, the connection relationship and the cost, and the Petri net model data are stored in a memory. This device determines an optimal travel path and an operation order of the unmanned vehicle by using the information stored in the memory. For example, a flight plan system that makes an operation plan for a plurality of moving bodies traveling in a traveling path network including a plurality of traveling paths is proposed (Japanese Patent Application Laid-Open (JP-A) No. 2020-149370). This system generates a plurality of travel timing plans in which timings at which the plurality of moving bodies travel on a traveling path are designated such that a conflict between the moving bodies does not occur on the traveling path based on position information of the plurality of moving bodies, traveling path structure information representing a structure of the traveling path network, and a plurality of path plans in which an order of one or more designated areas through which the plurality of moving bodies pass is designated for the plurality of designated areas in the traveling path network. For a single agent, a method referred to as safe interval path planning (SIPP) in which a path search in a case in which there is a moving obstacle is performed under continuous time is proposed (Mike Phillips and Maxim Likhachev, “SIPP: Safe Interval PathPlanning for Dynamic Environments”, Computer Science 2011 IEEE International Conference on Robotics and Automation, 9 May 2011). SUMMARY OF THE INVENTION However, in a case in which the movement of each agent is determined under discrete time, the time is divided into turns common to all the agents, and the action of the agent is determined for each turn. As a result, there is a problem that there is a case in which the limitation for avoiding a collision between the agents increases, and the path search becomes difficult. It is also conceivable to extend the MAPF problem in the case of continuous time by combining the MAPF problem in discrete time with a method of dealing with continuous time such as SIPP. However, in a case in which the SIPP is applied to a road map that is a non-grid graph, determining the collision between the agents becomes a bottleneck in calculation. This is because, in order to apply the SIPP, it is necessary to grasp in advance when and where a collision with all moving obstacles on the road map may occur. Therefore, in the case of the multi-agent, the paths of the agents are determined one by one in some priority order. In this case, when the number of agents increases, enormous calculation is required, and thus it becomes difficult to generate a path of each agent, which is a solution to the MAPF problem, in a realistic time. The disclosure has been made in view of the above points, and an object thereof is to enable path generation in continuous time of a multi-agent on a road map in a short period of time. In order to achieve the object, a collision condition application device according to the disclosure includes: an extraction unit that, in a case in which a plurality of agents move on a road map including a plurality of vertices and a plurality of edges connecting the plurality of vertices, extracts a first pair of vertices and edges for which there is a possibility of agents being present at the vertices or agents moving on the edges colliding with each other and a second pair of one edge and another edge for which ther