SEARCH
A-star search, like Dijkstra's shortest path algorithm,
solves the problem of finding an optimal path in a weighted directed
graph from a given start node to a given goal node.
The problem to be solved is defined by the weighted directed
graph, the start node, and the goal node.
A-star, like Dijkstra's algorithm, is a best-first search.
Unlike Dijkstra's algorithm, A-star search includes
an optimistic estimate of how much it would
cost to continue to the goal.
Though A-star based, the path planner's search algorithm differs in
several respects:
-
The path planner maximizes.
-
The path planner tests for a goal before adding to the active set.
Obtaining intermediate solutions
can reduce the consequences of early termination due to a time limit.
-
There are multiple goal nodes, all corresponding to the same
fat node and set of geographical locations. They can differ
in their detection probabilities and other attributes.
-
The cost of reaching a node is implicit in the node itself.
-
The estimated additional cost of proceeding to a goal cannot
be included with a simple addition or multiplication.
We use a slightly modified Dijkstra's algorithm
for a single source (our goal) and multiple destinations to
get optimistic estimates of the hazards awaiting
a UAV on its way from any fat node to a goal node.
We make this work by
- Ignoring the fuel capacity
- Ignoring the time limit
- For undetected UAVs, ignoring the possibility
that it would be detected by anything
that wouldn't destroy it
- Maximizing
- Replacing addition with multiplication
In the following algorithm, the search network is defined by the function
Forward(node).
The arc tail-->head
is in the network iff tail in domain(Forward) and head in Forward(tail).
The function IsGoal(node) just checks to see whether node corresponds
to the goal fat node.
LaunchNode is the starting node.
So far the UAV has not used any time or fuel and
it has survived undetected.
Score(node) is optimistic, but at most the probability of being able
to reach node.
Search(Forward, LaunchNode, IsGoal, Score)
{
// nothing has happened yet
// we start from the launch point
// there is no incumbent
history := empty
active := {(LaunchNode, Score(LaunchNode))}
scoreIncumbent := -1
while(active not empty) {
// pop a best node
from active, remove a (current, scoreCurrent) pair
with the largest scoreCurrent
if(scoreCurrent <= scoreIncumbent) {
terminate while loop
}
add current to history
for each next in Forward(current) {
if(Score(next) > scoreIncumbent &
next not dominated
by any node in history &
next not dominated
by any node in active ) {
from history and from active,
remove all nodes dominated by next
if(IsGoal(next)) {
scoreIncumbent := Score(next)
incumbent := path from
LaunchNode to next
} else {
add (next, Score(next)) to active
}
}
}
}
if(scoreIncumbent >= 0) return incumbent
else return infeasible