Positioning at least one vehicle in relation to a set of moving targets
A method and system for positioning a vehicle in relation to each moving target of an ordered set of moving targets. Each of the moving targets moves from an initial position at a constant velocity. Embodiments can compute an estimated time for the vehicle to be positioned within a predetermined proximity of one of the moving targets; compute an estimated location of the moving target at the estimated time, based on a current position of the moving target and the constant velocity of the moving target, and compute a required velocity for the vehicle to move from its current position to reach the estimated location by the estimated time. If the required velocity is less than or equal to a maximum velocity of the vehicle, outputting the estimated time and the estimated location for use in positioning the vehicle.
1. A computer-implemented method of positioning a vehicle in relation to each moving target of an ordered set of moving targets, wherein each of the moving targets moves from a respective initial position at a respective constant velocity, the method comprising:
i) computing, by selecting a range-limited random value, an estimated time (t x );
ii) computing, based on a current position of the moving target and the constant velocity of the moving target, an estimated location (r x ) of the moving target at the estimated time (t x );
iii) computing a required velocity for the vehicle to move from its current position to reach a location within a predetermined proximity of the estimated location (r x ) of the moving target by the estimated time (t x );
iv) if the required velocity is less than or equal to a maximum velocity of the vehicle, outputting the estimated time and the estimated location for use in positioning the vehicle; and
if the required velocity is greater than the maximum velocity of the vehicle, increasing the estimated time (t x ), and repeating ii)-iv).
2. The method according to claim 1 , further comprising repeating i)-iv) for each subsequent moving target in the set, wherein the current position of the vehicle is taken to correspond to the estimated location of a previous moving target in the set.
3. The method according to claim 1 , comprising repeating i)-iv) for a plurality of vehicles, where each of the plurality of vehicles is associated with its own ordered set of moving targets.
4. The method according to claim 3 , wherein i)-iii) at least are performed by solving an optimisation problem.
5. The method according to claim 4 , wherein the optimisation problem comprises determining/seeking:
a first time and a first position, and a second time and a second position, which meet the following conditions
the first position is within a predetermined proximity of a location of the first moving target at the first time,
the second position is within the predetermined proximity of a location of a second moving target at the second time, and
a distance between the first position and the second position is no greater than a distance the vehicle can travel at, or below, a maximum velocity of the vehicle for a duration equal to or less than a difference between the second time and the first time, and/or a difference between the second time and the first time is no greater than a time taken for the vehicle to travel from the first position to the second position at, or below, a maximum velocity of the vehicle.
6. The method according to claim 4 , wherein the optimisation problem is represented by an expression
minimise
t
,
p
,
dp
,
dt
,
t
start
,
t
end
f
=
∑
i
=
1
NV
t
end
(
i
)
-
t
start
(
i
)
+
0.001
·
t
(
i
)
wherein:
t represents the estimated time;
p represents a position of a said moving target, where p(i)=[x, y] denotes that the i th moving target is located at position [x, y] at time t 1 =x;
tt end represents task completion time for each of the plurality of vehicles;
t start represents a start time for each of the plurality of vehicles;
Dp represents an inter-task distance matrix, where dp(i,j)=[dx, dy] denotes that a distance vector [dx, dy] between the i th and j th moving targets at their respective execution times; and
Dt represents time difference between interception of the moving targets by a said vehicle, where dt(i, j)=x denotes that the execution times of moving target i and moving target j differ by an amount of x.
7. The method according to claim 6 , wherein a constraint on solutions to the optimisation problem is expressed by
m
∈
[
1
⋯
M
]
,
i
∈
[
1
⋯
n
t
]
,
∀
j
∈
[
1
⋯
n
t
]
,
∀
a
∈
[
1
⋯
n
v
]
,
x
(
a
,
i
,
j
)
=
1
and
i
≠
j
d
p
(
i
,
j
,
1
)
·
sin
(
2
π
m
M
)
+
d
p
(
i
,
j
,
2
)
·
cos
(
2
π
m
M
)
≤
d
t
(
i
,
j
)
·
v
max
wherein:
M represents a number of polygon edges used in a notional circle approximated by polygons, with a vector magnitude limit being implemented by forcing a vector to reside within an area of the notional circle; and V max represents the maximum velocity.
8. The method according to claim 4 , wherein the optimization problem is solved using a processor executing a Linear Programming optimization solver.
9. A system adapted to position a vehicle in relation to a set of moving targets, the system comprising at least one processor configured to:
i) compute, by selecting a range-limited random value, an estimated time (t x );
ii) compute, based on a current position of the moving target and the constant velocity of the moving target, an estimated location (r x ) of the moving target at the estimated time (t x );
iii) compute a required velocity for the vehicle to move from its current position to reach a location within a predetermined proximity of the estimated location (r x ) of the moving target by the estimated time (t x );
iv) if the required velocity is less than or equal to a maximum velocity of the vehicle, output the estimated time and the estimated location for use in positioning the vehicle; and
if the required velocity is greater than the maximum velocity of the vehicle, increase the estimated time (t x ), and repeat ii)-iv).
10. The system according to claim 9 , further including a communications interface configured to transfer signals representing the estimated time and the estimated location to at least one vehicle.
11. A vehicle including the system according to claim 9 .
12. The vehicle according to claim 11 , wherein the vehicle is at least partly autonomous.
13. The vehicle according to claim 11 , wherein the vehicle comprises a water-borne vessel.
14. A computer program product including one or more non-transitory machine-readable mediums encoded with instructions that when executed by one or more processors cause a process to be carried out for positioning a vehicle in relation to each moving target of an ordered set of moving targets, wherein each of the moving targets moves from a respective initial position at a respective constant velocity, the process comprising:
computing, by selecting a range-limited random value, an estimated time (t x );
computing, based on a current position of the moving target and the constant velocity of the moving target, an estimated location (r x ) of the moving target at the estimated time (t x );
computing a required velocity for the vehicle to move from its current position to reach a location within a predetermined proximity of the estimated location (r x ) of the moving target by the estimated time (t x );
in response to the required velocity being less than or equal to a maximum velocity of the vehicle, outputting the estimated time and the estimated location for use in positioning the vehicle.
15. The computer program product of claim 14 , the process further comprising:
in response to the required velocity being greater than the maximum velocity of the vehicle, increasing the estimated time (t x );
computing, based on a current position of the moving target and the constant velocity of the moving target, an estimated location (r x ) of the moving target at the estimated time (t x );
computing a required velocity for the vehicle to move from its current position to reach a location within a predetermined proximity of the estimated location (r x ) of the moving target by the estimated time (t x ); and
in response to the required velocity being less than or equal to a maximum velocity of the vehicle, outputting the estimated time and the estimated location for use in positioning the vehicle.
16. The computer program product of claim 14 , the process further comprising repeating the process for each subsequent moving target in the set, wherein the current position of the vehicle is taken to correspond to the estimated location of a previous moving target in the set.
17. The computer program product of claim 14 , the process comprising repeating the process for a plurality of vehicles, where each of the plurality of vehicles is associated with its own ordered set of moving targets.
18. The computer program product of claim 17 , wherein the computing comprises solving an optimisation problem.
19. The computer program product of claim 18 , wherein the optimisation problem comprises determining:
a first time and a first position, and a second time and a second position, which meet the following conditions
the first position is within a predetermined proximity of a location of the first moving target at the first time,
the second position is within the predetermined proximity of a location of a second moving target at the second time, and
a distance between the first position and the second position is no greater than a distance the vehicle can travel at, or below, a maximum velocity of the vehicle for a duration equal to or less than a difference between the second time and the first time, and/or a difference between the second time and the first time is no greater than a time taken for the vehicle to travel from the first position to the second position at, or below, a maximum velocity of the vehicle.
20. The computer program product of claim 18 , wherein the optimisation problem is represented by an expression
minimise
t
,
p
,
dp
,
dt
,
t
start
,
t
end
f
=
∑
i
=
1
NV
t
end
(
i
)
-
t
start
(
i
)
+
0.001
·
t
(
i
)
wherein:
t represents the estimated time;
p represents a position of a said moving target, where p(i)=[x, y] denotes that the i th moving target is located at position [x, y] at time t i =x;
tt end represents task completion time for each of the plurality of vehicles;
t start represents a start time for each of the plurality of vehicles;
Dp represents an inter-task distance matrix, where dp(i,j)=[dx, dy] denotes that a distance vector [dx, dy] between the i th and j th moving targets at their respective execution times; and
Dt represents time difference between interception of the moving targets by a said vehicle, where dt(i, j)=x denotes that the execution times of moving target i and moving target j differ by an amount of x.