SURFACE VEHICLE TRAJECTORY PLANNING SYSTEMS, DEVICES, AND METHODS

• US 20160299507A1
• Filed: 04/08/2016
• Published: 10/13/2016
• Est. Priority Date: 04/08/2015
• Status: Active Grant

• Current Assignee: University of Maryland, College Park
• Original Assignee: University of Maryland, College Park
• Inventors: SHAH, Brual C., SVEC, Petr, GUPTA, Satyandra K.
• Granted Patent: US 10,019,006 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: B63B 2035/007 autonomously operating
• CPC Class Codes: B63H 25/00 Steering; Slowing-down otherwise than by use of propulsive elements using movably-installed outboard propulsion units B63H20/00; Dynamic anchoring, i.e. positioning vessels by means of main or auxiliary propulsive elements
• CPC Class Codes: G01C 21/203 Specially adapted for sailing ships
• CPC Class Codes: G05D 1/0206 specially adapted to water vehicles
• CPC Class Codes: G08G 3/02 Anti-collision systems

Abstract

A planning module for a water surface vehicle can determine a vehicle trajectory that avoids one or more moving obstacles, such as civilian marine vessels, by performing a lattice-based heuristic search of a state space for the surface vehicle and selecting control action primitives from a predetermined set of control action primitives based on the search. The planning module can separate a travel space into a plurality of regions and can independently scale the control action primitives in each region based on the moving obstacles therein. The heuristic search includes evaluating a cost function at each state of the state space. The cost function can be based on at least predicted movement of the obstacles responsive to respective maneuvers performed by the surface vehicle at each node of the search.

Claims

1. An operating system comprising:

a planning module configured to determine a trajectory for a surface vehicle that avoids one or more moving obstacles by performing a lattice-based heuristic search of a state space for the surface vehicle and selecting control action primitives from a predetermined set of control action primitives for the surface vehicle based on the search,

wherein the planning module separates a travel space for the surface vehicle into a plurality of regions and independently scales the control action primitives in each region based on the moving obstacles therein,

wherein the heuristic search includes evaluating a cost function at each state of the state space, and

wherein the cost function is based on at least predicted movement of the obstacles responsive to respective maneuvers performed by the surface vehicle at each node of said search.

2. The operating system of claim 1, wherein the planning module is configured to set a multiplier value associated with the control action primitives in a first of the plurality of regions different from a multiplier value associated with the control action primitives in a second of the plurality of regions, the first region having a different level of congestion for the moving obstacles than that of the second region.

3. The operating system of claim 1, wherein the scaling of the control action primitives is such that sampling in regions with higher levels of congestion of the moving obstacles is increased as compared to sampling in regions with lower levels of congestion of the moving obstacles.

4. The operating system of claim 1, further comprising:

a perception module configured to output to the planning module a current state of the surface vehicle and states of the moving obstacles; and

a control module configured to receive the determined trajectory from the planning module and to control the surface vehicle so as to follow the determined trajectory.

5. The operating system of claim 1, wherein each control action primitive comprises at least a pose of the surface vehicle and an arrival time or velocity for the surface vehicle.

6. The operating system of claim 1, wherein the cost function is further based on collision risk of the surface vehicle with the moving obstacles, availability of contingency maneuvers for the surface vehicle to avoid colliding with the moving obstacles, and/or compliance with predetermined navigation rules governing movement of the obstacles and the surface vehicle.

7. The operating system of claim 1, wherein the cost function is given by f(s′

)=g(s′

)+∈

h(s′

), where g(s′

) is cost-to-come, h(s′

) is cost-to-go, and ∈

is a parameter for balancing a computational speed of the search and optimality of the trajectory.

8. The operating system of claim 1, wherein the planning module is configured to repeat the determining as the surface vehicle and the obstacles move.

9. The operating system of claim 1, wherein the state space is a five dimensional state space including time, position, orientation, and surge speed.

10. A non-transitory computer-readable storage medium upon which is embodied a sequence of programmed instructions that cause a computer processing system of a surface vehicle to:

separate a travel space for the surface vehicle into a plurality of regions;

independently scale control action primitives in each of said regions based on moving obstacles therein;

perform a lattice-based heuristic search of a state space for the surface vehicle in each of said regions;

based on the heuristic search, select a particular control action primitive from a predetermined set of control action primitives, and iterate the performing and selecting so as to build a determined trajectory for the surface vehicle by concatenating the selected control action primitives,

wherein the heuristic search includes evaluating a cost function at each state of the state space, and

wherein the cost function is based on at least predicted movement of the obstacles responsive to respective maneuvers performed by the surface vehicle at each iteration of the search.

11. The non-transitory computer-readable storage medium of claim 10, wherein the independently scaling the control action primitives comprises setting a multiplier value associated with the control action primitives in a first of the plurality of regions different from a multiplier value associated with the control action primitives in a second of the plurality of regions, the first region having a different level of congestion for the moving obstacles than that of the second region.

12. The non-transitory computer-readable storage medium of claim 10, wherein the sequence of programmed instructions further cause the computer processing system to control the surface vehicle to follow the determined trajectory.

13. The non-transitory computer-readable storage medium of claim 10, wherein the cost function is further based on collision risk of the surface vehicle with the moving obstacles, availability of contingency maneuvers for the surface vehicle to avoid colliding with the moving obstacles, and/or compliance with predetermined navigation rules governing movement of the obstacles and the surface vehicle.

14. The non-transitory computer-readable storage medium of claim 10, wherein

each control action primitive comprises at least a pose of the surface vehicle and an arrival time or velocity for the surface vehicle, and

the state space is a five dimensional state space including time, position, orientation, and surge speed.

15. The non-transitory computer-readable storage medium of claim 10, wherein the cost function is given by f (s′

)=g(s′

)+∈

h(s′

), where g(s′

) is cost-to-come, h(s′

) is cost-to-go, and ∈

is a parameter for balancing a computational speed of the search and optimality of the trajectory.

16. A surface vehicle comprising:

at least one actuator for propelling or directing the surface vehicle through a travel space; and

a planning module that determines a trajectory for the surface vehicle that avoids one or more moving obstacles in the travel space,

wherein the planning module performs a lattice-based heuristic search of a state space for the surface vehicle and selects control action primitives from a predetermined set of control action primitives based on the search,

wherein the planning module separates the travel space into a plurality of regions and independently scales the control action primitives in each region based on the moving obstacles therein,

wherein the heuristic search includes evaluating a cost function at each state of the state space, and

wherein the cost function is based on at least predicted movement of the obstacles responsive to the selected control action at each node of the search.

17. The surface vehicle of claim 16, wherein the surface vehicle is constructed to operate as an unmanned autonomous vehicle traveling on a water surface.

18. The surface vehicle of claim 16, wherein the scaling of the control action primitives is such that sampling in regions with higher levels of congestion of the moving obstacles is increased as compared to sampling in regions with lower levels of congestion of the moving obstacles.

19. The surface vehicle of claim 16, further comprising:

at least one sensor that monitors the surface vehicle and/or the moving obstacles;

a perception module that outputs to the planning module a current state of the surface vehicle and/or states of the moving obstacles based on outputs from the at least one sensor; and

a control module that receives the determined trajectory from the planning module and controls the at least one actuator such that the surface vehicle follows the determined traj ectory.

20. The surface vehicle of claim 16, wherein the cost function is further based on collision risk of the surface vehicle with the moving obstacles, availability of contingency maneuvers for the surface vehicle to avoid colliding with the moving obstacles, and/or compliance with predetermined navigation rules governing movement of the obstacles and the surface vehicle.