Patent Description:
Conventionally, methods of searching for a route using, for example, map data are known. <CIT> discloses this kind of route finding method.

<CIT> discloses a method of searching for the travelable route by expressing environment by a quadtree structure in which the environment is subdivided into four rectangular areas. If an obstacle exists in the subdivided rectangular area, the area is recursively subdivided into four rectangular areas.

However, the configuration of <CIT> cannot search for a route passing through a narrow space, such as between obstacles, when the processing which recursively subdivides into four rectangular areas is performed few times. On the other hand, if the number of times of subdividing into four rectangular areas is increased in order to search for such a narrow route, since the amount of data of the quadtree structure increases explosively, the calculation load increases. Therefore, the configuration of <CIT> has room for an improvement because a suitable route is unable to be searched for with light calculation load.

"<NPL>) discloses a path finding algorithm that uses a quad-tree decomposition and an establishment of a Voronoi-diagram.

The purpose of the present disclosure is to appropriately generate a graph for route finding. This is achieved by the claimed subject-matter. References to embodiments and aspects which do not fall under the scope of the claims are to be understood as examples useful for understanding the invention.

According to a first aspect of the present disclosure, a graph generating device according to claim <NUM> is provided.

Thus, the graph for route finding can be generated, which takes both the advantage of the quadtree dividing method, and the advantage of another method.

The first graph generating module may terminate the subdivision once performed a given upper limit number of times.

Thus, the number of subdividing a space performed by the quadtree dividing method is limited below a given number of times, resulting in achieving the reduction of a calculation load of the route calculation.

The second graph generating module may determine, in the area, which a surrounding area that is an area surrounding the obstacle an arbitrary point not included in the obstacle belongs by a Voronoi dividing method, sets a plurality of second vertexes along a boundary of the determined surrounding area, and generate the second graph by connecting the second vertexes with the second side.

Thus, the graph can be generated, which takes both the advantage of the quadtree dividing method by which a graph of a detour or longer route is not easily generated, and the advantage of the Voronoi dividing method by which the graph can be generated with a light load processing even in a location where the space between the obstacles is narrow.

The graph generating device may further include a second graph adjusting module configured to adjust the second graph generated by the second graph generating module, before being synthesized with the first graph by the graph synthesizing module.

Thus, the synthesized graph in which two graphs are naturally connected without giving a user uncomfortableness, can be generated.

According to the invention, the second graph adjusting module deletes the second side only passing through one or more of the exclusive cells.

Thus, for a part where the first graph and the second graph substantially overlap with each other, the two graphs can be synthesized by giving priority to the first graph generated by the quadtree dividing method.

When the cell partially including the obstacle is referred to as a partially inclusive cell, the second graph adjusting module may exclude the second side only passing through one or more of the partially inclusive cells from a deleting target.

Thus, the synthesized graph can be generated by using the second side passing the partially inclusive cell where the first side cannot be arranged in the first graph.

When a target second vertex that is one of two vertexes connected by the second side in the second graph is located in a partially inclusive cell and the second side passes through the exclusive cell as well as the partially inclusive cell, the graph synthesizing module may reconnect the second side to the target second vertex, and to the first vertex of the exclusive cell through which the second side first passes, when the second side originates from the target second vertex, the partially inclusive cell partially including the obstacle.

Thus, the second graph and the first graph can naturally be connected and synthesized.

According to a second aspect of the present disclosure, a method of generating a graph according to claim <NUM> is provided.

Thus, the route graph can be generated, which takes both the advantage of the quadtree dividing method, and the advantage of another method.

The present disclosure is illustrated by way of example and not by way of limitation in the figures of the accompanying drawings, in which like reference numerals indicate like elements and in which:.

Next, one embodiment of the present disclosure is described with reference to the accompanying drawings. <FIG> is a block graph illustrating an electric configuration of a graph generating device <NUM> according to one embodiment of the present disclosure.

The graph generating device <NUM> illustrated in <FIG> is capable of generating a graph which expresses one or more route to avoid an obstacle. The term "graph" as used herein may refer to a combination of a set of vertexes and a set of sides each of which connects two vertexes.

The graph generating device <NUM> may include a map data acquiring module <NUM> (obstacle data acquiring module), a quadtree graph generating module <NUM> (first graph generating module), a Voronoi graph generating module <NUM> (second graph generating module), a Voronoi graph adjusting module <NUM> (second graph adjusting module), a graph synthesizing module <NUM>, and a route finding module <NUM>.

Specifically, the graph generating device <NUM> may be comprised of a known computer, and include a CPU, a ROM, a RAM, and a HDD. A program for implementing a method of generating the graph of the present disclosure may be stored in the HDD. By collaboration of the hardware and the software described above, the graph generating device <NUM> may operate as the map data acquiring module <NUM>, the quadtree graph generating module <NUM>, the Voronoi graph generating module <NUM>, the Voronoi graph adjusting module <NUM>, the graph synthesizing module <NUM>, and the route finding module <NUM>.

The map data acquiring module <NUM> may acquire map data (obstacle data) used for the generation of the graph. The map data acquiring module <NUM> can acquire the map data, for example, from an external storage device (for example, a map database server) by communication.

The map data may include information on the position and the shape of the obstacle. As illustrated in <FIG>, for example, when obstacles <NUM> and <NUM> through which a movable body cannot pass exist in an area <NUM>, the map data may be comprised of vector data which describes the position of each vertex of polygonal lines expressing the contours of the obstacles <NUM> and <NUM>. The map data acquiring module <NUM> of <FIG> may output the acquired map data to the quadtree graph generating module <NUM> and the Voronoi graph generating module <NUM>.

The quadtree graph generating module <NUM> may generate the graph based on the map data, while using a known quadtree dividing method (hierarchical approximate cell dividing method).

In detail, the quadtree graph generating module <NUM> may vertically and laterally subdivide the area <NUM> where a user wants to generate a route in the map data to generate four cells having equal size. If the obstacles <NUM> and <NUM> are included only in some of the generated cells, the quadtree graph generating module <NUM> may again subdivide the area of the cell vertically and horizontally to again generate four cells having equal size. The quadtree graph generating module <NUM> may recursively perform the subdividing processing until the number of subdivision reaches a given value (subdividing depth). As a result, as illustrated by chain lines in <FIG>, the area <NUM> may be subdivided vertically and horizontally into a plurality of rectangular cells. There may be (first) cells filled up with the obstacle <NUM> or <NUM>, (second) cells partially including the obstacle <NUM> or <NUM>, and (third) cells not including the obstacle <NUM> or <NUM> at all. In the following description, the second cell may be referred to as a "partially inclusive cell," and the third cell may be referred to as an "exclusive cell.

When the subdivision of the cells is finished, the quadtree graph generating module <NUM> may set a vertex (first vertex) at each center of the exclusive cells, and connect the vertexes of the adjacent exclusive cells by a straight-line side (first side). Thus, the quadtree graph generating module <NUM> may generate the graph which can be used for a route calculation. Below, the graph according to the quadtree dividing method may simply be referred to as the "quadtree graph. " The quadtree graph may correspond to the first graph. <FIG> illustrates one example of the quadtree graph. This graph may be comprised of the first vertexes and the first sides. In <FIG>, the first vertex is indicated by a thick-line circle, and the first side is indicated by a thick line.

The number of subdivision (a depth of subdivision) performed by the quadtree graph generating module <NUM> may be limited below a given number (upper limit). Therefore, if the distance between the obstacle <NUM> and the obstacle <NUM> is small (i.e., narrow), in a part between the obstacles, the subdivision may be terminated before being performed finely enough and generating an exclusive cell. As a result, the first side may not be generated.

In <FIG>, a case where the maximum number (upper limit) of subdivisions is <NUM> is illustrated. In <FIG>, since there is no exclusive cell between the obstacle <NUM> and the obstacle <NUM>, no first side which connects the upper and lower graphs may exist at the center of the entire area <NUM>. Therefore, the entire graph may be split vertically.

Although the subdivision is terminated in the state of <FIG>, if the cells are further subdivided, the exclusive cells may be generated so as to be lined up and connect the upper and lower graphs. Therefore, the first sides can be generated in the narrow space between the obstacle <NUM> and the obstacle <NUM>. However, in this case, the number of vertexes of the graph will increase tremendously.

The quadtree graph generating module <NUM> of <FIG> may output the generated graphs to the Voronoi graph adjusting module <NUM> and the graph synthesizing module <NUM>.

The Voronoi graph generating module <NUM> may generate a graph based on the map data by using a known Voronoi dividing method.

In detail, in the general Voronoi dividing method, a plurality of points (seeds) may be given in a certain area, and when an arbitrary point in the area belongs to the nearest seed, a plane may be divided at a boundary between the point and the seed to which the point belongs. In this embodiment, the obstacles <NUM> and <NUM> may be not points but spread areas. Therefore, the Voronoi graph generating module <NUM> may express the contours of the obstacles <NUM> and <NUM> as polygons, determine, in the area <NUM>, which area (surrounding area) surrounding each of the obstacles <NUM> and <NUM> an arbitrary point not included in the obstacles <NUM> and <NUM> belongs, and determine boundaries of the obtained surrounding areas.

This boundary can be acquired in the form of a polygonal line, as illustrated in <FIG>, for example, by obtaining straight lines which bisect an area between the polygonal line of one obstacle <NUM> and the polygonal line corresponding to the other obstacle <NUM>.

The Voronoi graph generating module <NUM> may arrange a second vertex at the same position as each vertex of the bordering polygonal lines, and connect by second sides the second vertexes which are in relation of being connected by the polygonal lines (boundary). Thus, the Voronoi graph generating module <NUM> may generate the graph (second graph) which can be used for the route calculation. Below, the graph generated by the Voronoi dividing method may simply be referred to as a "Voronoi graph. " The Voronoi graph may correspond to the second graph. The example of the Voronoi graph is illustrated in <FIG>. This graph may be comprised of the second vertexes and the second sides. In <FIG>, the second vertex is illustrated by a double circle and the second side is illustrated by a double line.

Since the Voronoi graph generating module <NUM> uses the Voronoi dividing method, it can easily generate the graph in the narrow place. In the example of the Voronoi graph of <FIG>, it can be seen that the graph passing through between the obstacles <NUM> and <NUM> is generated also in the narrow part between the obstacles <NUM> and <NUM> where the graphs are disconnected in the quadtree graph of <FIG> due to the termination of the division.

Note that, according to the Voronoi dividing method, the second vertexes and the second sides can be arranged so that the space between the obstacles is equally divided or bisected even when the obstacles are widely separated from each other. Therefore, for example, as illustrated by broken lines in <FIG>, since a distance between the second vertex or the second side and the obstacles <NUM> or <NUM> becomes unnecessarily large, the route may become a detour or longer.

The Voronoi graph generating module <NUM> of <FIG> may output the generated graph to the Voronoi graph adjusting module <NUM>.

The Voronoi graph adjusting module <NUM> may adjust the Voronoi graph generated by the Voronoi graph generating module <NUM> using the graph generated by the quadtree graph generating module <NUM>.

The processing performed by the Voronoi graph adjusting module <NUM> may include deletion of the second side of the Voronoi graph. This side deletion processing may be to delete the second side if this second side passes only through one or more of the exclusive cell. Note that, as described above, the exclusive cell may be a cell which does not include any obstacles, where the thick-line circle (the first vertex of the quadtree graph) is disposed in <FIG>. This processing may be performed for each of the second sides which constitute the Voronoi graph.

For example, in <FIG>, although the second side illustrated by a reference character S2A passes through two cells, since the two cells are both exclusive cells, this second side S2A may be subject to the deletion. In <FIG>, an X-mark is indicated on the second side to be deleted by this processing. The Voronoi graph adjusting module <NUM> may also delete the second vertex which is disconnected from other second vertexes by deleting the second side. In <FIG>, an X-mark is also indicated on the second vertex to be deleted.

As a result, for the part where the quadtree graph and the Voronoi graph substantially overlap with each other, the quadtree graph will appear in a synthesized graph which will be described below. Thus, by giving priority to the quadtree graph, the disadvantage of the Voronoi graph which tends to be a longer route can be avoided.

For example, as illustrated by a reference character S2B in <FIG>, the second side may pass only through one or more partially inclusive cells. Since this second side S2B does not satisfy the condition described above, it may not be deleted by the Voronoi graph adjusting module <NUM>. The second side S2B may remain still in the graph outputted from the Voronoi graph adjusting module <NUM>. Therefore, the advantage of the Voronoi dividing method which can generate the graph in the narrow space between the obstacles <NUM> and <NUM> can favorably be utilized.

Therefore, the Voronoi graph adjusting module <NUM> of <FIG> can generate the Voronoi graph from which the second sides and the second vertexes are deleted so that the graph does not substantially overlap with the quadtree graph generated by the quadtree graph generating module <NUM>. The Voronoi graph adjusting module <NUM> may output the Voronoi graph after the above adjustment to the graph synthesizing module <NUM>.

The graph synthesizing module <NUM> may generate a sole synthesized graph by combining the quadtree graph outputted from the quadtree graph generating module <NUM>, and the Voronoi graph outputted from the Voronoi graph adjusting module <NUM>.

Specifically, the graph synthesizing module <NUM> may reconnect the second side of the Voronoi graph. This reconnection processing may be to reconnect the second side to the first vertex of the exclusive cell and to the second vertex, when this second vertex in question (target second vertex) is located in the partially inclusive cell and the second side passes not only through the partially inclusive cell but also through the exclusive cell. This processing may be performed for all the second side illustrated in <FIG>.

For example, the second side indicated by a reference character S2C in <FIG> is considered. If the upper second vertex of the two second vertexes connected with each other through the second side S2C is assumed to be the target second vertex, this target second vertex may be located in the partially inclusive cell. Moreover, this second side S2C may pass not only through the partially inclusive cell but also through the exclusive cell below the partially inclusive cell. Therefore, the graph synthesizing module <NUM> may reconnect the second side S2C to the upper target second vertex, and to the first vertex of the exclusive cell (in detail, the exclusive cell through which the second side S2C first passes, when the second side S2C originates from the target second vertex). In <FIG>, the reconnection of the second side is indicated by a black arrow. The graph synthesizing module <NUM> may delete the second vertex which is connected with no vertex. In <FIG>, an X-mark is indicated on the second vertex to be deleted.

As described using <FIG>, the Voronoi graph generated by the Voronoi graph generating module <NUM> may be adjusted beforehand by the Voronoi graph adjusting module <NUM>. By this pre-adjustment processing and the reconnection processing described using <FIG>, the graph synthesizing module <NUM> can generate the graph, as illustrated in <FIG>, in which the quadtree graph and the Voronoi graph are naturally connected without giving the user uncomfortableness.

Each first side which constitutes the quadtree graph, and each second side which constitutes the Voronoi graph may include information related to weights (weighted graph). As one example of the weight includes, but not limited to, a value related to a traveling distance between the vertexes, a time required for the travel. In such a case, the graph as the result of connecting the quadtree graph and the Voronoi graph by the graph synthesizing module <NUM> may also become the weighted graph. The graph synthesizing module <NUM> may output the generated graph to the route finding module <NUM>.

The route finding module <NUM> may search the route for the graph generated by the graph synthesizing module <NUM> based on a known graph search algorithm. By, for example, giving a departing location and a destination location to the obtained graph, the route finding module <NUM> can acquire the shortest route from the departing location to the destination location by using the shortest route problem algorithm for the weighted graph. The acquired route can be displayed, for example, on a display unit provided to the graph generating device <NUM>, or an external display unit electrically connected to the graph generating device <NUM>.

As described above, the graph generating device <NUM> of this embodiment may include the map data acquiring module <NUM>, the quadtree graph generating module <NUM>, the Voronoi graph generating module <NUM>, and the graph synthesizing module <NUM>. The map data acquiring module <NUM> may acquire the obstacle data including the information on the obstacles <NUM> and <NUM>. The quadtree graph generating module <NUM> may recursively subdivide the area <NUM> including the obstacles <NUM> and <NUM> into the cells by the quadtree dividing method, set the first vertex in the exclusive cells, and connect the first vertexes of the adjacent exclusive cells by the first side, to generate the quadtree graph. Meanwhile, the Voronoi graph generating module <NUM> may set the second vertex by a different method (Voronoi dividing method) from the quadtree dividing method, and connect the second vertexes by the second side, to generate the Voronoi graph. The graph synthesizing module <NUM> may synthesize the quadtree graph and the Voronoi graph, to generate the synthesized graph.

Therefore, the route graph can be generated, which takes both the advantage of the quadtree dividing method, and the advantage of another method.

Although the suitable embodiment of the present disclosure is described above, the above configuration may be changed as follows.

The graph generating device <NUM> may be provided with a potential graph generating module which generates the graph by using the concept of a known potential approach, instead of the Voronoi graph generating module <NUM>. For example, the potential graph generating module (second graph generating module) may generate a potential field of which the potential becomes higher as it is closer to the obstacle <NUM> or <NUM>, sets a point where the potential becomes a local minimum, as the second vertex, and suitably connects the second vertexes by the second side, to generate the graph.

The maximum number of subdivisions in the quadtree dividing method may be suitably set, for example, in consideration of the arrangement of the obstacles <NUM> and <NUM> in the map data, the physical size of the movable body, etc..

The Voronoi dividing method may also be configured to divide, not at the boundary where the space between the obstacles <NUM> and <NUM> is equally divided but also at a boundary where the space is divided at an eccentric dividing ratio of <NUM>:<NUM>. Such a boundary can be obtained by a calculation accompanied by a known weighted processing.

The boundary acquired by the Voronoi dividing method may not be limited to the polygonal line but may be, for example, a smooth curve. In this case, the Voronoi graph generating module <NUM> may set a plurality of second vertexes along the curve, and connect the second vertexes by the second sides to generate the Voronoi graph.

The route finding module <NUM> may be provided to a computer (route finding computer) different from the graph generating device <NUM>. In this case, the graph generating device <NUM> may store the graph generated in the graph synthesizing module <NUM> in a suitable storage device (for example, a database server or a removable memory). The route finding computer may acquire the graph from the storage device and perform the route finding.

Claim 1:
A graph generating device (<NUM>), comprising:
an obstacle data acquiring module (<NUM>) configured to acquire obstacle data including information on an obstacle (<NUM>, <NUM>);
a first graph generating module (<NUM>) configured to recursively subdivide an area (<NUM>) including the obstacle (<NUM>, <NUM>) into cells by a quadtree dividing method, set a first vertex in the center of each exclusive cell, wherein an exclusive cell is a cell without the obstacle (<NUM>, <NUM>), and connect the first vertexes of the adjacent exclusive cells by a first side, to generate a first graph;
a second graph generating module (<NUM>) configured to set second vertexes by a different method from the quadtree dividing method and connect the second vertexes by a second side, to generate a second graph;
a second graph adjusting module (<NUM>) configured to adjust the second graph generated by the second graph generating module (<NUM>) by deleting the second side only passing through one or more of the exclusive cells, and
a graph synthesizing module (<NUM>) configured to generate a synthesized graph by combining the first graph with the adjusted second graph.