System and method for route planning under multiple constraints
First Claim
1. A route planning method, comprising steps of:
- receiving target information concerning a set of available targets, the target information providing a set of target parameters for each of the available targets;
receiving sets of target thresholds, including a set of one or more threshold values for each of at least a subset of the target parameters;
receiving a set of mission objectives defining a plurality of distinct target parameter priority orderings, each target parameter priority ordering being associated with a respective mission status;
selecting a target sequence by repeatedly selecting a best next target and adding the best next target to a selected target sequence list until a mission completion criteria has been satisfied; and
communicating a route, comprising the target sequence, to a route utilization system;
whereinat a plurality of times while selecting the target sequence, the method includes determining a mission status in accordance with previously selected targets, if any, and determining a target parameter priority ordering in accordance with the determined mission status;
the step of selecting a best next target includes;
for each of at least a first subset of the available targets, mapping a plurality of the target parameters into respective bin values in accordance with respective ones of the sets of target thresholds, and computing a cost function value in accordance with the bin values;
selecting from the first subset of the available targets a second subset having a best cost function value;
if the second subset includes only one target, selecting the one target as the best next target; and
if the second subset includes more than one target, successively narrowing the second subset by removing from the second subset, for successive ones of the target parameters in accordance with the determined target parameter priority ordering, all targets in the second subset except targets having a best bin value for each of the successive target parameters until the second subset contains only one target, and selecting the one target as the best next target.
2 Assignments
0 Petitions
Accused Products
Abstract
A route planning mechanism receives a target set denoting a set of available targets, a set of target parameter thresholds for binning target parameters, a set of mission objectives and a corresponding set of mission thresholds for binning the mission parameters. The route planning mechanism may also receive an avoidance set denoting obstacles to be avoided. The mission objectives define a number of distinct target parameter priority orderings, each associated with a respective mission status. Successive best next targets are selected and added to a selected target sequence list until a mission completion criteria is satisfied. Each best next target is selected by determining a mission status in accordance with the previously selected targets, and a corresponding target parameter priority ordering. The target parameters of each available target are mapped into respective bin values in accordance with their respective target thresholds, and a cost function value is computed for each available target in accordance with the bin values. A subset of the available targets having a best cost function value is selected. That subset is successively narrowed until the subset contains only one target, and then that one target is selected as the best next target. The subset narrowing is performed using the bin values of the target parameters, applied in the target parameter priority ordering that is based on the current mission status. The resulting sequence of selected targets is then passed to a route utilization system, such as a satellite control system.
-
Citations
18 Claims
-
1. A route planning method, comprising steps of:
-
receiving target information concerning a set of available targets, the target information providing a set of target parameters for each of the available targets; receiving sets of target thresholds, including a set of one or more threshold values for each of at least a subset of the target parameters; receiving a set of mission objectives defining a plurality of distinct target parameter priority orderings, each target parameter priority ordering being associated with a respective mission status; selecting a target sequence by repeatedly selecting a best next target and adding the best next target to a selected target sequence list until a mission completion criteria has been satisfied; and communicating a route, comprising the target sequence, to a route utilization system; wherein at a plurality of times while selecting the target sequence, the method includes determining a mission status in accordance with previously selected targets, if any, and determining a target parameter priority ordering in accordance with the determined mission status; the step of selecting a best next target includes; for each of at least a first subset of the available targets, mapping a plurality of the target parameters into respective bin values in accordance with respective ones of the sets of target thresholds, and computing a cost function value in accordance with the bin values; selecting from the first subset of the available targets a second subset having a best cost function value; if the second subset includes only one target, selecting the one target as the best next target; and if the second subset includes more than one target, successively narrowing the second subset by removing from the second subset, for successive ones of the target parameters in accordance with the determined target parameter priority ordering, all targets in the second subset except targets having a best bin value for each of the successive target parameters until the second subset contains only one target, and selecting the one target as the best next target. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
7. A route planning method, comprising steps of:
-
uploading a data set from a control station to a semi-autonomous vehicle, the uploaded data set including; an initial set of target information, the initial set of uploaded target information providing a set of target parameters for each of the available targets; sets of target thresholds, including a set of one or more threshold values for each of at least a subset of the target parameters; a set of mission objectives defining a plurality of distinct target parameter priority orderings, each target parameter priority ordering being associated with a respective mission status; at the semi-autonomous vehicle, determining a target sequence by repeatedly selecting a best next target and adding the best next target to the selected target sequence list until a mission completion criteria has been satisfied; and at the control station, independently determining a second, identical target sequence by repeatedly selecting a best next target and adding the best next target to a second selected target sequence list until the mission completion criteria has been satisfied; uploading updates to the data set from the control station to the semi-autonomous vehicle so as to supplement and/or revise specified portions of the uploaded data set; and after the updates uploading step; at the semi-autonomous vehicle, redetermining the target sequence by repeatedly selecting a best next target and adding the best next target to the selected target sequence list until a mission completion criteria has been satisfied; and at the control station, independently redetermining the second, identical target sequence by repeatedly selecting a best next target and adding the best next target to the second selected target sequence list until the mission completion criteria has been satisfied; whereby identical target sequences are independently determined by the semi-autonomous vehicle and the control station, and the data set uploaded to the semi-autonomous vehicle is revised without re-uploading the entire updated data set from the control station to the semi-autonomous vehicle. - View Dependent Claims (8, 9, 10, 11)
-
-
12. A route planning and utilization system, comprising:
-
memory for storing a data set, including; target information, the target information providing a set of target parameters for a set of available targets; sets of target thresholds, including a set of one or more threshold values for each of at least a subset of the target parameters; and a set of mission objectives defining a plurality of distinct target parameter priority orderings, each target parameter priority ordering being associated with a respective mission status; a route planning engine that repeatedly selects a best next target and adds the best next target to a selected target sequence list until a mission completion criteria has been satisfied; and a route utilization system coupled to the route planning engine, that visits, in order, the targets in the selected target sequence list; the route planning engine including a data processing unit, and instructions to be executed by the data processing unit, including instructions for; determining, at a plurality of times while selecting the targets to be added to the selected target sequence list, a mission status in accordance with previously selected targets, if any, and determining a target parameter priority ordering in accordance with the determined mission status; selecting the best next target by; for each of at least a first subset of the available targets, mapping a plurality of the target parameters into respective bin values in accordance with respective ones of the sets of target thresholds, and computing a cost function value in accordance with the bin values; selecting from the first subset of the available targets a second subset having a best cost function value; if the second subset includes only one target, selecting the one target as the best next target; and if the second subset includes more than one target, successively narrowing the second subset by removing from the second subset, for successive ones of the target parameters in accordance with the determined target parameter priority ordering, all targets in the second subset except targets having a best bin value for each of the successive target parameters until the second subset contains only one target, and selecting the one target as the best next target. - View Dependent Claims (13, 14, 15, 16, 17)
-
-
18. A route planning and utilization system, comprising:
-
a semi-autonomous vehicle, including a first wireless communication mechanism; a control station, including a second wireless communication mechanism that coacts with the first wireless communications mechanism to upload a data set from the control station to the semi-autonomous vehicle, the data set including; target information, the target information providing a set of target parameters for a set of available targets; sets of target thresholds, including a set of one or more threshold values for each of at least a subset of the target parameters; and a set of mission objectives defining a plurality of distinct target parameter priority orderings, each target parameter priority ordering being associated with a respective mission status; the semi-autonomous vehicle including a first route planning engine that determines a target sequence by repeatedly selecting a best next target and adding the best next target to the selected target sequence list until a mission completion criteria has been satisfied; and the control station including a second route planning engine that independently determines a second, identical target sequence by repeatedly selecting a best next target and adding the best next target to the second selected target sequence list until the mission completion criteria has been satisfied; the control station including control mechanisms that, in conjunction with the first and second wireless communication mechanisms, upload updates to the data set from the control station to the semi-autonomous vehicle so as to supplement and/or revise specified portions of the uploaded data set; the second route planning engine including logic for redetermining the target sequence using the updated data set; the first route planning engine including logic for redetermining the target sequence, after the updates to the data set have been uploaded to the semi-autonomous vehicle; whereby identical target sequences are independently determined by the semi-autonomous vehicle and the control station, and the data set uploaded to the semi-autonomous vehicle is revised without re-uploading the entire updated data set from the control station to the semi-autonomous vehicle.
-
Specification