Route planning

Patent metadata

Field	Value
Publication number	US-9733090-B2
Application number	US-201414905204-A
Country	US
Kind code	B2
Filing date	Jul 7, 2014
Priority date	Jul 15, 2013
Publication date	Aug 15, 2017
Grant date	Aug 15, 2017

Abstract

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.

First claim

The invention claimed is:

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; and
determining 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; and
performing one or more times steps (i) to (vi), so as to produce the shortened path; wherein
step (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; and
step (vi) depending on the first and second cost values, either:
disregarding the additional edge and maintaining the current path; or
modifying 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.

2. A method according to claim 1 , wherein the method further comprises controlling, by a vehicle controller operatively coupled to the one or more processors, the vehicle so that the vehicle follows the route, thereby moving the vehicle to be at least partially located within the region.

3. A method according to claim 1 , wherein, were the vehicle to follow the vehicle route defined by the additional edge, if the vehicle would collide with another entity, at step (vi), the current path is not modified and the additional edge is disregarded.

4. A method according to claim 1 , wherein the graph is a rapidly-exploring random belief tree.

5. A method according to claim 1 , wherein constructing the graph comprises:
initialising the graph by determining, using the measured position of the vehicle, the first vertex of the graph; and one or more times performing steps (vii) to (ix), thereby providing the graph; wherein
step (vii) comprises sampling the state space of the vehicle to provide a further vertex;
step (viii) comprises providing an edge connecting the further vertex to a different vertex of the graph; and
step (ix) comprises including the further vertex and the edges in the graph.

6. A method according to claim 5 , wherein, for each performance of steps (vii) to (ix), an edge is only included in the graph, were the vehicle to follow the vehicle route defined by that edge, if the vehicle would not collide with another entity.

7. A method according to claim 1 , wherein identifying the path from the first vertex to the second vertex comprises:
assigning, to one or more vertices within the graph, one or more belief values;
propagating, along each path in the graph, the belief values so as assign to each vertex in the graph one or more belief values, each belief value associated to a vertex in the graph corresponding to a unique path in the graph that passes through that vertex; and

selecting, based upon one or more of the belief values, a path from the first vertex to the second vertex.

8. A method according to claim 7 , wherein:
a belief value assigned to the first vertex is indicative of an uncertainty associated with the measurement of the position of the vehicle; and
for a each vertex in the graph other than the first vertex, a belief value assigned to that vertex is indicative of a positional uncertainty of the vehicle if the vehicle were to follow a route specified by a path in the graph from the first vertex to that vertex; and
propagating the belief values comprises adjusting one or more of the belief values to account for further measurements of a position of the vehicle taken by the measurement apparatus.

9. A method according to claim 7 , wherein:
for a each vertex in the graph other than the first vertex, a belief value assigned to that vertex is indicative of a cost value associated with the vehicle following a route specified by a path in the graph from the first vertex to that vertex; and
identifying the path from the first vertex to the second vertex comprises:
identifying, from a set of belief values assigned to the second vertex, the belief value corresponding to the lowest cost value; and
identifying the path from the first vertex to the second vertex corresponding to the identified belief value.

10. A method according to claim 1 , further comprising:
measuring, by the measurement apparatus, a position of a further vehicle;
wherein:
the region has a fixed position in relation to the further vehicle;
the route determination process is performed to further determine a further route for the further vehicle;
the graph is constructed within a joint state space of the vehicle and the further vehicle; and
the first vertex of the graph corresponding to the measured positions of the vehicle and the further vehicle.

11. A method according to claim 1 , wherein the vehicle is an unmanned vehicle.

12. A method according to claim 1 , wherein the measurement apparatus comprises one or more measurement systems selected from the group: a radar system, and a global positioning system.

13. Apparatus for determining a route for a vehicle, the apparatus comprising:
measurement apparatus configured to measure a position of the vehicle; and
one or more processors coupled to the measurement apparatus and configured, using the measurements and a specification of a region into which the vehicle is to be moved, to perform 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 provi

Assignees

• Bae Systems Plc

Inventors

• Simpson Richard Edward

Classifications

• G01C21/20 Primary

  Instruments for performing navigational calculations (G01C21/24, G01C21/26 take precedence) · CPC title

• G05D1/0291

  Fleet control (monitoring fleets in traffic control systems for road vehicles G08G1/127, G08G1/127) · CPC title

• G01C21/3438

  Rendezvous; Ride sharing · CPC title

• G05D1/0206

  specially adapted to water vehicles · CPC title

• G01C21/203 Primary

  specially adapted for water-borne vessels · CPC title