Download Implementing a Time Optimal Task Sequence For Robot

1
3
2
5
9
7
6
10
4
11
8
12
Figure 6: The order in which nodes of the search tree is explored during breadth-first
search.
of the objective function in the COP. For every decision made during the search, the
best value of that branch for f is evaluated. If the new bound is lower than the previous best the branch is further explored. Otherwise the entire subtree under the branch
is pruned from the search space and the solver will continue on the next branch, or
backtrack if no other branch exists.
The function f can be any function that, for the given problem, calculates a good
boundary value. This function could be strictly discrete or it can be a relaxed to a
real-value function. For vehicle routing problems, a good boundary function to use is
a shortest path heuristic function that can compute the best bound for each route in the
VRP.
Restarts During Search Assume that the branching uses randomisation. The cost
of backtracking can be too high and to save time during the search a restart strategy
can be implemented. This restart is set to start the search from the root node once a
criterion has been met. This criterion can be a time limit, no solution found within x
seconds, or a limit on the number of failures.
A restart strategy is a sequence (t1 ,t2 ,t3 , . . . ) where ti is the number of branches and
backtracking steps the randomised search is allowed to perform. After ti steps, the
search is restarted from the root node and is allowed to run for ti+1 steps. The sequence
can either be the number of steps or a sequence of scalars multiplied by a fixed number
of steps.
Restart strategies are commonly used for minimising the cost of randomised search
heuristics. As with all heuristics, the restart strategy selected is based on knowledge of
the problem at hand. In the case of randomised search it is based on the run-time distribution of the specific problem; these strategies are called non-universal. In contrast,
universal strategies are used to work with any problem. The first proposed universal
strategy is the Luby sequence [17] to solve problems with randomised algorithms. The
Luby sequence is given by S = (1, 1, 2, 1, 1, 2, 4, 1, 1, 2, 4, 8, . . . ) where the number of
26