JP7030657B2 - Route creation device, route creation method, route creation program and map data manufacturing method - Google Patents

Description

The present invention relates to a route creation device, a route creation method, a route creation program, and a map data manufacturing method.

Conventionally, RRT (Rapidly-exploring Random Tree) and RRT ^* (Rapidly-exploring Random Tree) have been known as algorithms for determining a movement route. RRT and RRT ^* are algorithms that can create a movement path while avoiding collision with an obstacle in free space, and are used to determine a movement path for an industrial robot arm or the like. Patent Document 1 discloses a technique of using RRT for creating a traveling route of an automobile.

Japanese Unexamined Patent Publication No. 2011-11388

When deciding the movement route, it is conceivable that not only simply avoiding obstacles but also setting an area that can be used as a movement route but wants to avoid being used as a movement route if possible. For example, when deciding the flight route of a drone, it is not prohibited to fly the drone, but there is a case where you want to set a traffic recommendation level in the space, such as an area where you want to avoid the flight of the drone as much as possible. Be done.

However, in the conventional RRT and RRT ^* , it is possible to search for a route in consideration of the binary information of passable / impassable like an obstacle, but if possible, it is desired to avoid being used as a movement route. It is not possible to determine the movement route in a space that includes an area that is treated as an intermediate, such as an area.

Therefore, one aspect of the present invention is to provide a technique capable of creating a movement route in consideration of the passage recommendation degree in a space in which the passage recommendation degree of the movement route is set.

The route creation device according to one aspect of the present invention is a route creation device for creating a movement route when a moving body moves from a starting point to a destination by connecting a line segment connecting nodes, and is a space. A storage unit that stores area information in which one or more areas contained therein and a multi-valued weight value applied to each of the one or more areas are associated and stored, and a node arranged in the space. A new node is placed at one point and a second point selected from a group of nodes including the departure point, which has moved a predetermined distance from a nearby node close to the first point toward the first point, based on a predetermined placement probability. Then, a movement route to the destination is created by repeating connecting the neighboring node to the new node with a line segment, or within a predetermined range based on the new node in the node group including the departure point. A movement route creation unit that creates a movement route to the destination by repeating connecting a candidate node with a low cost of the movement route from the departure point and a new node with a line segment among one or more existing candidate nodes. Based on the weight value included in the area information, the movement route creating unit has a predetermined distance, a predetermined placement probability, a selection criterion of a nearby node close to the first point, and a predetermined range size. , And adjust at least one of the costs of the travel path from the origin to each of the one or more candidate nodes.

According to one aspect of the present invention, it is possible to provide a technique capable of creating a movement route in consideration of the passage recommendation degree in a space in which the passage recommendation degree of the movement route is set.

It is a figure which shows an example of the movement management system 1 which concerns on embodiment. It is a figure for demonstrating the RRT algorithm. It is a figure for demonstrating the RRT ^* algorithm. It is a figure which shows the hardware configuration example of the route generator. It is a figure which shows the functional block composition example of the route generation apparatus. It is a figure which shows an example of area information. It is a figure which shows an example of the space which a route generation apparatus generates a route. It is a figure for demonstrating an example of the route generation method by algorithm 1. FIG. It is a figure for demonstrating an example of the route generation method by algorithm 1. FIG. It is a figure for demonstrating an example of the route generation method by algorithm 2. It is a figure for demonstrating an example of the route generation method by algorithm 4. It is a figure for demonstrating a modification.

Preferred embodiments of the present invention will be described with reference to the accompanying drawings. In each figure, those with the same reference numerals have the same or similar configurations.

<System configuration>
FIG. 1 is a diagram showing an example of a movement management system 1 according to an embodiment. The movement management system 1 includes a route generation device 10 and a mobile body 20. Although a plurality of mobile bodies 20 are shown in FIG. 1, the number of mobile bodies 20 included in the movement management system 1 may be one. The route generation device 10 and the mobile body 20 can communicate with each other by the communication network N. The communication network N is basically assumed to be a wireless network, but may include a wired network.

The route generation device 10 is a device that generates a route that the moving body 20 should take in space. The route generation device 10 may be any information processing device such as a server, a personal computer (PC), a notebook PC, a smartphone, a tablet terminal, a mobile phone, a mobile information terminal (PDA), and a home-use game device. Further, the route generation device 10 may be composed of one or a plurality of information processing devices. The path generated by the route generation device 10 may be either a path in a two-dimensional space or a path in a three-dimensional space, and may theoretically be a path in a space of four or more dimensions.

The moving body 20 is, for example, a flying object such as a drone or a helicopter, a vehicle, a robot, or the like, and moves from a starting point to a destination according to a moving path generated by the route generating device 10.

In the space where the route generation device 10 generates a route, there are an area where the moving body 20 is prohibited from passing, an area where the moving body 20 is to be avoided as much as possible, and an area where the moving body 20 can freely pass. Exists. The area where the moving body 20 is prohibited from passing is, for example, an area where an obstacle such as a building exists, an area where flight is prohibited, and the like. The area in which the passage of the moving body 20 is desired to be avoided as much as possible is, for example, in a space where a large number of moving bodies 20 pass, although a small amount of the moving body 20 is allowed to pass, a large number of moving bodies 20 pass through. Free passage is an area that you want to avoid.

In the present embodiment, these areas are represented by a multi-valued weight value (hereinafter referred to as "passage recommendation degree") indicating the degree to which the passage of the moving body 20 in the area is recommended. The traffic recommendation level is expressed by a value from 0% to 100%, for example. In addition, the traffic recommendation level given to the area may change depending on external factors such as time, weather, and the number and condition of surrounding aircraft. The recommended passage in the area where the moving body 20 is prohibited is set to 0%, and the recommended passage in the area where the moving body 20 can freely pass is set to 100%. The recommended degree of passage in the area where the passage of the moving body 20 is desired to be avoided as much as possible is set according to the degree to which the passage is desired to be avoided. For example, if the recommendation level of passage is 70%, it means an area where the passage of the moving body 20 is allowed to some extent. For example, if the recommendation level of passage is 20%, it means an area where the passage of the moving body 20 is not so allowed. means. Further, for an area to be passed with priority, a passage recommendation level exceeding 100% (for example, 120%) may be given.

It should be noted that the method of expressing the recommended passage level is just an example, and is not limited to the expression by percentage. For example, the degree of recommendation for passage may be expressed by a value from 0 (no passage) to 1 (free passage). Alternatively, the recommended degree of passage may be expressed by a value of 100% (prohibited) to 0% (freely allowed), and the recommended degree of passage may be expressed as 1 (prohibited) to 0 (freely allowed). It may be expressed by the value of (possible).

The passage recommendation level for each area existing in the space is included in the "area information" held by the route generation device 10. The area information is associated with one or more areas and the traffic recommendation level applied to each of the one or more areas, and the route generation device 10 refers to the area information when generating the route. Therefore, the route is generated while considering the recommended traffic for each area.

The route generator 10 generates a route using an RRT algorithm or an RRT ^* algorithm. First, a method of creating a route in a two-dimensional space using an existing RRT algorithm will be described using an example shown in FIG. In FIG. 2, a two-dimensional space will be described as an example for convenience of explanation, but the present embodiment is not intended to be limited to the two-dimensional space. This embodiment can also be applied to a three-dimensional space, a four-dimensional space, or a multidimensional space beyond that.

RRT places a new node at a point that is a predetermined distance (Δq) ahead of the point (node) set in the space, and repeats connecting these two nodes with a line segment as the starting point. It is an algorithm that creates a route from to the destination. Δq is also called incremental distance or step size. In FIG. 2, Qinit is the starting point and Qgoal is the destination. Qinit is also one of the nodes. Area X indicates an area where the mobile body 20 is prohibited from passing.

First, the route generation device 10 randomly arranges the points Qrand in the space S (FIG. 2A). Subsequently, the route generation device 10 selects the node Qnear closest to the point Qrand. In FIG. 2A, since the node has only Qinit, the route generation device 10 selects Qinit as the node Qnear. Subsequently, the route generator 10 arranges a new node Qnew at a point Δq ahead of Qinit on the line segment from Qinit to the point Qrand (FIG. 2 (b)), and a line between Qinit and Qnew. A line segment L is added (FIG. 2 (c)).

Subsequently, the route generation device 10 randomly arranges the next Qrand in the space S (FIG. 2 (c)), and selects Qnew as the node Qnear closest to the Qrand. Subsequently, the route generation device 10 arranges a new node Qnew at a point ahead of Qnear by Δq on the line segment from Qnear to the point Qrand (FIG. 2 (d)). At this time, if the distance from the node Qnear to the Qrand is less than Δq, the point ahead of the node Qnear by Δq may be set as the new node Qnew, or the Qrand may be set as the new node Qnew. good.

In the example of FIG. 2D, since Qnew is located in the area X where passage is prohibited, the route generation device 10 discards this Qnew and redoes the process of arranging a new Qrand. .. Further, even if Qnew is not located in the area X where the passage is prohibited, if the area X where the passage is prohibited is included between Qnear and Qnew, the route generation device 10 discards this Qnew. Then, repeat the process of placing a new Qrand. If Qnew is not located in the area X where traffic is prohibited and the area X where traffic is prohibited is not included between Qnear and Qnew, a line segment is added between Qnear and Qnew.

The route generation device 10 performs these processing procedures on the condition that the line segment connecting Qnew and Qgoal does not pass through the area X and the line segment is within a predetermined distance (condition 1), or Qnear and Qnew. This is repeated until the condition (condition 2) that the line segment connecting Qgoal and the line segment connecting Qgoal are equal to or less than a predetermined distance and the line segment connecting Qnear and Qgoal does not pass through the area X is satisfied (FIG. 2 (e)). When the condition 1 is satisfied, the route generation device 10 connects Qnew and Qgoal with a line segment. Further, when the condition 2 is satisfied, the route generation device 10 connects Qnear and Qgoal with a line segment. As a result, one route is created from Qinit to Qgoal. Since the condition for terminating the search is not defined in the RRT algorithm, the route generation device 10 can search for another route by repeating the processing procedure described above.

Next, a method of creating a route in a two-dimensional space using an existing RRT ^* algorithm will be described with reference to FIG. The RRT ^* algorithm is the same as the RRT algorithm in the procedure up to the placement of Qnew, but the process of adding a line segment after that is different from the RRT algorithm.

Specifically, the route generation device 10 has the node with the lowest cost from Qinit to each node among the nodes existing in a predetermined range surrounded by a circle centered on Qnew after arranging Qnew. Select Qmin) and add a line segment between Qmin and Qnew. The cost is the length of the entire line segment. For example, in the example of FIG. 3A, the nodes Q1, Q2, and Q3 are included in the circle C1 having a radius r centered on Qnew, and the cost from the nodes Q1 to Qnew is the smallest. Therefore, as shown in FIG. 3B, the route generation device 10 regards the node Q1 as Qmin and adds a line segment L1 between the node Q1 (Qmin) and Qnew.

In addition, in the RRT ^* algorithm, after adding a line segment from Qmin to Qnew, the cost is increased by going through Qnew among the nodes existing in the predetermined range surrounded by the circle centered on Qnew. If there is something that goes down, reconnect the line segment so that it goes through Qnew. For example, in the example of FIG. 3A, the cost from Qinit to the node Q3 is lower when the route via Qnew is used than the route shown in FIG. 3A. Therefore, as shown in FIG. 3B, the route generation device 10 deletes the line segment between the node Q3 and the node Q4, and adds the line segment L2 between the node Q3 and the Qnew.

In the RRT ^* algorithm, the radius r is set to a predetermined fixed value or a smaller value based on the number of nodes existing in the circle centered on Qnew. ..

<Hardware configuration>
FIG. 4 is a diagram showing a hardware configuration example of the route generation device 10. The route generation device 10 includes a CPU (Central Processing Unit) 11, a storage device 12 such as a memory, an HDD (Hard Disk Drive) and / or an SSD (Solid State Drive), and a communication IF (Interface) 13 for performing wired or wireless communication. It has an input device 14 that accepts input operations and an output device 15 that outputs information. The input device 14 is, for example, a keyboard, a touch panel, a mouse and / or a microphone. The output device 15 is, for example, a display and / or a speaker.

<Functional block configuration>
FIG. 5 is a diagram showing an example of a functional block configuration of the route generation device 10. The route generation device 10 includes a route creation unit 101, a route output unit 102, and a storage unit 103. The route creation unit 101 and the route output unit 102 can be realized by the CPU 11 of the route generation device 10 executing the program stored in the storage device 12. Further, the program can be stored in a storage medium. The storage medium in which the program is stored may be a non-transitory computer readable medium. The non-temporary storage medium is not particularly limited, but may be, for example, a storage medium such as a USB memory or a CD-ROM. Further, the storage unit 103 can be realized by using the storage device 12 included in the route generation device 10.

The route creation unit 101 creates a movement route when the moving body moves from the starting point to the destination by connecting the line segments connecting the nodes in order by using the RRT algorithm. Specifically, the route creation unit 101 is selected from the points arranged based on the first placement probability in the space (hereinafter referred to as "placement points (first point)") and the node group including the departure point. The second placement probability (referred to as the predetermined placement probability) is at the selected point (second point) that has moved a predetermined distance from the node close to the placement point (hereinafter referred to as "proximity node") toward the placement point. A new node (hereinafter referred to as "new node") is placed based on the above.

Further, the route creation unit 101 creates a movement route to the destination by repeating connecting the neighboring node and the new node with a line segment according to the RRT algorithm. Alternatively, the route creation unit 101 follows the RRT ^* algorithm and refers to one or more nodes (hereinafter referred to as “candidate nodes”) existing in a predetermined range based on the new node in the node group including the departure point. Of these, a travel route to the destination is created by repeating connecting the candidate node and the new node, which have a low cost of the travel route from the departure point, with a line segment.

Here, the first placement probabilities may be uniform (ie, random). More specifically, determining a point based on the first placement probability means determining a point in space by generating a uniform random number within the defined area of each axis in the n-dimensional space. You may. In addition, in order to speed up processing by limiting the placement range, a point in space is generated by limiting it to an ellipsoid (or sphere) that includes the starting point and the destination and generating a uniform random number. You may decide. In that case, if the point determined by generating a uniform random number in each orthogonal coordinate axis is included in the predetermined ellipsoid (or sphere), the point is determined as a point in space, and if it is not included, it is determined again. This can be achieved by repeating the process of generating a uniform random number. Alternatively, a point in space may be determined by generating a uniform random number for the domain of each axis of polar coordinates.

Further, when the route creation unit 101 selects a nearby node from the node group including the departure point, the route creation unit 101 may select it by using a linear search, or uses a method that can search at high speed like a Kd tree. May be selected.

Further, when the route creation unit 101 creates a movement route while connecting the nodes with a line segment, the route creation unit 101 is close to a predetermined distance, a predetermined second placement probability, and a placement point based on the traffic recommendation level included in the area information. Move by adjusting at least one of the selection criteria of neighboring nodes to be used, the size of a predetermined range based on the new node, and the cost of the travel route from the departure point to each of one or more candidate nodes. The area where the passage of the body 20 is not recommended is controlled so that the line segment is less likely to be drawn.

The route output unit 102 outputs the movement route data created by the route creation unit 101. The output movement route data is read by the moving body 20, and the moving body 20 that has read the moving route data moves from the starting point to the destination according to the moving route data.

The storage unit 103 stores area information. FIG. 6 shows an example of area information. The "area position" stores information for specifying the position of the area in which the recommended passage level is set in the space. The position of the area may be expressed using any data. For example, it may be expressed using latitude and longitude, it may be expressed by a set of vertex coordinate data, it may be expressed by using polygons, or 3D (three-dimensional) data such as glTF may be expressed. It may be expressed using. A value from 0% to 100% is stored in the "traffic recommendation level". The area where the moving body 20 can freely pass (the area where the recommended passage degree is 100%) may be omitted from the area information.

<Processing procedure>
Subsequently, the procedure for the route generation device 10 to create a route will be specifically described. In the following description, for convenience of explanation, a two-dimensional space will be used, but the description is not limited to this. This embodiment is also applicable to the case of creating a route in a three-dimensional space.

FIG. 7 is a diagram showing an example of a space in which the route generation device 10 generates a route. In the space S shown in FIG. 7, an area A1 and an area A2 having a recommended passage degree of 0%, an area A3 having a recommended passage degree of 40%, and an area A4 having a recommended passage degree of 60% are set. There is.

The route creation unit 101 of the route generation device 10 creates a route in consideration of the degree of recommendation for passage by changing a part of the above-mentioned RRT algorithm or RRT ^* algorithm. Specifically, a route is created by combining any one or a plurality of the following algorithms 1 to 6. The points not specifically mentioned follow the existing RRT algorithm or RRT ^* algorithm described with reference to FIG.

(Algorithm 1)
When arranging a new node (Qnew), the route creation unit 101 has a line segment length as the passage recommendation level is lower for the area through which the line segment connecting the neighboring node (Qnear) to the new node (Qnew) passes. Arrange the position of the new node (Qnew) so that is short.

FIG. 8 is a diagram for explaining an example of a route generation method by the algorithm 1. In the following description, percentages shall be calculated in terms of percentages. That is, for example, X × 50% is calculated assuming that it is X × 0.5.

The point q is a point advanced by Δq from the neighboring node (Qnear). In the algorithm 1, the route creation unit 101 extends the line segment from the proximity node (Qnear) to the placement point (Qrand) while adjusting the distance traveled according to the recommended passage of the area to be passed. At this time, the length of the line segment extending becomes shorter as the degree of recommendation for passage is lower. That is, if there is even a part of the area from the proximity node (Qnear) to the point q where the recommended passage is less than 100%, the line segment extending from the proximity node (Qnear) reaches the point q. Instead, it will stop in the middle.

In FIG. 8, the area B_n (n = 1, 2, 3 ... N) is a proximity node among one or more areas through which a line segment extending from the proximity node (Qnear) toward the placement point (Qrand) passes. The nth area is shown in order of proximity to (Qnear). Further, the point where the boundary on the proximity node (Qnear) side of the area B_n intersects with the line segment connecting the proximity node (Qnear) and the point q is called a boundary (q_border1_n). Further, the point where the boundary on the point q side of the area B_n intersects with the line segment connecting the neighboring node (Qnear) and the point q is called a boundary (q_border2_n). Further, the distance from the boundary (q_border1_n) to the boundary (q_border2_n) is called Δarea (B_n). The recommended passage level for area B_n is X_n%. However, when n = 1, a proximity node (Qnear) may be included inside the area B_1. Therefore, when n = 1, Δarea (B_1) is assumed to be the distance from the neighboring node (Qnear) to the boundary (q_border2_n).

“Rest” is a variable indicating the surplus force of the stretching force when the line segment is stretched, and the initial value is Δq. The extension force is a value calculated by dividing the length of extending the line segment by the recommended passage degree, and the extension force when extending the length X of the line segment in the area where the recommended passage degree is 100% is X. On the other hand, when the line segment is extended by the length X in the area where the recommended passage is 50%, the extending force is 2X. The extension force is reduced each time the area is passed, and when the rest becomes 0, the line segment cannot be extended any more and stops. Δq'is a variable that stores the length of the line segment calculated by the algorithm 1, and the initial value is zero.

First, when the route creation unit 101 extends the line segment from the proximity node (Qnear) toward the placement point (Qrand), does the line segment stop in the middle of the area B_1 or does the line segment penetrate the area B_1? Is calculated.

When ΔareaB_1 ÷ X_1% is rest or more (that is, there is no room for the line segment to penetrate the area B_1), the line segment stops in the middle of the area B_1 or at the boundary (q_border2_1) (n = in FIG. 8A). 1). In this case, the route creation unit 101 adds rest × X_1% (that is, the length at which the line segment extends) to Δq ′.

On the other hand, when ΔareaB_1 ÷ X_1% is less than rest (that is, when the line segment has a margin to penetrate the area B_1), the line segment does not stop in the middle of the area B_1 and enters the area B_1 (FIG. 8 (b). ) N = 1). In this case, the route creation unit 101 adds ΔareaB_1 to Δq'and subtracts ΔareaB_1 ÷ X_1% from rest.

Next, when the line segment enters the area B_2, the route creating unit 101 stops the line segment in the middle of the area B_2 when the line segment is extended from the boundary of the area B_2 (q_border1_2) toward the point q. Or whether the line segment penetrates area B_2.

If ΔareaB_2 ÷ X_2% is rest or more, the line segment stops in the middle of the area B_2 or at the boundary (q_border2_2) (n = 2 in FIG. 8A). In this case, the route creation unit 101 adds rest × X_2% (the length at which the line segment extends) to Δq ′.

On the other hand, when ΔareaB_2 ÷ X_2% is less than rest, the line segment does not stop in the middle of the area B_2 and enters the area B_3 (n = 2 in FIG. 8B). In this case, the route creation unit 101 adds ΔareaB_2 to Δq'and subtracts ΔareaB_2 ÷ X_2% from rest.

The route creation unit 101 extends the line segment until the line segment extended from the proximity node (Qnear) toward the point q stops in any area (that is, until the state shown in FIG. 8A is reached). By repeating the above, the value of Δq'when the line segment is stopped is calculated. Finally, the route creation unit 101 arranges a new node (Qnew) at a point Δq'advanced from the proximity node (Qnear) toward the point q.

Subsequently, a specific example will be described with reference to FIG. In the following explanation, the percentage shall be calculated by converting it into a percentage. FIG. 9A shows a point where a new node (Qnew) is arranged when the recommended passage rate is 60%. In the example of FIG. 9A, all the line segments connecting the points q from the proximity node (Qnear) are included in the area where the recommended passage degree is 60%. In this case, since rest (= Δq) is smaller than ΔareaB_1 (= Δq) ÷ 60%, the line segment extending from the neighboring node (Qnear) stops in the middle of the area B_1 (FIG. 8A). pattern). Therefore, Δq'= Δq × 60%. Finally, the route creation unit 101 arranges a new node (Qnew) at a point Δq'advanced from the proximity node (Qnear) toward the arrangement point (Qrand).

FIG. 9B shows a point where a new node (Qnew) is placed when the recommended passage rate is 40%. In the example of FIG. 9B, all the line segments connecting the points q from the proximity node (Qnear) are included in the area where the recommended passage degree is 40%. In this case, since rest (= Δq) is smaller than ΔareaB_2 (= Δq) ÷ 40%, the line segment extending from the neighboring node (Qnear) stops in the middle of area B_2 (FIG. 8A). pattern). Therefore, Δq'= Δq × 40%. Finally, the route creation unit 101 arranges a new node (Qnew) at a point Δq'advanced from the proximity node (Qnear) toward the arrangement point (Qrand).

FIG. 9C shows a point where a new node (Qnew) is arranged when areas having different recommended passage levels are mixed. First, the route creation unit 101 compares rest (= Δq) with ΔareaB_1 ÷ 100% (= Δq × 45% ÷ 100%). In this case, since r is larger than ΔareaB_1 ÷ 100%, the line segment extending from the neighboring node (Qnear) penetrates the area B_1 (pattern in FIG. 8B). Therefore, the route creation unit 101 adds ΔareaB_1 to Δq'and subtracts ΔareaB_1 ÷ 100% from rest. At this point, rest = Δq × 55% (= Δq−Δq × 45% ÷ 100%).

Next, the route creation unit 101 compares rest (= Δq × 55%) with ΔareaB_2 ÷ 60% (= Δq × 25% ÷ 60%). In this case, since the rest is larger than ΔareaB_2 ÷ 60%, the line segment extending from the neighboring node (Qnear) penetrates the area B_2 (the pattern in FIG. 8B). Therefore, the route creation unit 101 adds ΔareaB_2 to Δq'and subtracts ΔareaB_2 ÷ 60% from rest. At this point, rest = Δq × 13.33% (= Δq × 55% −Δq × 25% ÷ 60%).

Next, the route creation unit 101 compares rest (= Δq × 13.3%) with ΔareaB_3 ÷ 40% (= Δq × 30% ÷ 40%). In this case, since the rest is smaller than ΔareaB_3 ÷ 40%, the line segment extending from the neighboring node (Qnear) stops in the middle of the area B_3 (pattern in FIG. 8A). Therefore, the route creation unit 101 adds rest × 40% (= Δq × 5.3%) to Δq ′.

According to the above procedure, Δq'= Δq × 45% + Δq × 25% + Δq × 5.3% (that is, Δq × 75.3%). Subsequently, the route creation unit 101 arranges a new node (Qnew) at a point Δq'advanced from the proximity node (Qnear) toward the arrangement point (Qrand).

In Algorithm 1, when a plurality of areas are included between the proximity node (Qnear) and the point q, Δq'may be calculated as follows. In the example of FIG. 9 (c), among the line segments connecting the points q from the proximity node (Qnear), the recommended passage of 45% of the sections is 100%, and the recommended passage of 25% of the sections is 60%. Yes, the recommended passage rate for the 30% section is 40%. Therefore, Δq'= Δq × (45% × 100% + 25% × 60% + 30% × 40%), that is, Δq ′ = Δq × 72% may be calculated. It is possible to reduce the amount of calculation as compared with the above method.

In addition, when a passage recommendation level exceeding 100% (for example, 120%, etc.) is given to an area that is particularly preferentially passed through, the algorithm 1 process is performed using the passage recommendation level exceeding 100% as it is. It is also good. Alternatively, the traffic recommendation level of each area contained in the space is normalized by the maximum value of the traffic recommendation level of each area (that is, the value calculated by the maximum value of the traffic recommendation level ÷ the traffic recommendation level). The processing of the algorithm 1 may be performed.

According to Algorithm 1, the length of the line segment added between Qinit and Qnew becomes shorter as the recommended passage of the area through which the line segment passes is lower. That is, since the line segment is difficult to extend in the area where the recommended passage is low, the possibility that a route to the destination is generated through the area where the recommended passage is low is reduced. Therefore, by using the algorithm 1, it is possible to reduce the possibility that a movement route including an area with a low recommendation level is generated.

(Algorithm 2)
When the route creation unit 101 arranges a new node (Qnew) at a point moved by a predetermined distance (Δq) from a nearby node (Qnear) toward an arrangement point (Qrand), the degree to which the passage of a moving body is recommended is The lower the area, the lower the probability of arranging the new node (Qnew) (second placement probability).

FIG. 10 is a diagram for explaining an example of a route generation method by the algorithm 2. The route creation unit 101 tentatively determines the point where the new node (Qnew) is to be placed in the space, and determines whether or not to place the new node (Qnew) at the tentatively determined point according to the magnitude of the traffic recommendation level. decide. For example, as shown in FIG. 10, in the space S, an area A1 and an area A2 having a recommended passage degree of 0%, an area A3 having a recommended passage degree of 40%, and an area A4 having a recommended passage degree of 60%. It is assumed that areas other than areas A1 to A4 where the recommended passage level is 100% are set.

It is assumed that the route creation unit 101 tentatively decides to place a new node (Qnew) at the point q1 in the area where the recommended passage level is 100%. In this case, the route creation unit 101 determines that the point q1 is to be a new node (Qnew) with a probability of 100%. Similarly, it is assumed that the route creation unit 101 tentatively decides to place a new node (Qnew) at the point q2 in the area where the traffic recommendation level is 60%. In this case, the route creation unit 101 determines that the point q2 is to be a new node (Qnew) with a probability of 60%. If it is decided not to make the point q2 a new node (Qnew), this q2 is discarded and the process of arranging the placement point (Qrand) is restarted.

Similarly, it is assumed that the route creation unit 101 tentatively decides to place a new node (Qnew) at the point q3 in the area where the traffic recommendation level is 40%. In this case, the route creation unit 101 determines that the point q3 is to be a new node (Qnew) with a probability of 40%. If it is decided not to make the point q3 a new node (Qnew), this q3 is discarded and the process of arranging the placement point (Qrand) is restarted.

It should be noted that the processing of Algorithm 2 is not performed based on the traffic recommendation level of the area including the point where the new node (Qnew) is placed, but the processing of Algorithm 2 is performed based on the traffic recommendation level of the area including the placement point (Qnear). May be done. For example, suppose that in FIG. 10, it is tentatively decided to place a new node (Qnew) at the point q3. In this case, the processing of the algorithm 2 may be performed based on the traffic recommendation degree (100%) of the area including the arrangement point (Qnear3).

In addition, instead of processing Algorithm 2 based on the traffic recommendation level of the area including the point where the new node (Qnew) is placed, the area where the line segment from the placement point (Qnear) to the new node (Qnew) passes. The processing of the algorithm 2 may be performed based on the passage recommendation degree of the area having the lowest passage recommendation degree among the passage recommendation degrees of. For example, suppose that in FIG. 10, it is tentatively decided to place a new node (Qnew) at the point q3. In this case, among the traffic recommendations of the area including the line segment from the placement point (Qnear3) to the new node (Qnew), the traffic recommendation of the area with the lowest traffic recommendation is 40%. Therefore, the route creation unit 101 performs the processing of the algorithm 2 assuming that the passage recommendation degree is 40.

Further, in the algorithm 2, when it is decided not to place the new node at the point tentatively decided to place the new node (Qnew), the place (Qrand) is not placed again from the process of placing the new node (Qrand). ) May be selected and the processing of the algorithm 2 may be performed again by selecting the proximity node (Qnear) that is the next closest to the distance.

In addition, when a passage recommendation level exceeding 100% (for example, 120%, etc.) is given to an area that is particularly preferentially passed, the passage recommendation level of each area included in the space is set to the passage recommendation level of each area. The processing of the algorithm 2 may be performed using the value normalized by the maximum value (that is, the value calculated by the maximum value of the recommended passage ÷ the recommended passage).

According to the algorithm 2, the probability that a new node (Qnew) is arranged decreases as the traffic recommendation level is lower. In other words, the probability that a line segment will be added toward an area with a low recommendation level will decrease. Therefore, by using the algorithm 2, it is possible to reduce the possibility that a movement route including an area with a low recommendation level is generated.

(Algorithm 3)
The route creation unit 101 may adjust the probability of arranging the arrangement point (Qrand) based on the passage recommendation degree. In other words, when arranging the placement point (Qrand), the area where the passage of moving objects is less recommended is adjusted so that the probability of arranging the placement point (Qrand) is lower (first placement probability). You may do it.

Further, the algorithm 3 may be the method shown below. First, the route creation unit 101 determines in which traffic recommendation area the placement point (Qrand) is to be placed. At this time, the route creation unit 101 reduces the probability of arranging the arrangement point (Qrand) as the area with the lower recommended passage is. Subsequently, the route creation unit 101 selects an arbitrary place as a placement point (Qrand) in the selected area.

A specific example will be described. For example, the route creation unit 101 sets 0 to 99, 100 to 159, and 160 to 199 among the numerical values from 0 to 199, respectively, in an area where the passage recommendation level is 100% and the passage recommendation level is 60%, respectively. Allocate to areas and areas with a recommended passage rate of 40%. First, the route creation unit 101 randomly selects any one of the numerical values from 0 to 199 to determine in which traffic recommendation area the placement point (Qrand) is to be placed. For example, when "170" is selected, the route creation unit 101 arranges the arrangement point (Qrand) in the area A3 having a passage recommendation degree of 40%. Subsequently, the route creation unit 101 randomly selects a point to place the placement point (Qrand) in the area A3 having a passage recommendation level of 40%.

According to the algorithm 3, the probability that the placement point (Qrand) is placed decreases as the traffic recommendation level is lower. In other words, the probability that a line segment will be added toward an area with a low recommendation level will decrease. Therefore, by using the algorithm 3, it is possible to reduce the possibility that a movement route including an area with a low recommendation level is generated.

(Algorithm 4)
When the route creation unit 101 selects a nearby node (Qnear) close to the placement point (Qrand), it is less recommended that the moving body 20 pass through the area where the node exists for the node existing in the space. The more, the selection criteria of the neighboring nodes close to the placement point are adjusted so that the distance from the placement point is determined to be far.

FIG. 11 is a diagram for explaining an example of a route generation method by the algorithm 4. The route creation unit 101 multiplies the distance between the placement point (Qrand) and each node existing in the space by the reciprocal of the value converted into the ratio of the recommended degree of passage in the area where each node exists, and recommends passage. The node having the shortest distance multiplied by the reciprocal of the value converted into the ratio may be determined as the proximity node (Qnear). For example, the route creation unit 101 calculates that the distance between the node q1 existing in the area C1 having the recommended passage degree of 100% and the placement point (Qrand) is “d1 × 1”. Similarly, the route creation unit 101 calculates that the distance between the node q2 existing in the area C2 having a passage recommendation level of 50% and the placement point (Qrand) is “d2 × 1 / 0.5”. do. That is, the distance between the node q2 and the placement point (Qrand) is considered to be about twice as long as the actual distance d2.

例えば図１１において、Q1とQrandとを結ぶ線分のうちエリアＣ１に含まれる部分の距離を距離Ａとし、エリアＣ２に含まれる部分の距離を距離Ｂとした場合、Q1からQrandまでの距離は、距離Ａ÷１＋距離部Ｂ÷０．５で算出される。 Further, the algorithm 4 may be the method shown below. For example, when the route creation unit 101 selects a proximity node (Qnear) close to the placement point (Qrand), the traffic recommendation level in the area existing between the proximity node (Qnear) and the placement point (Qrand) is set. The lower the distance, the farther the distance from the placement point may be, and the selection criteria of the neighboring nodes close to the placement point may be adjusted. For example, it is assumed that the line segment connecting each proximity node (Qnear) and the placement point (Qrand) passes through N areas from 1 to N. In this case, assuming that the passing distance and the recommended passage (the recommended passage in terms of ratio) in the area n are ln and Wn, respectively, the distance L'between each proximity node (Qnear) and the placement point (Qrand). Can be expressed by the following formula.

For example, in FIG. 11, when the distance of the part included in the area C1 of the line segment connecting Q1 and Qrand is defined as the distance A and the distance of the portion included in the area C2 is defined as the distance B, the distance from Q1 to Qrand is , Distance A ÷ 1 + distance part B ÷ 0.5.

According to Algorithm 4, the probability that a node existing in an area with a low traffic recommendation level or a low traffic recommendation level in an area existing between a node and a placement point is selected as a proximity node (Qnear) is high. descend. Since the line segment extends from the selected proximity node (Qnear), the probability of being selected as a proximity node (Qnear) decreases, so the probability that the line segment extends from that proximity node (Qnear) decreases. It is synonymous with doing. As the probability of line segment growth decreases, the number of line segments formed in areas with low recommended traffic decreases, and as a result, travel routes containing areas with low recommended traffic may be generated. Will also decline.

(Algorithm 5)
Algorithm 5 is an algorithm corresponding to RRT ^* . The route creation unit 101 adjusts so that the lower the traffic recommendation level in the area where the new node (Qnew) exists, the smaller the size of the predetermined range with respect to the new node (Qnew). Specifically, the size of the predetermined range based on the new node (Qnew) is calculated by multiplying the radius shown by the formula specified in the RRT ^* algorithm by the recommended passage degree (passage recommendation degree converted into a ratio). Will be done.

A specific example will be described with reference to FIG. For example, in FIG. 3, it is assumed that the radius r is A when the recommended passage degree of the area where the new node (Qnew) exists is 100%. In this case, assuming that the recommended passage rate of the area where the new node (Qnew) exists is 50%, the radius r of the circle with respect to the new node (Qnew) is A × 0.5.

According to Algorithm 5, as the size of the predetermined range with respect to the new node (Qnew) becomes smaller, the possibility that the candidate node selectable as Qmin does not exist in the predetermined range increases. Become. In other words, there is a high possibility that the connection from Qmin to Qnew will not be established. Therefore, by using the algorithm 5, it is possible to reduce the possibility that a movement route including an area with a low recommendation level is generated.

(Algorithm 6)
Algorithm 6 is an algorithm corresponding to RRT ^* . The route creation unit 101 adjusts the cost of the travel route from the departure point to each of the one or more candidate nodes so that the lower the travel recommendation level in the area through which the travel route passes, the higher the cost. do.

なお、アルゴリズム６において、ルート作成部１０１は、出発地から１以上の候補ノードの各々を経由して新ノード（Qnew）に至るまでの移動経路のコストについて、移動経路が通過するエリアにおける通行推奨度が低いほどコストが大きくなるように、移動経路のコストを調整するようにしてもよい。 Here, it is assumed that the line segment connecting the departure point to each candidate node passes through N areas from 1 to N. In this case, assuming that the passing distance through which the line segment passes through the area n and the recommended passage degree of the area n (the recommended passage degree converted into a ratio) are ln and Wn, respectively, the movement route from the departure point to each candidate node. The cost C of is expressed by the following equation.

In Algorithm 6, the route creation unit 101 recommends passage in the area through which the travel route passes, regarding the cost of the travel route from the departure point to the new node (Qnew) via each of the one or more candidate nodes. The cost of the travel route may be adjusted so that the lower the degree, the higher the cost.

According to the algorithm 6, for each of the one or more candidate nodes, the cost may be higher for the candidate node that has passed through the area with the lower recommendation level. In other words, the candidate node that has passed through the area with the lower recommendation level may be less likely to be connected to the new node (Qnew). Therefore, by using the algorithm 6, it is possible to reduce the possibility that a movement route that has passed through many areas with a low recommendation level is generated.

<Modification example>
In the movement route generated by the route generation device 10, the destination is not limited to a specific point, and may be an arbitrary point in a set of a plurality of points. For example, as shown in FIG. 12, the destination may be an area G1 having a predetermined area or volume provided in the space, or a linear area G2. In the area or space where the route generation device 10 generates a movement route, a plurality of areas represented by a set of these plurality of points may be set. When the destination is area G1, the route creation unit 101 moves between Qnew1 and the point when the distance between Qnew1 and the point closest to Qnew1 in the area G1 is equal to or less than a predetermined distance. By connecting with the line segment L1, a movement route from the starting point to the destination is generated. Similarly, when the destination is area G2, the route creation unit 101 sets Qnew2 and the point when the distance between Qnew2 and the point closest to Qnew2 in area G2 is equal to or less than a predetermined distance. By connecting the distances with a line segment L2, a movement route from the starting point to the destination is generated. This makes it possible to generate a travel route using the RRT algorithm even when the destination is not a specific point.

Further, in the N-dimensional space, the destination may be a region represented by the N-1 dimension. For example, in a three-dimensional space, the destination may be a surface (that is, a two-dimensional region). As a specific example, when the line segment reaches a height of 100 m in a three-dimensional space, it may be determined that the destination has been reached.

Further, the destination may be a topographically continuous area such as a high-voltage tower, a river, and a planned passage route of a moving body. As an example of use when the planned passage route is the destination, for example, it may be used for route search when returning to the original planned passage route when the moving object deviates from the flight route.

Further, in the present embodiment, in the area information, the passage recommendation level of the moving body applied to each of one or more areas is a line segment extending from the neighboring node (Qnear) (that is, a line segment connecting Qnear to Qrand). May be set for each direction when entering the area. For example, in the area A3 in FIG. 12, there are cases where a line segment enters the area A3 from above, a line segment enters the area A3 from the left direction, and a line segment enters the area A3 from the right direction. , Different traffic recommendation levels may be set depending on whether a line segment enters the area A3 from below.

Alternatively, in the area information, the line segment extending from the neighboring node (Qnear) (that is, the line segment connecting Qnear to Qrand) in which the passage recommendation level of the moving object applied to each of one or more areas enters the area. It may be set to change according to the angle. In this case, the recommended passage may be calculated by using a function that outputs the recommended passage by inputting the angle (or the vector of the line segment) at which the line segment enters the area.

In the example of FIG. 12, it is assumed that it is set to 30% when entering from the left direction and 80% when entering from the upper direction. This modification can be applied when generating a movement path using Algorithm 1 or Algorithm 4. Hereinafter, a specific description will be given.

First, when generating a movement route using the algorithm 1, the route creation unit 101 determines that the line segment connecting the proximity node (Qnear) to the point advanced by Δq enters the area where the recommended passage degree is set. , The length of the line segment (that is, Δq) connecting the neighboring node (Qnear) to the new node (Qnew) is shortened according to the traffic recommendation level corresponding to the direction in which the line segment enters the area or the approach angle. Place a new node (Qnew) in.

A specific example will be described with reference to FIG. In the example of FIG. 12, the line segment connecting the proximity node (Qnear3) to the point q3 advanced by Δq enters the area A3 from the left. In this case, the route creation unit 101 calculates Δq ′ assuming that the recommended passage degree is 30%. Similarly, the line segment connecting the proximity node (Qnear4) to the point q4 advanced by Δq enters the area A3 from above. In this case, the route creation unit 101 calculates Δq ′ assuming that the recommended passage degree is 80%.

Next, when the movement route is generated by using the algorithm 4, the route creation unit 101 sets the line segment connecting the proximity node (Qnear) to the placement point (Qrand) in any of the areas stored in the area information. When approaching, the distance between the proximity node (Qnear) and the placement point (Qrand) is calculated according to the traffic recommendation level corresponding to the direction in which the line segment enters the area or the approach angle.

A specific example will be described with reference to FIG. In the example of FIG. 12, the line segment connecting the proximity node (Qnear3) to the random position (Qrand) enters the area A3 from the left. In this case, the route creation unit 101 calculates the distance between the proximity node (Qnear3) and the placement point (Qrand), assuming that the passage recommendation level is 30%. Specifically, the route creation unit 101 calculates that the distance between the proximity node (Qnear3) and the placement point (Qrand) is about 3.3 times farther than the distance when the recommended passage is 100%. .. Similarly, the line segment connecting the proximity node (Qnear4) to the random position (Qrand) enters the area A3 from above. In this case, the route creation unit 101 calculates the distance between the proximity node (Qnear4) and the placement point (Qrand), assuming that the passage recommendation level is 80%. Specifically, the route creation unit 101 calculates that the distance between the proximity node (Qnear4) and the placement point (Qrand) is about 1.25 times farther than the distance when the recommended passage is 100%. ..

Further, in the present embodiment, different passage recommendation levels may be set for the area information for each algorithm. For example, in the area information shown in FIG. 6, the traffic recommendation degree corresponding to each area position is the traffic recommendation degree corresponding to the algorithm 1, the traffic recommendation degree corresponding to the algorithm 2, and the traffic recommendation degree corresponding to the algorithm 3. It may be stored separately in.

Further, in the present embodiment, the route generation device 10 may be incorporated in the moving body 20. That is, the moving body 20 may generate a moving path by itself and move. In this case, the communication network N and the communication IF 13 become unnecessary.

Further, in the present embodiment, the map data may be manufactured by storing the movement route generated by the route generation device 10 in the map data. Further, the moving body 20 may store the map data and perform a route search by selecting an arbitrary moving route from a plurality of moving routes stored in the map data. Alternatively, the moving body 20 performs a route search by selecting one of the plurality of moving routes stored in the map data by combining it with a search algorithm such as the Dijkstra method or the A * method. You may do it.

The embodiments described above are for facilitating the understanding of the present invention, and are not for limiting the interpretation of the present invention. The flowcharts, sequences, elements included in the embodiments, arrangements, materials, conditions, shapes, sizes, and the like described in the embodiments are not limited to those exemplified, and can be appropriately changed. Further, it is possible to partially replace or combine the configurations shown in different embodiments.

1 ... movement management system, 10 ... route generation device, 11 ... CPU, 12 ... storage device, 13 ... communication IF, 14 ... input device, 15 ... output device, 20 ... mobile body, 101 ... route creation unit, 102 ... route Output unit, 103 ... Storage unit

Claims (12)

It is a route creation device that creates a movement route when a moving object moves from a starting point to a destination by connecting a line segment connecting nodes.
A storage unit that stores area information in which one or more areas included in the space and a multi-valued weight value applied to each of the one or more areas are associated and stored.
To the first point arranged in the space and the second point selected from the node group including the departure point and moved by a predetermined distance from the nearby node close to the first point toward the first point. Place a new node based on the specified placement probability,
By repeating connecting the neighboring node to the new node with a line segment, a movement route to the destination is created, or
Among one or more candidate nodes existing in a predetermined range based on the new node in the node group including the departure point, the candidate node having a small cost of the movement route from the departure point and the new node are selected. By repeating connecting with a line segment, a movement route to the destination is created.
The movement route creation unit and
Have,
Based on the weight value included in the area information, the movement route creating unit has the predetermined distance, the predetermined placement probability, the selection criterion of the proximity node close to the first point, and the size of the predetermined range. And adjust at least one of the costs of the travel path from the departure point to each of the one or more candidate nodes.
Route creation device. The multi-valued weight value applied to each of the one or more areas indicates the degree to which movement of the moving object is recommended in each of the one or more areas.
The route creation device according to claim 1. The movement route creating unit adjusts so that the lower the degree to which the passage of the moving body is recommended in the area through which the line segment connecting the proximity node to the new node passes, the shorter the predetermined distance is.
The route creating apparatus according to claim 2. When arranging the new node, the movement route creating unit adjusts so that the lower the degree to which the passage of the moving body is recommended, the lower the predetermined arrangement probability.
The route creating apparatus according to claim 2 or 3. The movement route creating unit refers to nodes existing in one or more areas included in the space.
The less recommended the passage of moving objects in the area where the node is, or
The less recommended the passage of moving objects in the area between the node and the first point, the lower.
Adjust the selection criteria of the proximity node close to the first point so that the distance from the first point is determined to be far.
The route creating apparatus according to any one of claims 2 to 4. The movement route creating unit adjusts so that the smaller the degree to which the passage of the moving body is recommended in the area where the new node exists, the smaller the size of the predetermined range.
The route creating apparatus according to any one of claims 2 to 5. Regarding the cost of the movement route from the departure point to each of the one or more candidate nodes, the movement route creation unit increases the cost as the degree to which the passage of the moving body in the area through which the movement route passes is recommended. So, adjust the cost of the travel route,
The route creating apparatus according to any one of claims 2 to 6. The destination is an arbitrary point in a set of a plurality of points.
The route creating device according to any one of claims 1 to 7. The multi-valued weight value applied to each of the one or more areas is set for each direction when the line segment connecting the neighboring node to the new node enters the area or according to the approach angle.
When the movement route creating unit sets the new node, if the line segment connecting the proximity node to the new node enters any area stored in the area information, the line segment enters the area. The position of the new node is set so that the line segment connecting the neighboring node to the new node is shortened according to the weight value corresponding to the direction of entry or the approach angle.
The route creating apparatus according to any one of claims 2 to 8. It is a route creation method executed by a route creation device that creates a movement route when a moving object moves from a starting point to a destination by connecting a line segment connecting nodes.
A storage step for storing area information stored in a storage unit in which one or more areas included in the space and a multi-valued weight value applied to each of the one or more areas are associated with each other and stored.
To the first point arranged in the space and the second point selected from the node group including the departure point and moved by a predetermined distance from the nearby node close to the first point toward the first point. Place a new node based on the specified placement probability,
By repeating connecting the neighboring node to the new node with a line segment, a movement route to the destination is created, or
Among one or more candidate nodes existing in a predetermined range based on the new node in the node group including the departure point, the candidate node having a small cost of the movement route from the departure point and the new node are selected. By repeating connecting with a line segment, a movement route to the destination is created.
Travel route creation step and
Have,
The movement route creation step is based on the weight value included in the area information, the predetermined distance, the predetermined placement probability, the selection criterion of the proximity node close to the first point, and the size of the predetermined range. And adjust at least one of the costs of the travel path from the departure point to each of the one or more candidate nodes.
Route creation method. A computer that creates a movement route when a moving object moves from a starting point to a destination by connecting a line segment connecting nodes.
A storage unit that stores area information in which one or more areas included in the space and a multi-valued weight value applied to each of the one or more areas are associated and stored.
To the first point arranged in the space and the second point selected from the node group including the departure point and moved by a predetermined distance from the nearby node close to the first point toward the first point. Place a new node based on the specified placement probability,
By repeating connecting the neighboring node to the new node with a line segment, a movement route to the destination is created, or
Among one or more candidate nodes existing in a predetermined range based on the new node in the node group including the departure point, the candidate node having a small cost of the movement route from the departure point and the new node are selected. By repeating connecting with a line segment, a movement route to the destination is created.
The movement route creation unit and
To make it work
Based on the weight value included in the area information, the movement route creating unit has the predetermined distance, the predetermined placement probability, the selection criterion of the proximity node close to the first point, and the size of the predetermined range. And adjust at least one of the costs of the travel path from the departure point to each of the one or more candidate nodes.
Route creation program. A map data generation method for generating map data including the movement route created by the route creation apparatus according to any one of claims 1 to 9.

Images