| 摘要 |
A method and apparatus for determining a route for a vehicle (6), the method comprising: measuring a position of the vehicle (6); providing a specification of a region (12) into which the vehicle (6) is to be moved; and, using the measurements and specification, determining the vehicle route. The route determination process comprises constructing a graph (34) within a state space (X) of the vehicle (6), identifying, within the graph (34), a path for the vehicle (6), performing a path shortening algorithm on the identified path, and, using the shortened path, determining the vehicle route. The path shortening algorithm comprises: selecting two vertices along the path that are separated by at least two edges; connecting the two selected vertices with an additional edge; and, depending on certain cost values, removing the edges and vertices by which the selected vertices are connected, and including, in the path, the additional edge. |
| 主权项 |
1. A method of determining a route for a vehicle, the method comprising:
measuring, by measurement apparatus, a position of the vehicle; providing, for use by one or more processors, a specification of a region into which the vehicle is to be moved; and using the measurements and the specification of the region, performing, by the one or more processors, a route determination process to determine the route for the vehicle, wherein the route determination process comprises:
constructing a graph within a state space of the vehicle, the graph comprising a plurality of vertices and one or more edges connecting those vertices;identifying, within the constructed graph, a path from a first vertex of the graph to a second vertex of the graph, the first vertex corresponding to the measured position of the vehicle, and the second vertex corresponding to the vehicle being at least partially located within the region;using the identified path, performing a path shortening algorithm so as to provide a shortened path; anddetermining the vehicle route specified by the shortened path, thereby providing the route for the vehicle; and the path shortening algorithm comprises:
defining the identified path to be the current path; andperforming one or more times steps (i) to (vi), so as to produce the shortened path; whereinstep (i) comprises selecting a vertex along the current path so as to provide a first path vertex;step (ii) comprises selecting a further vertex along the current path so as to provide a second path vertex, the second path vertex being connected to the first path vertex by at least two edges;step (iii) comprises determining a first cost value, the first cost value being indicative of a cost associated with a path within the current path from the first path vertex to the second path vertex;step (iv) comprises providing an additional edge, the additional edge having as its starting vertex the first path vertex and as its ending vertex the second path vertex;step (v) comprises determining a second cost value, the second cost value being indicative of a cost associated with a path from the first path vertex to the second path vertex along the additional edge; andstep (vi) depending on the first and second cost values, either:
disregarding the additional edge and maintaining the current path; ormodifying the current path by removing, from the current path, the edges and vertices in the current path by which the first path vertex and the second path vertex are connected, and including, in the current path, the additional edge. |
