The movie illustrates the branch-and-bound search process, finding the shortest route from the start (left) to the goal (green star, right) avoiding the obstacles (red circles). The vehicle has speed and turn rate limits. The result is globally optimal, but it is not necessary to search all combinations of "left and right".
Thursday, 13 September 2007
The movie demonstrates the difference between ordinary "greedy" DMPC and cooperative DMPC. Two vehicles must pass to reach their targets (circles) but the passage is too narrow. Beginning with greedy DMPC, the two vehicles reach a deadlock, but when they switch to cooperative DMPC, the deadlock is broken and both reach their targets.