Four-dimensional route planner
First Claim
Patent Images
1. A method of determining a route between an origin and a destination comprising:
- beginning at the origin, determining multiple feasible segments from the origin to a node at the end of each feasible segment;
varying altitude as a function of three dimensional representations of hazard areas;
iteratively determining further segments from the nodes to create multiple segment paths between the origin and the destination; and
determining the segment path between the origin and destination having the least cost.
1 Assignment
0 Petitions
Accused Products
Abstract
A route planner uses a recursive algorithm to determine a lateral path, and an adaptive algorithm to determine a vertical path. The vertical path is adjusted based on hazard areas represented by horizontal polygons having top and bottom altitudes. The route planner attempts to find a route which meets a required time of arrival window. A route may be broken into multiple starting and ending points, with desired arrival times specified for each ending point.
87 Citations
26 Claims
-
1. A method of determining a route between an origin and a destination comprising:
-
beginning at the origin, determining multiple feasible segments from the origin to a node at the end of each feasible segment;
varying altitude as a function of three dimensional representations of hazard areas;
iteratively determining further segments from the nodes to create multiple segment paths between the origin and the destination; and
determining the segment path between the origin and destination having the least cost. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
7. A method of determining a route, comprising:
-
receiving an origin node;
receiving a destination node, the destination node located a distance from the origin node;
creating a grid comprising the origin node, the destination node, and a plurality of en route nodes, each node having a plurality of altitudes;
determining the cost to transition to the destination node and each of the plurality of en route nodes;
varying the altitude as a function of three dimensional hazard areas; and
selecting a subset of nodes from the plurality of en route nodes, the subset of nodes having the least total cost to transition from the origin node to the destination node. - View Dependent Claims (8, 9, 10, 11)
-
-
12. A method of selecting a lateral and vertical route, comprising:
-
receiving an origin node;
receiving a destination node, the destination node remote from the origin node;
defining a plurality of paths, each path originating at the origin node and terminating at the destination node and traversing one or more intermediate nodes;
defining more intermediate nodes at varying altitudes in response to hazards which are defined with lateral and vertical dimensions;
defining more paths utilizing the intermediate nodes defined at varying altitudes;
determining the cost associated with traversing each of the plurality of paths; and
selecting the path that satisfies a predetermined cost function. - View Dependent Claims (13, 14, 15, 16)
-
-
17. A method of determining a route between an origin and a destination for a vehicle taking into account variables as it moves along the route, the method comprising:
-
establishing a plurality of nodes in a three dimensional grid encompassing the origin and destination;
beginning at the origin node, determining costs of moving the vehicle to multiple nodes proximate to the origin node;
from each of the multiple nodes, determining transition costs of moving to further multiple nodes as a function of the variables;
varying altitude in response to three dimensional hazard areas; and
repeatedly determining further costs from the nodes to create multiple routes between the origin and the destination. - View Dependent Claims (18, 19)
-
-
20. A system for determining a route between an origin and a destination, the system comprising:
-
means for determining multiple feasible segments beginning from the origin to a node at the end of each feasible segment;
means for varying altitude as a function of three dimensional representations of hazard areas;
means for iteratively determining further segments from the nodes to create multiple segment paths between the origin and the destination; and
means for determining the segment path between the origin and destination having the least cost. - View Dependent Claims (21, 22, 23, 24, 25)
-
-
26. A route planner comprising:
-
a module implementing a recursive algorithm to determine a horizontal path;
a module implementing an adaptive algorithm to determine a vertical path that is adjusted based on hazzard areas represented by horizontal polygons having top and bottom altitudes.
-
Specification