Patent Description:
Systems that calculate routes for avoiding collisions with obstacles are known. For example, there is a disclosed system that calculates a route via a plurality of nodes by adding a node around a node that interferes with an obstacle and replacing the added node with the interfering node.

However, the conventional technology always searches for nodes with high calculation accuracy in order to add the nodes that are necessarily not interfering with the obstacles, which may result in increasing the route calculation time.

It is an object of the present disclosure to provide a route planning device, a route planning method, and a computer-readable medium capable of shortening the route calculation time.

<CIT> Al relates to an information processing device, mobile object, information processing method, and computer program product.

With reference to the accompanying drawings, a route planning device, a route planning method, and a route planning program will be described in detail hereinafter.

<FIG> is a schematic diagram illustrating an example of a route planning system <NUM> according to a first arrangement.

The route planning system <NUM> includes a route planning device <NUM> and a mobile body <NUM>. The route planning device <NUM> and the mobile body <NUM> are communicatively connected.

The route planning device <NUM> is an information processing device that calculates a route of the mobile body <NUM>.

The mobile body <NUM> is a movable object that moves along the route calculated by the route planning device <NUM>. The mobile body <NUM> may be a flying object, a ship, a vehicle, a robot, or the like, for example. The flying object may be a drone, an airplane, or the like, for example. The vehicle may be a four-wheel automobile, a motorbike, or the like, for example. The mobile body <NUM> may be a structure in which the position of a main body part is fixed and part of mechanisms provided to the main body part moves. For example, the mobile body <NUM> may be a robot arm. The mobile body <NUM> may be any mobile unit that moves via driving operations of a person, and any mobile body that can move autonomously without driving operations of a person. The mobile body <NUM> may be a holonomic mobile body capable of moving in all directions including forward, backward, left, right, up, down, and diagonal directions, as well as on-the-spot turning, and the like, or may be a non-holonomic mobile body.

In the present arrangement, a mode in which the mobile body <NUM> is a holonomic drone will be described as an example.

A route herein is a route that passes through a plurality of tour points defined in advance.

The tour points are points that the mobile body <NUM> ought to pass through. The tour points include a start point and a goal point, for example. The start point is a starting point of the route, that is, the point of departure. The goal point is the end point of the route, that is, the point to be the goal.

The tour points may include a plurality of points between the start point and the goal point. The points between the start point and the goal point include the points where the mobile body <NUM> executes a predetermined task on a work target, for example. The work target is, for example, a target of a task such as an inspection. Specifically, the work target may be a board surface of an instrument, or the like. The tasks defined in advance may be sensing of the work target, for example. Sensing of the work target specifically includes capturing an image of the work target, measuring various parameters of the work target, and the like.

The route planning device <NUM> calculates a route that avoids collisions with obstacles. Details of the route calculation will be described later.

The route planning device <NUM> includes a storage <NUM>, a display unit <NUM>, an input unit <NUM>, a communication unit <NUM>, and a controller <NUM>. The storage <NUM>, the display unit <NUM>, the input unit <NUM>, the communication unit <NUM>, and the controller <NUM> are communicatively connected via a bus <NUM> and the like.

The storage <NUM>, the display unit <NUM>, the input unit <NUM>, and the communication unit <NUM> may simply be configured to be connected to the controller <NUM> communicatively with wire or wirelessly. At least one of the storage <NUM>, the display unit <NUM>, and the input unit <NUM> may be connected to the controller <NUM> via a network.

At least one of the storage <NUM>, the display unit <NUM>, and the input unit <NUM> may be provided outside the route planning device <NUM>, or at least one of a single or a plurality of functional units included in the storage <NUM>, the display unit <NUM>, the input unit <NUM>, and the controller <NUM> may be loaded in an external information processing device that is communicatively connected to the route planning device <NUM> via a network, or the like.

The storage <NUM> stores various kinds of data. In the present arrangement, the storage <NUM> stores in advance obstacle information 12A, tour point information 12B, and mobile body information 12C, and the like.

The obstacle information 12A is information regarding an obstacle included in a moving target area of the mobile body <NUM>. In the present arrangement, the obstacle information 12A is information indicating the position coordinates of each of a plurality of elements configuring the obstacle in a three-dimensional space and the impact severity of each of the elements.

In more detail, the obstacle information 12A is information that expresses an obstacle <NUM> by a group of elements. A group of elements is expressed by a group of points, a group of voxels each being a unit of a regular grid in a three-dimensional space, a group of polygons each being a basic polygonal shape when an obstacle is modeled as a polyhedron, and the like. The obstacle information 12A includes the information indicating the position coordinates of each of the elements configuring the obstacle in a three-dimensional space.

The collision severity is the information indicating the severity when the mobile body <NUM> collides with the obstacle. For example, information indicating the collision severity of a higher (greater) value is given for the elements of the obstacle that imposes a more serious influence such as shutdown of the business, or the like. In the obstacle information 12A, information indicating the collision severity is given in advance for each of the elements configuring the obstacle. Hereinafter, the collision severity may be referred to as collision severity mcol.

The tour point information 12B is information indicating the position coordinates of the tour points included in the moving target area of the mobile body <NUM> in a three-dimensional space. For example, the tour point information 12B includes information indicating the position coordinates of each of the start point, the goal point, and a point or a plurality of points between the start point and the goal point. The tour point information 12B may also include information regarding at least one selected from the work content executed by the mobile body <NUM> at each of the tour points, the stopped time at the tour points, the posture of the mobile body <NUM> at the tour points, and the position coordinates and posture of the work target at the tour points.

The mobile body information 12C is information regarding the mobile body <NUM>. In the present arrangement, the mobile body information 12C includes information representing the size of the mobile body <NUM> and the obstacle avoidance performance of the mobile body <NUM>. The size of the mobile body <NUM> is information indicating the range the mobile body <NUM> occupies in an actual space. The size of the mobile body <NUM> is expressed by, for example, information indicating the maximum length in each of the directions in which the mobile body <NUM> can move.

The obstacle avoidance performance indicates the ability of the mobile body <NUM> to avoid obstacles. The obstacle avoidance performance is expressed by the presence or absence of an obstacle avoidance function, or the level of the obstacle avoidance performance. The obstacle avoidance function means a function that detects and reflexively avoid obstacles on the route. The obstacle avoidance performance is the level of the obstacle avoidance function, and the higher the obstacle avoidance performance is, the greater the value of the level of the obstacle avoidance performance becomes. In the present arrangement, a mode in which the obstacle avoidance performance is expressed by the level of obstacle avoidance performance will be described as an example.

The obstacle avoidance performance is defined by at least one selected from the observation accuracy of the mobile body <NUM> and the positioning accuracy of the mobile body <NUM>. This is because the obstacle avoidance performance is determined by the observation performance and the control performance especially for the mobile body <NUM> that moves autonomously. In other words, the success rate of obstacle avoidance can be improved when a sensor mounted on the mobile body <NUM> can measure the obstacle with high accuracy, and the success rate of obstacle avoidance can be improved when the positioning accuracy of the mobile body <NUM> is high. In the present arrangement, a mode in which the obstacle avoidance performance is determined by the observation accuracy of the mobile body <NUM> and the positioning accuracy of the mobile body <NUM> will be described as an example.

The observation accuracy of the mobile body <NUM> indicates the observation accuracy of the external world of the mobile body <NUM> acquired by the mobile body <NUM>. The observation accuracy of the mobile body <NUM> is defined by the sensor mounted on the mobile body <NUM>, the positioning accuracy of the mobile body <NUM>, and the like. The positioning accuracy of the mobile body <NUM> indicates the degree capable of accurately positioning the mobile body <NUM> at a desired position and the degree capable of more accurately achieving the desired posture. The positioning accuracy of the mobile body <NUM> is defined by the sensor mounted on the mobile body <NUM>, the accuracy of a driving mechanism of the mobile body <NUM>, and the like.

For example, the obstacle avoidance performance is expressed by a weighted sum of the observation accuracy of the mobile body <NUM> and the positioning accuracy of the mobile body <NUM>. Specifically, the obstacle avoidance performance is expressed by following equation (<NUM>).

In equation (<NUM>), mobs represents the obstacle avoidance performance. In detail, mobs represents the level of the obstacle avoidance performance. The higher the level of the obstacle avoidance performance is, the greater the value of mobs becomes. In equation (<NUM>), mo1 represents the observation accuracy. The higher the observation accuracy is, the greater the value of mo1 becomes. Note that mo2 represents the positioning accuracy. The higher the positioning accuracy is, the greater the value of mo2 becomes. Note that ko1 and ko2 represent gains. Furthermore, ko1 and ko2 may be set in advance in accordance with the mobile body <NUM>. In explanations hereinafter, the level of the obstacle avoidance performance may be referred to as the obstacle avoidance performance or the obstacle avoidance performance mobs. Furthermore, in the explanations hereinafter, the observation accuracy may be referred to as observation accuracy mo1 and the positioning accuracy may be referred to as positioning accuracy mo2.

The display unit <NUM> displays various kinds of information. The display unit <NUM> may be a display, a projection device, or the like, for example. The input unit <NUM> receives operation input made by the user. The input unit <NUM> may be a pointing device such as a mouse and a touchpad, a keyboard, or the like, for example. The display unit <NUM> and the input unit <NUM> may also be an integrated touch panel. The communication unit <NUM> is a communication interface for having communication with information processing devices outside the route planning device <NUM> and the mobile body <NUM>.

The controller <NUM> executes information processing in the route planning device <NUM>. The controller <NUM> includes a tentative route calculation module 20A, a via point addition module 20B, and an output control module 20C.

The tentative route calculation module 20A, the via point addition module 20B, and the output control module 20C are achieved by a single or a plurality of processors, for example. For example, each of the above units may also be achieved by having a processor such as a central processing unit (CPU) execute a computer program, that is, by software. Each of the above units may also be achieved by a processor such as a dedicated IC, that is, by hardware. Each of the above units may also be achieved by using a combination of software and hardware. In a case of using a plurality of processors, each of the processors may achieve one of the units or may achieve two or more of the units.

The controller <NUM> may simply need to include at least the tentative route calculation module 20A and the via point addition module 20B, and may be configured without the output control module 20C. In the present arrangement, a mode in which the controller <NUM> includes the tentative route calculation module 20A, the via point addition module 20B, and the output control module 20C will be described as an example.

The tentative route calculation module 20A calculates a tentative route. The tentative route calculation module 20A calculates a tentative route based on the tour point information 12B.

<FIG> is an explanatory diagram illustrating a calculation example of a tentative route <NUM>. In <FIG>, as an example, a space S and a virtual space SB are illustrated as two-dimensional spaces. In reality, the space S and the virtual space SB are three-dimensional spaces. In <FIG>, obstacles 46A and 46B are illustrated as examples. The obstacle 46A and the obstacle 46B are examples of the obstacle <NUM> disposed in a moving target area of the mobile body <NUM>. Furthermore, <FIG> also illustrates a tour point 40A, a tour point 40B and a tour point 40C as examples of a tour point <NUM>.

The tentative route calculation module 20A calculates a tentative route <NUM> that passes through a plurality of tour points <NUM> disposed in the virtual space SB acquired by removing the obstacle <NUM> from the space S including the obstacle <NUM> that is the moving target area of the mobile body <NUM>.

The tentative route <NUM> is expressed by a graph formed with the tour points <NUM> and edges connecting the tour points <NUM>. The tentative route calculation module 20A generates a graph having the tour points <NUM> as nodes in the virtual space SB assumed to include no obstacle <NUM>, and calculates a node sequence connecting the tour point <NUM> at the start point (for example, the tour point 40A) to the tour point <NUM> at the goal point (for example, the tour point 40C) to calculate the tentative route <NUM>.

In the present arrangement, the tentative route calculation module 20A calculates a tour route that passes through the tour points <NUM> at least once as the tentative route <NUM>. In other words, the tentative route calculation module 20A calculates the tentative route <NUM> that is drawn to go through the tour points <NUM> in a single stroke. That is, in the present arrangement, the tentative route calculation module 20A calculates the tentative route <NUM> by solving Traveling Salesman Problem (TSP). Any algorithms may be used to solve TSP. The tentative route calculation module 20A solves TSP using a cost that is the length of the edge between the tour points <NUM>. Therefore, the tentative route calculation module 20A according to the present arrangement includes a cost calculation module. Note that other indicators regarding movement may be added to the cost, such as a posture change amount of the mobile body when moving between the tour points, a movement amount in up and down directions, and the like.

<FIG> is a schematic diagram illustrating a configuration example of the tentative route calculation module 20A. In the present arrangement, the tentative route calculation module 20A includes a cost calculation module 20A1 and a tentative route search module 20A2.

The cost calculation module 20A1 calculates the cost between the tour points <NUM> disposed in the virtual space SB from which the obstacle <NUM> is removed. The cost calculation module 20A1 calculates a cost by using the length of the edge between the tour points <NUM>. That is, the cost calculation module 20A1 calculates a cost for each of the edges connecting the nodes that are the tour points <NUM>.

The tentative route search module 20A2 searches for the edge having the minimum cost so as to search for the tentative route <NUM> that is formed with the tour points <NUM> and the edge of the minimum cost that connects the tour points <NUM>.

Note that the cost calculation module 20A1 is preferable to calculate a cost with a straight edge. That is, the tentative route calculation module 20A including the cost calculation module 20A1 is preferable to calculate the tentative route <NUM> formed with the tour points <NUM> and a straight line connecting the tour points <NUM>.

With TSP, a graph is generated in which a node is connected all of the other nodes except itself. Therefore, the number of edges increases exponentially as the number of nodes increases. When the mobile body <NUM> is holonomic, the mobile body <NUM>, after reaching one tour point <NUM>, can move to a next tour point <NUM> by turning sharply, that is, discontinuously. Therefore, by making the edges connecting the tour points <NUM> included in the tentative route <NUM> straight, it is possible to generate the tentative route <NUM> that can be preferably applied to the holonomic mobile body <NUM>.

In addition, by allowing the cost calculation module 20A1 to calculate the cost of the straightened edges, it is possible to shorten the calculation time required for calculating the cost of each edge. That is, the tentative route calculation module 20A can shorten the calculation time required for calculating the tentative route <NUM> by calculating the tentative route <NUM> with the straightened edges.

The tentative route calculation module 20A calculates the tentative route <NUM> that passes through the tour points <NUM> disposed in the virtual space SB from which the obstacle <NUM> is removed. When there is no obstacle <NUM>, it is not necessary to do searching for detouring the obstacle <NUM>, and the edges connecting the tour points <NUM> are always straight. Therefore, the tentative route calculation module 20A only needs to calculate an equation for the straight line connecting the tour points <NUM>, which results in shortening the calculation time required for calculating the tentative route <NUM>.

Returning to <FIG>, the explanations will be continued.

The via point addition module 20B derives a route with one or more via points added around the interference point between the obstacle <NUM> and the tentative route <NUM> in the space S including the obstacle <NUM> that is the moving target area of the mobile body <NUM>, with a calculation accuracy corresponding to the precision of the route point calculation.

The via point addition module 20B calculates the one or more via points with a lower accuracy as the precision is lower. Furthermore, the via point addition module 20B calculates the one or more via points with a higher accuracy as the precision is higher.

<FIG> is a functional block diagram illustrating an example of the via point addition module 20B.

The via point addition module 20B includes a precision calculation module 20B1, an obstacle information change module 20B2, an interference check module 20B3, a via point search module 20B4, and a verification module 20B5. The via point addition module 20B may simply need to be configured with at least the precision calculation module 20B1 and the via point search module 20B4, and may be configured without at least one of the obstacle information change module 20B2, the interference check module 20B3, and the verification module 20B5.

The precision calculation module 20B1 calculates the precision. Precision is the information indicating the degree of precision of the via point calculation. The precision calculation module 20B1 calculates the precision based on at least one of the collision severity mcol of the obstacle <NUM> and the obstacle avoidance performance mobs of the mobile body <NUM> to be lower as the collision severity mcol is lower and to be lower as the obstacle avoidance performance mobs is higher. In other words, the precision calculation module 20B1 calculates the precision to be higher as the collision severity mcol is higher and to be higher as the obstacle avoidance performance mobs is lower.

In detail, the precision calculation module 20B1 calculates the precision by using following equations (<NUM>) and (<NUM>). <MAT> <MAT>.

In equations (<NUM>) and (<NUM>), p1 represents the first precision. Note that p2 represents the second precision. Also, kobs and kcol represent gains. Furthermore, ε is a minute number to prevent division by zero. In addition, mcol represents the collision severity mcol. Also, mobs represents the obstacle avoidance performance mobs. In the explanations hereinafter, the first precision may be referred to as the first precision p1 and the second precision may be referred to as the second precision p2.

The first precision p1 and the second precision p2 are examples of a precision p.

The first precision p1 is the precision p defined by the obstacle avoidance performance mobs. As indicated in equation (<NUM>), the first precision p1 takes a higher value as the obstacle avoidance performance mobs is lower. Furthermore, the first precision p1 takes a lower value as the obstacle avoidance performance mobs is higher.

The second precision p2 is the precision p defined by the collision severity mcol and the obstacle avoidance performance mobs. As indicated in equation (<NUM>), the second precision p2 takes a lower value as the obstacle avoidance performance mobs is higher, and takes a lower value as the collision severity mcol is lower. Furthermore, the second precision p2 takes a higher value as the obstacle avoidance performance mobs is lower, and takes a higher value as the collision severity mcol is higher.

The precision calculation module 20B1 calculates the first precision p1 by using the obstacle avoidance performance mobs included in the mobile body information 12C and equation (<NUM>) described above. Furthermore, the precision calculation module 20B1 calculates the second precision p2 for each element by using the collision severity mcol of each of the elements configuring the obstacle <NUM> included in the obstacle information 12A and the calculated first precision p1.

The precision calculation module 20B1 outputs the precision p including the calculated first precision p1 and second precision p2 to the obstacle information change module 20B2, the interference check module 20B3, and the via point search module 20B4.

The obstacle information change module 20B2 changes the density of a group of elements in the obstacle information 12A of the obstacle <NUM> that is expressed by the group elements to a lower density as the precision p is lower. In the present arrangement, the obstacle information change module 20B2 changes the density of the group of elements to a lower density as the second precision p2 is lower. The reason is that it is necessary to find a route not colliding, that is, not interfering with the obstacle <NUM> more strictly as the obstacle avoidance performance mobs of the mobile body <NUM> is lower.

<FIG> are explanatory diagrams illustrating examples of a change in the obstacle information 12A. <FIG> illustrates an example of the density of a group of elements <NUM> when the second precision p2 is high. <FIG> illustrates an example of the density of a group of elements <NUM> when the second precision p2 is low.

As described above, the obstacle information 12A is the information that expresses the obstacle <NUM> by a group of the elements <NUM> such as a group of points, a group of voxels each being a unit of a regular grid in a three-dimensional space, a group of polygons each being a basic polygonal shape when an obstacle is modeled as a polyhedron, and the like. <FIG> illustrate examples of a case where the group of the elements <NUM> is a group of voxels.

For example, it is assumed that the density of the group of the elements <NUM> indicated by the obstacle information 12A acquired from the storage <NUM> is the density illustrated in <FIG>.

When the second precision p2 is the low precision p that is equal to or lower than a threshold, for example, the obstacle information change module 20B2 changes the obstacle information 12A to the obstacle information 12A in which the density of the group of the elements <NUM> is lowered.

For example, the obstacle information change module 20B2 generates the obstacle information 12A in which the density of the group of the elements <NUM> illustrated in <FIG> is changed to the group of the elements <NUM> with a lower density illustrated in <FIG> by increasing the size of the voxels that are the elements <NUM> indicated by the obstacle information 12A read out from the storage <NUM>. That is, <FIG> illustrate a scene of changing the density of the group of the elements <NUM> by changing the size of the voxels as an example.

Note that the obstacle information change module 20B2 may generate the obstacle information 12A changed to the group of the elements <NUM> with a still lower density by thinning out the voxels that are the elements <NUM> indicated by the obstacle information 12A read out from the storage <NUM>.

Furthermore, the obstacle information change module 20B2 may calculate the obstacle information 12A of the group of the elements <NUM> with a lower density as the second precision p2 is lower, by using a function or the like that derives the group of the elements <NUM> with a lower density as the second precision p2 becomes lower.

<FIG> are explanatory diagrams illustrating examples of a change in the obstacle information 12A. <FIG> illustrates an example of the density of a group of the elements <NUM> when the second precision p2 is high. <FIG> illustrates an example of the density of a group of the elements <NUM> when the second precision p2 is low. <FIG> illustrate examples of a case where the group of the elements <NUM> is a group of polygons.

When the second precision p2 is the low precision p that is equal to or lower than a threshold, for example, the obstacle information change module 20B2 changes the obstacle information 12A to the obstacle information 12A in which the density of the group of the elements <NUM> is lowered. For example, the obstacle information change module 20B2 generates the obstacle information 12A in which the density of the group of the elements <NUM> illustrated in <FIG> is changed to the group of the elements <NUM> with a lower density illustrated in <FIG> by increasing the size of the polygons that are the elements <NUM> indicated by the obstacle information 12A read out from the storage <NUM>. That is, <FIG> illustrate a scene of changing the density of the group of the elements <NUM> by changing the size of the polygons as an example.

Note that the obstacle information change module 20B2 may generate the obstacle information 12A changed to the group of the elements <NUM> with still lower density by thinning out the polygons that are the elements <NUM> indicated by the obstacle information 12A read out from the storage <NUM>.

Similarly, for the case where the group of the elements <NUM> is a point group, the obstacle information change module 20B2 may change the obstacle information 12A to be the group of the elements <NUM> with a higher density as the second precision p2 is higher and to be the group of the elements <NUM> with a lower density as the second precision p2 is lower.

By having the obstacle information change module 20B2 change the density of the group of the elements <NUM> in the obstacle information 12A to be a lower density as the second precision p2 is lower, the interference check module 20B3 to be described later can reduce the number of repetitions of collision checks, thereby making it possible to shorten the calculation time.

In detail, by having the obstacle information change module 20B2 thin out the polygons, voxels, or points that are the elements <NUM> expressed by the obstacle information 12A read from the storage <NUM> more as the second precision p2 becomes lower, the interference check module 20B3 to be described later can reduce the number of the elements <NUM> that are the target of interference checking. Therefore, it is possible to shorten the calculation time of the interference check module 20B3 by performing the changing processing of the obstacle information 12A according to the second precision p2 by the obstacle information change module 20B2.

Furthermore, by having the obstacle information change module 20B2 enlarge the size of the polygons or voxels that are the elements <NUM> expressed by the obstacle information 12A read from the storage <NUM> more as the second precision p2 becomes lower, the interference check module 20B3 to be described later can reduce the number of the elements <NUM> that are the target of interference checking. Therefore, it is possible to shorten the calculation time of the interference check module 20B3 by performing the changing processing of the obstacle information 12A according to the second precision p2 by the obstacle information change module 20B2.

The obstacle information change module 20B2 is preferable to adjust the size of the enlarged polygons or voxels such that the size of a single polygon or a single voxel after being enlarged becomes less than the overall circumscribed size of a single obstacle <NUM>. By adjusting the size of a single polygon or a single voxel after being enlarged to be less than the overall circumscribed size of a single obstacle <NUM>, it is possible to suppress deterioration in the interference checking performance of the interference check module 20B3 to be described later.

Furthermore, the obstacle information change module 20B2 changes the density of the group of the elements <NUM> in the obstacle information 12A to be a lower density as the second precision p2 becomes lower, that is, as the obstacle avoidance performance mobs becomes higher. The higher the obstacle avoidance performance mobs of the mobile body <NUM> is, the higher the performance thereof in moving by avoiding the obstacle <NUM>. Therefore, the obstacle information change module 20B2 can derive the obstacle information 12A that can suppress collisions with the obstacle <NUM> and shorten the calculation time of the interference check module 20B3 to be described later.

Furthermore, the obstacle information change module 20B2 changes the density of the group of the elements <NUM> in the obstacle information 12A to be a higher density as the second precision p2 becomes higher, that is, as the obstacle avoidance performance mobs becomes lower.

Therefore, the obstacle information change module 20B2 can derive the obstacle information 12A that can check the interference with a high accuracy by the interference check module 20B3 to be described later according to the obstacle avoidance performance mobs of the mobile body <NUM>.

Next, the interference check module 20B3 will be described. The interference check module 20B3 identifies interference points between the tentative route <NUM> and the obstacle <NUM>.

<FIG> is an explanatory diagram illustrating an example when identifying an interference point C by the interference check module 20B3. In <FIG>, the tentative route <NUM> and the tour point 40C not interfering with each other are omitted in order to focus on the interference area. In <FIG>, as an example, the space S and the virtual space SB are illustrated as two-dimensional spaces. In reality, the space S and the virtual space SB are three-dimensional spaces.

The interference check module 20B3 receives the tentative route <NUM> from the tentative route calculation module 20A. Furthermore, the interference check module 20B3 receives, from the obstacle information change module 20B2, the obstacle information 12A that is changed in the obstacle information change module 20B2. When the obstacle information 12A is not changed in the obstacle information change module 20B2, the interference check module 20B3 may simply receive the unchanged obstacle information 12A from the obstacle information change module 20B2. The interference check module 20B3 checks the interference between the obstacle <NUM> indicated in the received obstacle information 12A and the tentative route <NUM>, and identifies the interfering interference point C.

When the group of the elements <NUM> indicated in the obstacle information 12A is a group of points, the interference check module 20B3 converts it to a group of voxels or polygons, and checks interference thereof with the tentative route <NUM>.

For each of the elements <NUM> expressed in the obstacle information 12A, the interference check module 20B3 checks an intersection with a line segment represented by the tentative route <NUM> to check the interference between the tentative route <NUM> and the obstacle <NUM>. In detail, for each of the elements <NUM> expressed by a group of voxels or a group of polygons, the interference check module 20B3 checks the interference between the face of the voxel or polygon that is the element <NUM> and the tentative route <NUM> to identify the interference point C. Then, the interference check module 20B3 outputs, as interference point information, the position coordinates of the interfering interference point C and the identification information of the tour points <NUM> disposed at both ends of the edge where the interference point C exists.

Note that the interference check module 20B3 may identify the interference point C between the tentative route <NUM> and an obstacle area <NUM> in which a wider margin area M is added around the obstacle <NUM> as the precision p is higher.

In detail, the interference check module 20B3 sets the obstacle area <NUM> in which a wider margin area M is added around the obstacle <NUM> as the second precision p2 becomes higher.

<FIG> illustrates, as an example, the obstacle 46A indicated by the obstacle information 12A with the high second precision p2 and a high density of the group of the elements <NUM>, and the obstacle 46B indicated by the obstacle information 12A with the low second precision p2 and a low density of the group of the elements <NUM>. In this case, the interference check module 20B3 sets the obstacle area <NUM> with the wider margin area M for the obstacle 46A, and sets the obstacle area <NUM> with the narrower margin area M for obstacle 46B.

Then, the interference check module 20B3 checks the intersection of the obstacle area <NUM> with the tentative route <NUM> for each of the elements <NUM> of each of the obstacles 46A and 46B disposed in the space S. In the example illustrated in <FIG>, the second precision p2 of each of the elements <NUM> of the obstacle 46A is higher than the second precision p2 of each of the elements <NUM> of the obstacle 46B. That is, the density of the group of the elements <NUM> indicated by the obstacle information 12A of the obstacle 46A is higher than the density of the group of the elements <NUM> indicated by the obstacle information 12A of the obstacle 46B. Therefore, also for the margin area M, the interference check module 20B3 may simply check the intersection with the tentative route <NUM> for each of the elements <NUM> in a density that matches the density of the group of the elements <NUM> indicated by the obstacle information 12A of the obstacle <NUM> including the margin area M.

In the example illustrated in <FIG>, for example, the interference check module 20B3 identifies an interference point C1, an interference point C2, an interference point C3, and an interference point C4 as interference points C. Then, the interference check module 20B3 outputs the interference point information that includes each of those interference points C and identification information of each of the tour point 40A and the tour point 40B, which are the tour points <NUM> at both ends of each of the edges that include each of the interference points C.

In detail, for example, the interference check module 20B3 outputs the interference point information that includes the interference point C1 and the identification information of each of the tour point 40A and the tour point 40B, which are the tour points <NUM> at both ends of the edges including the interference point C1 on the tentative route <NUM>. Furthermore, the interference check module 20B3 outputs the interference point information that includes the interference point C2 and the identification information of each of the tour point 40A and the tour point 40B, which are the tour points <NUM> at both ends of the edges including the interference point C2 on the tentative route <NUM>. Furthermore, the interference check module 20B3 outputs the interference point information that includes the interference point C3 and the identification information of each of the tour point 40A and the tour point 40B, which are the tour points <NUM> at both ends of the edges including the interference point C3 on the tentative route <NUM>. Furthermore, the interference check module 20B3 outputs the interference point information that includes the interference point C4 and the identification information of each of the tour point 40A and the tour point 40B, which are the tour points <NUM> at both ends of the edges including the interference point C4 on the tentative route <NUM>.

The interference check module 20B3 checks the intersection of the obstacle area <NUM> with the tentative route <NUM> for each of the elements <NUM> of each of the obstacles 46A and 46B disposed in the space S. The density of the group of the elements <NUM> is the density changed by the obstacle information change module 20B2 according to the second precision p2. Therefore, the interference check module 20B3 can check the intersection of the obstacle area <NUM> with the tentative route <NUM> with a calculation accuracy corresponding to the precision p by checking the intersection of each of the elements <NUM> with the tentative route <NUM>.

Furthermore, the density of the group of elements <NUM> indicated by the obstacle information 12A of the obstacle 46B is changed to be lower than the density of the group of the elements <NUM> indicated by the obstacle information 12A of the obstacle 46A according to the second precision p2. Therefore, the interference check module 20B3 can shorten the calculation time required for checking the interference by checking the interference with the tentative route <NUM> for each of the elements <NUM> indicated in the obstacle information 12A that is changed according to the second precision p2.

Furthermore, the interference check module 20B3 sets the obstacle area <NUM> in which the wider margin area M is added around the obstacle <NUM> as the second precision p2 becomes higher. Having the higher second precision p2 means that at least one of the observation accuracy of the mobile body <NUM> and the positioning accuracy of the mobile body <NUM> is low. The interference check module 20B3 can identify the interference point C with a higher accuracy according to the obstacle avoidance performance mobs of the mobile body <NUM> by adding the wider margin area M around the obstacle <NUM> as the second precision p2 becomes higher.

Note that the minimum value of the margin area M may be defined to be the size of the mobile body <NUM> included in the mobile body information 12C. By setting the minimum value of the margin area M to be the size of the mobile body <NUM>, the interference check module 20B3 can check the interference between the tentative route <NUM> and the obstacle <NUM> with a higher accuracy.

Next, the via point search module 20B4 will be described. The via point search module 20B4 searches the search space with a search accuracy corresponding to the precision p, and adds one or more via points around the interference point C. Then, the via point search module 20B4 derives a route by adding the one or more via points to the tentative route <NUM>.

The via point search module 20B4 receives the tentative route <NUM> from the tentative route calculation module 20A. Furthermore, the interference check module 20B3 receives, from the obstacle information change module 20B2, the obstacle information 12A that is changed in the obstacle information change module 20B2. When the obstacle information 12A is not changed in the obstacle information change module 20B2, the via point search module 20B4 may simply receive the unchanged obstacle information 12A from the obstacle information change module 20B2. Furthermore, the via point search module 20B4 receives, from the interference check module 20B3, the interference point information including the interference point C and the identification information of each of the tour points <NUM> at both ends of the edge including the interference point C on the tentative route <NUM>. In addition, the via point search module 20B4 receives the precision p from the precision calculation module 20B1.

The via point search module 20B4 searches the search space by using the tentative route <NUM>, the obstacle information 12A, the interference point information, and the precision p, and adds the one or more via points. Then, the via point search module 20B4 derives a route <NUM> by adding the one or more via points to the tentative route <NUM>. A series of processing performed by the via point search module 20B4 for searching the search space, adding the via points, and deriving the route <NUM> may be referred and described as route derivation processing.

<FIG> are explanatory diagrams illustrating examples of the route derivation processing performed by the via point search module 20B4. <FIG> is an explanatory diagram illustrating an example of a case where the first precision p1 is high. <FIG> is an explanatory diagram illustrating an example of a case where the first precision p1 is low. The high first precision p1 means that the first precision p1 is equal to or more than a threshold determined in advance. The low first precision p1 means that the first precision p1 is less than the threshold.

The via point search module 20B4 searches a search space SS. Algorithms such as Rapidly exploring random tree (RRT), A-star (A*), and Dijkstra's algorithm may be used for the search methods. These search methods dispose search points in a grid form or randomly in the search space SS, and search the search space SS for each of the search points. <FIG> illustrate a series of search points arranged in a grid form as an example.

The via point search module 20B4 sets a search interval σ to be longer as the first precision p1 is lower. In addition, the via point search module 20B4 sets the search interval σ to be shorter as the first precision p1 is higher. Therefore, as illustrated in <FIG>, when the first precision p1 is high, the via point search module 20B4 sets the search interval σ to be shorter than when the first precision p1 is low. On the other hand, as shown in <FIG>, when the first precision p1 is low, the via point search module 20B4 sets the search interval σ to be longer than when the first precision p1 is high.

Then, the via point search module 20B4 searches the search space SS for each search point at the search interval σ set according to the first precision p1, from the tour point 40A at the start point toward the tour point 40B at the goal point. At this time, the via point search module 20B4 searches the search space SS for each search point at the set search interval σ such that the cost expressed by the distance from the tentative route <NUM> is lower and that the interference point C and the obstacle area <NUM> indicated by the interference point information are not interfered (see arrow <NUM>). The via point search module 20B4 may use the obstacle area <NUM> that is set up in the similar manner as that of the interference check module 20B3. Note that the via point search module 20B4 may narrow the search range by searching the search space SS by having a search point in the surroundings of the first interference point C (for example, the interference point C1) between the tentative route <NUM> and the obstacle <NUM> as the start point.

Then, the via point search module 20B4 adds one or more via points <NUM> to the search points that are searched at each search interval σ such that the cost expressed by the distance from the tentative route <NUM> is lower and that the interference point C and the obstacle area <NUM> indicated by the interference point information are not interfered. Note that the via point search module 20B4 may selectively add the via point <NUM> to the search point where the search direction is changed.

For example, in the case of the example illustrated in <FIG> with the high first precision p1, the via point search module 20B4 searches for the search point that satisfies the above condition for each search interval σ narrower than the search interval σ of the low first precision p1 illustrated in <FIG>, and adds a via point 48A, a via point 48B, and a via point 48C as the via points <NUM>.

Furthermore, in the case of the example illustrated in <FIG> with the low first precision p1, the via point search module 20B4 searches for the search point that satisfies the above condition for each search interval σ wider than the search interval σ of the high first precision p1 illustrated in <FIG>, and adds the via point 48A, the via point 48B, and the via point 48C as the via points <NUM>.

Note that the via points <NUM> and the search directions illustrated in <FIG> are examples, and are not limited to the mode illustrated in <FIG>.

Furthermore, <FIG> illustrate, as an example, the case where each of the intersection points of a search grid at the search interval σ is the search point. However, the search point may also be a position between the intersections (vertices) of each of the four sides configuring the search grid.

As described, the via point search module 20B4 disposes the search points in the search space SS, and searches the search space SS for each of the search points. That is, the via point search module 20B4 does not search the area between the previous search point and the current search point. Therefore, the via point search module 20B4 can shorten the search time.

Furthermore, the via point search module 20B4 sets the search interval σ to be longer as the first precision p1 becomes lower, and searches the search space SS for each of the search points at the search interval σ. Therefore, the via point search module 20B4 can search the search space SS with a coarser search accuracy as the first precision p1 is lower, and add the via points <NUM>. As a result, the via point search module 20B4 can search the search space SS with the search accuracy corresponding to the precision p, thereby making it possible to shorten the search time.

Then, upon completing the search of the search space SS, the via point search module 20B4 adds the via points <NUM> to the tentative route <NUM> by inserting the via points <NUM> as the solution obtained by the search and the second precisions p2i of each of the via points <NUM> to the tentative route <NUM>.

In detail, the via point search module 20B4 inserts the identification of the via points <NUM> between the identification information of the tour points <NUM> disposed at both ends of the edges of the interference points C, which avoid interference by the via points <NUM>, on the tentative route <NUM>. For the identification information of the via points <NUM>, information that can be identified as not being the identification information of the tour points <NUM> but being the identification information of the via points <NUM> may be used. For example, for the identification information of the via points <NUM>, numbers with different number of digits with respect to the numbers of the identification information of the tour points <NUM> may be used.

Furthermore, the via point search module 20B4 gives, to the via points <NUM>, the second precision p2 of the elements <NUM> at the interference points C in the obstacle <NUM> avoided by the via points <NUM>, as the second precision p2i of the via points <NUM>. The via point search module 20B4 may give the linking information or the like capable of identifying the second precision p2i to the via points <NUM>.

The via point search module 20B4 derives the tentative route <NUM> with the added via points <NUM> as the route <NUM>. Note that the via point search module 20B4 may derive, as the route <NUM>, a graph formed with the tour points <NUM> included in the tentative route <NUM>, the added via points <NUM>, and edges connecting the points including the tour points <NUM> and the via points <NUM>. In this case, the via point search module 20B4 can derive the route <NUM> that can be preferably applied to the holonomic mobile body <NUM> by calculating the route <NUM> with the straight edges connecting the points. Furthermore, in this case, the via point search module 20B4 can shorten the time required for deriving the route <NUM>.

Returning to <FIG>, the explanations will be continued. When the total length of the route <NUM> derived by the via point search module 20B4 is less than the length acquired by adding a threshold to the total length of the tentative route <NUM> used in calculation of the route <NUM>, the verification module 20B5 identifies the route <NUM> as the output target route <NUM>.

The route <NUM> derived by adding the via points <NUM> between the tour points <NUM> by the via point search module 20B4 may become the route <NUM> indicating an unnecessary detour due to the positions and the like of the tour points <NUM>. The reason why the route <NUM> indicating an unnecessary detour is derived may be that connections between the points including the tour points <NUM> and the via points <NUM> are not appropriate.

Therefore, when the total length of the route <NUM> derived by the via point search module 20B4 is equal to or longer than the length acquired by adding the threshold to the total length of the tentative route <NUM> used in calculation of the route <NUM>, the verification module 20B5 determines it as the route <NUM> indicating an unnecessary detour, and excludes the route <NUM> from the target to be output to the output control module 20C. Furthermore, when the total length of the route <NUM> derived by the via point search module 20B4 is less than the length acquired by adding the threshold to the total length of the tentative route <NUM> used in calculation of the route <NUM>, the verification module 20B5 determines it as not being the route <NUM> indicating an unnecessary detour, and identifies the route <NUM> as the output target route <NUM>. Then, the verification module 20B5 outputs the identified route <NUM> to the output control module 20C. The threshold used to calculate the added length may be defined in advance.

Returning to <FIG>, the explanations will be continued. The via point addition module 20B may derive the route <NUM> to which the via points <NUM> are added by the route derivation processing described above, and may also derive the route <NUM> acquired by adding the input via points <NUM> to the tentative route <NUM>.

For example, the via point addition module 20B displays the tentative route <NUM> calculated by the tentative route calculation module 20A and the obstacle <NUM> indicated by the obstacle information 12A on the display unit <NUM>. The user sets the via points <NUM> at positions by avoiding interference with the obstacle <NUM> by operating the input unit <NUM> while viewing the tentative route <NUM> displayed on the display unit <NUM>. The user may input the position coordinates of the via points <NUM> in the space S by operating the input unit <NUM>. The user may also indicate the positions of the via points <NUM> on the display screen for the displayed tentative route <NUM> by operating the input unit <NUM>. In this case, the via point addition module 20B may calculate the positions of the via points <NUM> in the space S from the relative positions of the via points <NUM> indicated for the tentative route <NUM> on the display screen.

Then, the interference check module 20B3 of the via point addition module 20B checks interference between the route <NUM>, which is acquired by inserting the received via points <NUM> to the tentative route <NUM>, with the obstacle <NUM> and, when there is interference, displays interference information indicating the interference on the display unit <NUM>. The user may change the positions of the via points <NUM> by operating the input unit <NUM> while checking the interference information displayed on the display unit <NUM>.

When the route <NUM> acquired by inserting the received or changed via points <NUM> to the tentative route <NUM> does not interfere with the obstacle <NUM>, the via point addition module 20B may output the route <NUM> to the output control module 20C as the output target route <NUM>.

By using the via points <NUM> received from the user in the via point addition module 20B, the route planning device <NUM> according to the present arrangement can be applied also to systems where the above route derivation processing is difficult to execute. For example, as described above, there may be a case where the total length of the route <NUM> derived by the via point search module 20B4 is equal to or longer than the added length, so that the verification module 20B5 determines that it is the route <NUM> indicating an unnecessary detour and excludes the route <NUM> from output target for the output control module 20C. In that case, it is possible to derive the output target route <NUM> by using the via points <NUM> received from the user in the via point addition module 20B.

Next, the output control module 20C will be described.

The output control module 20C outputs the route <NUM> received from the via point addition module 20B. For example, the output control module 20C outputs the route <NUM> received from the via point addition module 20B to the mobile body <NUM> and the display unit <NUM>.

Upon receiving the route <NUM> from the via point addition module 20B, the output control module 20C may output the route <NUM> to the mobile body <NUM> and the display unit <NUM>. Furthermore, the output control module 20C may display the route <NUM> on the display unit <NUM> upon receiving an instruction to display the route <NUM> by an operation instruction or the like of the user via the input unit <NUM>. Also, the output control module 20C may transmit the route <NUM> to the mobile body <NUM> via the communication unit <NUM> upon receiving an instruction to transmit the route <NUM> to the mobile body <NUM> by an operation instruction or the like of the user via the input unit <NUM>. Furthermore, the output control module 20C may store the route <NUM> in the storage <NUM> or transmit it to an external information processing device via the communication unit <NUM> and a network.

Upon receiving the route <NUM>, the mobile body <NUM> acquires the three-dimensional position coordinates of each of the tour points <NUM> and the via points <NUM> indicated on the route <NUM> and moves along the route <NUM> by sequentially moving to the positions indicated by the three-dimensional position coordinates. The route <NUM> may be information that includes the three-dimensional position coordinates of each of the tour points <NUM> and the via points <NUM>. Furthermore, the route <NUM> may also include information indicating where the three-dimensional position coordinates of each of the tour points <NUM> and the via points <NUM> are stored. Furthermore, the route <NUM> may include information regarding at least one selected from the work content executed by the mobile body <NUM> at each of the tour points <NUM> and the via points <NUM>, the stopped time at the points, the posture of the mobile body <NUM> at the points, and the position coordinates and the posture of the work target at the points. In this case, the via point addition module 20B may read out the information from the tour point information 12B and derive the route <NUM>.

Upon receiving the route <NUM>, the display unit <NUM> displays the received route <NUM>. The output control module 20C is preferable to display the tour points <NUM> and the via points <NUM> included in the route <NUM> in different display modes on the display unit <NUM>. By displaying the tour points <NUM> and the via points <NUM> in different display modes on the display unit <NUM>, the tour points <NUM> and the via points <NUM> can be provided to the user in an easily identifiable manner.

For example, the output control module 20C displays, on the display unit <NUM>, the tour points <NUM> and via points <NUM> included in the route <NUM> in display modes that are different in at least one of color, shape, and size. The output control module 20C may also display each of the tour points <NUM> on the display unit <NUM> in a display mode corresponding to the value of the second precision p2i given to the tour points <NUM>. The output control module 20C may also display the value of the second precision p2i given to the via points <NUM> in the vicinity of the display area of the via points <NUM> indicating the second precision p2i. The output control module 20C may also acquire the second precision p2 of each of all elements <NUM> included in the search space SS, and display it at the corresponding positions on the display screen of the display unit <NUM>. Furthermore, the output control module 20C may display the second precision p2 on the display screen in colors corresponding to the values of the second precision p2.

Also, upon receiving instruction information that includes at least one of an instruction to add an additional via point to the route <NUM> displayed on the display unit <NUM> and an instruction to change the positions of the via points <NUM> included in the route <NUM>, the output control module 20C may change the route <NUM> based on the instruction information.

For example, the user operates the input unit <NUM> while viewing the route <NUM> displayed on the display unit <NUM> to perform operations such as changing the positions of the via points <NUM> included in the displayed route <NUM>, adding an additional via point that is a new via point <NUM>, and the like. For example, the positions of the via points <NUM> included in the displayed route <NUM> can be changed when the user performs a dragging operation or the like of a mouse as the input unit <NUM>. Furthermore, the user may also change the connection relationship of the edges connecting the points including the tour points <NUM> and the via points <NUM> by operating the input unit <NUM>.

Upon receiving the instruction information such as an instruction to add an additional via point to the route <NUM> displayed on the display unit <NUM>, an instruction to change the positions of the via points <NUM> included in the route <NUM>, and an instruction to change the connection relationship of the edges connecting the points, the output control module 20C changes the route <NUM> to be the route <NUM> that corresponds to the instruction information.

Therefore, the output control module 20C can change the route <NUM> derived by the via point addition module 20B to be the route <NUM> upon which the user's intention is reflected.

Next, an example of a flow of the information processing executed by the route planning device <NUM> according to the present arrangement will be described.

<FIG> is a flowchart illustrating an example of the flow of the information processing executed by the route planning device <NUM> according to the present arrangement.

The tentative route calculation module 20A calculates the tentative route <NUM> (step S100). The tentative route calculation module 20A calculates the tentative route <NUM> based on the tour point information 12B.

Then, the output control module 20C displays the tentative route <NUM> calculated at step S100 on the display unit <NUM> (step S102).

Thereafter, the precision calculation module 20B1 calculates the precision p (step S104). In the present arrangement, the precision calculation module 20B1 calculates the first precision p1 and the second precision p2.

The obstacle information change module 20B2 determines whether the mobile body <NUM> has the obstacle avoidance performance mobs (step S106). For example, the obstacle information change module 20B2 executes the determination of step S106 by determining whether the second precision p2 calculated at step S104 is the low precision p that is equal to or lower than the threshold.

When determined negative at step S106 (No at step S106), the processing proceeds to step S110 to be described later. When determined positive at step S106 (Yes at step S106), the processing proceeds to step S108.

At step S108, the obstacle information change module 20B2 changes the density of the group of the elements <NUM> indicated in the obstacle information 12A acquired from the storage <NUM> to a lower density as the second precision p2 calculated at step S104 is lower (step S108).

The interference check module 20B3 checks the interference between the tentative route <NUM> and the obstacle <NUM> by using the tentative route <NUM> calculated at step S100 and the obstacle information 12A changed at step S108 or the obstacle information 12A that is not changed because the determination at step S106 is negative (step S110). By the processing of step S110, the interference points C between the tentative route <NUM> and the obstacle <NUM> are identified, and the position coordinates of the interference points C and the identification information of the tour points <NUM> disposed at both ends of the edges where the interference points C exist are output as the interference point information.

The via point search module 20B4 searches the search space SS with the search accuracy corresponding to the precision p calculated at step S104, and adds the via points <NUM> around the interference points C (step S112). Then, the via point search module 20B4 derives the route <NUM> by adding the via points <NUM> to the tentative route <NUM>.

The verification module 20B5 verifies the route <NUM> that is derived at step S112 (step S114). At step S114, when the total length of the route <NUM> derived at step S112 is less than the length acquired by adding the threshold to the total length of the tentative route <NUM> used in calculation of the route <NUM>, the verification module 20B5 identifies the route <NUM> as the output target route <NUM>.

Next, the output control module 20C determines whether the via points <NUM> are received from the input unit <NUM> by an operation instruction of the user via the input unit <NUM> (step S116). When determined negative at step S116 (No at step S116), the processing proceeds to step S118.

At step S118, the output control module 20C outputs the route <NUM> verified at step S114 or the route <NUM> determined negative at step S120 to be described later to the mobile body <NUM> and the display unit <NUM> (step S118). Then, the present routine is terminated.

In the meantime, when determined positive at step S116 (Yes at step S116), the processing proceeds to step S120. At step S120, the interference check module 20B3 of the via point addition module 20B determines whether the obstacle <NUM> interferes with the route <NUM> that is acquired by inserting the via points <NUM> received at step S116 to the tentative route <NUM> (step S120). When determined at step S120 that there is no interference (No at step S120), the processing proceeds to step S118 described above.

When determined at step S120 that there is interference (Yes at step S120), the processing proceeds to step S122.

At step S122, the output control module 20C displays the interference information indicating the interference on the display unit <NUM> (step S122). The user changes the positions of the via points <NUM> by operating the input unit <NUM> while checking the interference information displayed on the display unit <NUM>.

The via point addition module 20B receives the change in the positions of the via points <NUM> from the input unit <NUM> (step S124). Then, returning to step S120, the interference check module 20B3 of the via point addition module 20B may determine whether the obstacle <NUM> interferes with the route <NUM> that is acquired by inserting the via points <NUM> changed at step S124 to the tentative route <NUM>.

As described above, the route planning device <NUM> according to the present arrangement includes the tentative route calculation module 20A and the via point addition module 20B. The tentative route calculation module 20A calculates the tentative route <NUM> that passes through the tour points <NUM> disposed in the virtual space SB acquired by removing the obstacle <NUM> from the space S including the obstacle <NUM>. The via point addition module 20B derives the route <NUM> with one or more via points <NUM> added around the interference points C between the obstacle <NUM> and the tentative route <NUM> included in the space S with the calculation accuracy corresponding to the precision p of the via point calculation.

Note here that the conventional technology always searches for the via points <NUM> with a high calculation accuracy in order to add the via points <NUM> that are necessarily not interfering with the obstacle <NUM>, which may result in increasing the route calculation time.

On the contrary, the route planning device <NUM> according to the present arrangement derives the route <NUM> with one or more via points <NUM> added around the interference points C between the obstacle <NUM> and the tentative route <NUM> included in the space S with the calculation accuracy corresponding to the precision p.

As described, since the route planning device <NUM> according to the present arrangement can change the calculation accuracy of the precision p according to the precision p, it is possible to shorten the route calculation time compared to the case where the route <NUM> is always derived with a high calculation accuracy regardless of the precision p.

Therefore, the route planning device <NUM> according to the present arrangement can shorten the route calculation time.

The first arrangement has been described above by referring, as an example, to the mode that derives the route <NUM> by using the tentative route <NUM> of the lowest cost calculated by the tentative route calculation module 20A. The second arrangement will be described by referring to a mode that derives the route <NUM> for each of a plurality of tentative routes <NUM> calculated in the tentative route calculation module 20A, and determines the suboptimal route <NUM> from the derived routes <NUM>.

In the present arrangement, same reference signs are applied to functions and components same as those of the first arrangement, and detailed explanations thereof are omitted.

<FIG> is a schematic diagram illustrating an example of a route planning system 1B according to the present arrangement.

The route planning system 1B includes a route planning device 10B and the mobile body <NUM>. The route planning device 10B and the mobile body <NUM> are communicatively connected. The mobile body <NUM> is the same as that of the first arrangement.

The route planning device 10B includes the storage <NUM>, the display unit <NUM>, the input unit <NUM>, the communication unit <NUM>, and a controller <NUM>. The storage <NUM>, the display unit <NUM>, the input unit <NUM>, the communication unit <NUM>, and the controller <NUM> are communicatively connected via the bus <NUM> and the like. The route planning device 10B is the same as the route planning device <NUM> of the first arrangement described above, except that it includes the controller <NUM> instead of the controller <NUM>.

The controller <NUM> includes a tentative route calculation module 21A, a route selection module 21D, the via point addition module 20B, a cost calculation module 21E, a route determination module 21F, and the output control module 20C. The tentative route calculation module 21A, the route selection module 21D, the via point addition module 20B, the cost calculation module 21E, the route determination module 21F, and the output control module 20C are achieved by a single or a plurality of processors, for example. For example, each of the above units may be achieved by having a processor such as a CPU execute a computer program, that is, by software. Each of the above units may also be achieved by a processor such as a dedicated IC, that is, by hardware. Each of the above units may also be achieved by using a combination of software and hardware. In a case of using a plurality of processors, each of the processors may achieve one of the units or may achieve two or more of the units.

The tentative route calculation module 21A calculates the tentative route <NUM> in the same manner as that of the tentative route calculation module 20A of the first arrangement. However, in the present arrangement, the tentative route calculation module 21A calculates a plurality of tentative routes <NUM> in which at least part of the via routes of the tour points <NUM> is different from each other.

That is, the tentative route calculation module 20A of the first arrangement described above outputs the tentative route <NUM> of the lowest cost. On the contrary, the tentative route calculation module 21A of the present arrangement outputs a plurality of tentative routes <NUM> and the cost of each of the tentative routes <NUM>. The tentative route calculation module 21A may calculate the cost of the tentative routes <NUM> in the same manner as that of the tentative route calculation module 20A of the first arrangement described above.

The route selection module 21D controls the via point addition module 20B to repeat the above route derivation processing to derive the route <NUM> acquired by adding the via points <NUM> to the tentative route <NUM> for each of the tentative routes <NUM> calculated by the tentative route calculation module 21A, in an ascending order from the tentative route <NUM> of the lowest cost.

In detail, the route selection module 21D sorts the tentative routes <NUM> calculated by the tentative route calculation module 21A in an ascending order of the cost, which is the order from the lowest cost. Then, the route selection module 21D reads, in order, the tentative routes <NUM> that have not yet undergone the route derivation processing by the via point addition module 20B and have the lowest cost among the tentative routes <NUM>, and outputs those to the via point addition module 20B.

The via point addition module 20B sequentially receives the tentative routes <NUM> output from the route selection module 21D in an ascending order of the cost, and executes the same route derivation processing as that of the first arrangement every time a single tentative route <NUM> is received.

The cost calculation module 21E calculates the cost of the route <NUM> derived by the via point addition module 20B.

When the route derivation processing by the via point addition module 20B satisfies a termination condition, the route determination module 21F determines the route <NUM> of the lowest cost to be the suboptimal route <NUM>, and outputs it to the output control module 20C.

In detail, the route determination module 21F determines that the termination condition is satisfied, when the number of repetitions of the route derivation processing by the via point addition module 20B becomes equal to or greater than a threshold, and the calculation time of the route derivation processing becomes equal to or longer than a prescribed time or the cost of the route <NUM> derived by the via point addition module 20B is equal to or lower than the cost of another tentative route <NUM> that is the next lowest with respect to the cost of the tentative route <NUM> used to derive the route <NUM>.

Specifically, when the number of repetitions of the route derivation processing by the via point addition module 20B is equal to or greater than the threshold, the route determination module 21F determines the route <NUM> derived immediately before by the via point addition module 20B to be the suboptimal route <NUM> and outputs it to the output control module 20C. This threshold may be defined in advance. Furthermore, the threshold value may also be changeable by an operation instruction or the like of the user via the input unit <NUM>.

Note that when the number of repetitions of the route derivation processing by the via point addition module 20B is equal to or greater than the threshold, the route determination module 21F may determine, among the routes <NUM> derived by the via point addition module 20B, the route <NUM> of the lowest cost to be the suboptimal route <NUM> and output it to the output control module 20C.

Furthermore, when the calculation time of the route derivation processing becomes equal to or longer than the prescribed time, the route determination module 21F determines that the route <NUM> derived immediately before by the via point addition module 20B as the suboptimal route <NUM> and outputs it to the output control module 20C. The calculation time of the route derivation processing is the time elapsed since the route derivation processing is started by the via point addition module 20B. The prescribed time may be defined in advance. The prescribed time may also be changeable by an operation instruction or the like of the user via the input unit <NUM>.

When the calculation time of the route derivation processing by the via point addition module 20B becomes equal to or longer than the prescribed time, the route determination module 21F may determine, among the routes <NUM> derived by the via point addition module 20B, the route <NUM> of the lowest cost to be the suboptimal route <NUM> and output it to the output control module 20C.

Furthermore, when the cost of the route <NUM> derived by the via point addition module 20B is equal to or lower than the cost of another tentative route <NUM> that is the next lowest with respect to the cost of the tentative route <NUM> used to derive the route <NUM>, the route determination module 21F determines the route <NUM> as the suboptimal route <NUM> and outputs it to the output control module 20C.

When determined that the termination condition is not satisfied, the route determination module 21F determines that the route <NUM> derived immediately before by the via point addition module 20B as the tentative route <NUM>. Then, the route determination module 21F adds the tentative route <NUM> to a group of tentative routes <NUM> calculated by the tentative route calculation module 21A and sorts them in an ascending order of the cost, which is the order from the lowest cost. Then, the route selection module 21D may read, in order, the tentative routes <NUM> that have not yet undergone the route derivation processing by the via point addition module 20B and have the lowest cost among the tentative routes <NUM>, and output those to the via point addition module 20B.

Furthermore, the route determination module 21F may output the route <NUM> selected by the user among the routes <NUM> derived by repeating the route derivation processing to the output control module 20C as the suboptimal route <NUM>.

The output control module 20C may output the route <NUM> that is determined by the route determination module 21F to be suboptimal to the display unit <NUM> and the mobile body <NUM>.

As in the first arrangement, the output control module 20C may change the route <NUM>, upon receiving instruction information that includes at least one of an instruction to add an additional via point to the route <NUM> displayed on the display unit <NUM> and an instruction to change the positions of the via points <NUM> included in the route <NUM>.

At this time, the output control module 20C may further display a group of the tentative routes <NUM> on the display unit <NUM>. In this case, the user may select the tentative route <NUM> to be used for deriving the route <NUM> by operating the input unit <NUM> and selecting a desired tentative route <NUM> from the displayed group of the tentative routes <NUM>. Then, the output control module 20C may control the via point addition module 20B to derive the route <NUM> by using the selected tentative route <NUM>.

Next, an example of a flow of information processing executed by the route planning device 10B according to the present arrangement will be described.

<FIG> is a flowchart illustrating an example of the flow of the information processing executed by the route planning device 10B according to the present arrangement.

The tentative route calculation module 21A calculates a plurality of tentative routes <NUM> in which at least part of the via routes of the tour points <NUM> is different from each other and the cost of the tentative routes <NUM> (step S200).

The route selection module 21D sorts the tentative routes <NUM> calculated at step S200 in an ascending order of the cost, which is the order from the lowest cost (step S204).

Then, the route selection module 21D sets "<NUM>" representing the number of repetition time <NUM> to the number of repetitions i of the route derivation processing executed by the via point addition module 20B (step S206).

Then, the first tentative route <NUM> is read in order from the lowest cost, and output to the via point addition module 20B (step S208). The via point addition module 20B uses the first tentative route <NUM> to execute the route derivation processing (step S210). The processing of step S210 is similar to steps S102 to S124 described in the first arrangement (see <FIG>).

Then, the cost calculation module 21E calculates the cost of the route <NUM> that is derived by the via point addition module 20B by performing the route derivation processing of step S210 (step S212).

Thereafter, the route determination module 21F determines whether the route derivation processing of step S210 satisfies the termination condition (step S214). For example, the route determination module 21F determines that the termination condition is satisfied, when the number of repetitions i is equal to or greater than the threshold, and the calculation time of the route derivation processing becomes equal to or longer than the prescribed time or the cost of the route <NUM> calculated at step S212 is equal to or lower than the cost of another tentative route <NUM> that is the next lowest with respect to the cost of the tentative route <NUM> used to derive the route <NUM>.

When determined positive at step S214 (Yes at step S214), the processing proceeds to step S216. At step S216, the route determination module 21F determines that the route <NUM> derived by the route derivation processing of S210 performed right before is the suboptimal route <NUM> and outputs it to the output control module 20C (step S216). As described above, the route determination module 21F may determine the route <NUM> of the lowest cost among the routes <NUM> derived by the route derivation processing of step S210 as the suboptimal route <NUM>, and output it to the output control module 20C.

The output control module 20C outputs the route <NUM> that is determined to be suboptimal at step S216 to the display unit <NUM> and the mobile body <NUM> (step S218). Then, the present routine is terminated.

In the meantime, when the route determination module 21F determines that the termination condition is not satisfied (No at step S214), the processing proceeds to step S220. At step S220, the route selection module 21D adds <NUM> to the number of repetitions i of the route derivation processing (step S220).

Then, the route determination module 21F determines the route <NUM> derived by the route derivation processing of step S210 performed right before as the tentative route <NUM> (step S222). Then, the route determination module 21F adds the tentative route <NUM> to the tentative routes <NUM> calculated at step S200, and sorts them in an ascending order of the cost, which is the order from the lowest cost (step S224). Then, the processing returns to step S208 described above.

As described above, in the route planning device 10B of the present arrangement, for each of the tentative routes <NUM> in which at least part of the via routes of the tour points <NUM> is different from each other, the route selection module 21D controls the via point addition module 20B so as to repeat, in order from the tentative route <NUM> of the lowest cost, the route derivation processing for deriving the route <NUM> acquired by adding the via points <NUM> to the tentative route <NUM>. When the route derivation processing satisfies the termination condition, the route determination module 21F determines the route <NUM> of the lowest cost to be the suboptimal route <NUM>.

Therefore, by repeating the route derivation processing, the route planning device 10B of the present arrangement can derive the suboptimal route <NUM> in addition to achieving the effects of the first arrangement described above.

Note that the scope of application of the route planning device <NUM> and the route planning device 10B according to the arrangements described above is not limited. For example, the mobile body <NUM> that moves along the route <NUM> derived by the route planning device <NUM> and the route planning device 10B is not limited to a drone. As described above, the mobile body <NUM> may also be a flying object other than a drone, a ship, a vehicle, a robot, or the like.

The route planning device <NUM> and the route planning device 10B according to the arrangements are described by referring, as an example, to a mode in which the tentative route <NUM> is a tour route that passes through the tour points <NUM> at least once and the route <NUM> is a tour route that passes through the points including the tour points <NUM> and the via points <NUM> at least once. However, the tentative route <NUM> and the route <NUM> are not limited to such tour routes. That is, derivation of the tentative route <NUM> and the route <NUM> by the route planning device <NUM> and the route planning device 10B according to the arrangements is not limited to traveling problems, but can also be applied to route finding problems.

Next, an example of the hardware configuration of the route planning device <NUM> and the route planning device 10B according to the arrangements will be described.

<FIG> is a hardware configuration diagram illustrating an example of the route planning device <NUM> and the route planning device 10B according to the arrangements.

The route planning device <NUM> and the route planning device 10B according to the arrangements are in a hardware configuration using a typical computer, including a control device such as a central processing unit (CPU) 90D, storage devices such as read only memory (ROM) 90E, a random access memory (RAM) 90F, and a hard disk drive (HDD) <NUM>, an interface for various devices, such as an I/F unit 90B, an output unit 90A that outputs various kinds of information, an input unit 90C that receives operations of the user, and a bus <NUM> that connects each of the units.

In the route planning device <NUM> and the route planning device 10B according to the arrangements, the CPU 90D reads out a computer program from the ROM 90E and executes it on the RAM 90F, thereby achieving each of the units on the computer.

Note that the computer program for executing each of the above described processing performed by the route planning device <NUM> and the route planning device 10B according to the arrangements may be stored in the HDD <NUM>. The computer program for executing each of the above described processing performed by the route planning device <NUM> and the route planning device 10B according to the arrangements may also be provided by being mounted to the ROM 90E in advance.

Claim 1:
A route planning device (<NUM>) comprising:
a tentative route calculation module (20A) configured to calculate a tentative route (<NUM>) passing through a plurality of tour points (<NUM>, 40A, 40B) disposed in a virtual space assumed to include no obstacle (<NUM>) for a space including an obstacle (<NUM>); and
a via point addition module (20B) comprising:
a precision calculation module (20B1) configured to calculate a precision based on at least one selected from a collision severity indicating a severity when a mobile body moving along the route collides with the obstacle and an obstacle avoidance performance of the mobile body, wherein the precision is lower as the collision severity is lower and the precision is lower as the obstacle avoidance performance is higher; and
a via point search module (20B4) configured to search a search space that is the space with a search accuracy corresponding to the precision, and add one or more via points around an interference point at which the obstacle included in the space and the tentative route intersect, wherein the search accuracy is lower as the precision is lower;
wherein the via point addition module (20B) is configured to derive a route (<NUM>) passing through the tour points (<NUM>, 40a, 40B) and the one or more via points (<NUM>, 48A, 48B, 48C).