Real time planning and scheduling for a team of unmanned vehicles

• US 20070233338A1
• Filed: 03/30/2006
• Published: 10/04/2007
• Est. Priority Date: 03/30/2006
• Status: Active Grant

• Current Assignee: Honeywell International Inc.
• Original Assignee: Honeywell International Inc.
• Inventors: Subramanian, Dharmashankar, Johnson, Daniel, Ariyur, Kartik
• Granted Patent: US 7,603,212 B2
• Time in Patent Office: Days
• US Class Current: 701/23
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30
• CPC Class Codes: G05D 1/0289 with means for avoiding collisions between vehicles vehicle fittings for automatically controlling speed including means for detecting potential obstacles B60K31/0008; avoiding obstacles by action on the steering system B62D; radar, sonar, lidar systems designed for anti-collision purposes G01S13/93, G01S15/93, G01S17/93

Abstract

A method of implementing a plurality of unmanned vehicles over an obstacle field. The method includes obtaining a physical map of the obstacle field. Discretizing the physical map into traversable edges that avoid the obstacles, the traversable edges meeting at nodes. Replacing sections of the traversable edges that are beyond the maneuverability of the unmanned vehicles with traversable arcs. Determining traverse time parameters associated with paths through the obstacle fields, each path made up of select traversable edges and select traversable arcs and using the traverse time parameters in planning and scheduling the vehicles.

Claims

1. A method of forming a traversability map, the method comprising:

discretizing a map of an obstacle field to obtain traversable edges that avoid the obstacles, the traversable edges meeting at nodes; and

replacing sections of the traversable edges that are beyond the maneuverability of vehicles with traversable arcs.

2. The method of claim 1, further comprising:

designate traversable paths though the obstacle field using the traversable edges and traversable arcs.

3. The method of claim 2, further comprising:

determining traverse times through the traversable paths.

4. The method of claim 3, wherein determining traverse times through the traversable paths further comprises:

determining for each arc an arc traverse time parameter;

using the arc traverse time to determine the traverse times through the traversable paths.

5. The method of claim 3, wherein determining an arc traverse time parameter further comprises:

determining all non-trivial incoming and outgoing arcs at a node;

determining the maximum acceptable velocity of a vehicle to traverse each arc associated with the node;

using the slowest of the maximum velocities for the arc traverse time parameter.

6. The method of claim 1, wherein discretizing the map of the obstacle field further comprising:

applying computational geometry to the obstacle field.

7. The method of claim 6, wherein the computation geometry includes at least one of Voronoi diagrams and trapezoidal maps.

8. A method of implementing a plurality of unmanned vehicles over an obstacle field, the method comprising:

obtaining a physical map of the obstacle field;

discretizing the physical map into traversable edges that avoid the obstacles, the traversable edges meeting at nodes;

replacing sections of the traversable edges that are beyond the maneuverability of the unmanned vehicles with traversable arcs;

determining traverse time parameters associated with paths through the obstacle fields, each path made up of select traversable edges and select traversable arcs; and

using the traverse time parameters in planning and scheduling the vehicles.

9. The method of claim 8, wherein discretizing the physical map further comprises:

applying computational geometry to the obstacle field.

10. The method of claim 8, wherein determining traverse time parameters associated with traversable paths further comprises:

determining for each arc an arc traverse time parameter.

11. The method of claim 10, wherein determining an arc traverse time parameter further comprises:

determining all non-trivial incoming and outgoing arcs at a node;

determining the maximum acceptable velocity of a vehicle to traverse each arc associated with the node;

using the slowest of the maximum velocities for the arc traverse time parameter.

12. The method of claim 8, further comprising:

using a mixed variable problem that allows for a variable solution according to partial assignments of variables in the planning of the vehicles.

13. A surveillance system, the system comprising:

a plurality of unmanned vehicles; and

a central controller in communication with the plurality of unmanned vehicles, the controller including,

a discretization module including instructions to discretize a physical map of an obstacle field,

a planning and scheduling module including instructions to plan and schedule the plurality of unmanned vehicles, and

a processor adapted to process the instructions from the discretization module and the planning and scheduling module, the processor further adapted to direct the plurality of the unmanned vehicles based at least in part on the instructions from the discretization module and the planning and scheduling module.

14. The system of claim 13, wherein the controller further comprises a transceiver adapted to communicate with each of the unmanned vehicles.

15. The system of claim 13, wherein each unmanned vehicle includes a transceiver adapted to communicate with the central controller.

16. The system of claim 13, wherein the instructions to discretize the physical map in the discretization module includes instructions to generate traversable edges that meet at nodes while avoiding obstacles in the obstacle field and replace sections of the traversable edges that are beyond the maneuverability of unmanned vehicles with traversable arcs.

17. The system of claim 16, wherein the processor is further adapted to determine traverse times of paths made up of the traversable edges and traversable arcs.

18. The system of claim 17, wherein the processor is further adapted to determine the traverse times of the paths and associate the traverse times with the respective paths.

19. The system of claim 18, wherein determining the traverse times of paths made up of the traversable edges and traversable arcs further comprises:

determining the slowest maximum velocity of a vehicle to traverse each traversable arc at a node.

20. The system of claim 18, wherein the planning and scheduling module includes a mixed variable vehicle planning scheme that implements the traverse times.