Infinite loop when finding next link in Benenson parking search logic

[ctchervenkov]

CONTEXT The Benenson parking search model, as implemented in the parking search contrib, is divided into 4 stages :

1. DRIVING: driving towards the destination
2. OBSERVING: observation of parking situation while driving towards destination
3. SEARCH_WHILE_APPROACH: estimating the amount of free parking lots on the way to destination and parking before arrival
4. SEARCH_FOR_NEXT: taking the next free parking space if it isn't too far away after having reached the destination

PROBLEM In the SEARCH_WHILE_APPROACH, the routine selects the next link using the following logic:

1. Once the agent arrives at the end node of a link, loop through all the links exiting from that node.
2. For each out link, compute the distance between the out link's end node and the start node of the destination link.
3. The out link for which this distance is minimized is selected as the next link.

This selection algorithm is simple and works very well for grid networks with bidirectional links of similar length. However, let's consider the following example below.

   A
   ||                       F
 1 || 2                    ||
   ||       3              ||
    B = = = = = = C        ||
            4    ||        ||
                 ||        ||
                 ||        ||
                 ||        ||
               5 || 6    7 || 8
                 ||        ||
                 ||        ||
                 ||        ||
                 ||        ||
                 ||        ||
                 ||        ||
                 ||        ||
                  D = = = = E

Imagine a trip with destination at F and for which the SEARCH_WHILE_APPROACH phase is triggered at node B. At node B, there are 2 out link: link 2 from B to A and link 4 from B to C. Node C is closer to node F than node A, so link 4 is chosen. At node C, there are 2 out link: link 5 from C to D and link 3 from C to B. Node B is closer to node F than node D, so link 3 is chosen. We just entered an infinite loop.

SOLUTION The solution would be to consider the shortest path from each possible next link to the destination node:

1. Once the agent arrives at the end node of a link, loop through all the links exiting from that node.
2. For each out link, compute the shortest path between the out link's end node and the start node of the destination link.
3. The out link for which this path is minimized is selected as the next link.

However, this might substantially increase computation time. In addition, the algorithm would differ from the original one proposed by Benenson et al.

[jfbischoff]

That is a nice bug. I don't think adding a shortest path search would make the whole routing that much slower - it is already quite slow, anyway. Perhaps another idea would be to avoid traveling back to nodes already visited. So the algorithm would be altered that (1) the next node is selected which is closest to the destination (2) the next node has not been visited yet (unless all alternative nodes have been visited already, in which case only rule (1) applies).

Maybe @tschlenther has an opinion on the topic?