摘要 |
A method and apparatus for determining a route for a vehicle 6, the method comprising: measuring a position of the vehicle; providing a specification of a region 12 into which the vehicle is to be moved; and, using the measurements and specification, determining the vehicle route. The route determination process comprises constructing a graph, such as a tree (34, Fig 8) within a state space of the vehicle, identifying, within the graph, a path for the vehicle, 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. |