Dynamic Routing

[sync-by-unito[bot]]

Dependencies: https://trello.com/c/TvIBv6JPhttps://trello.com/c/4lJM5O3K

Criterion:

In case the agent cannot continue in its current path, or it wants to take another path, it will need to generate a new path. This can happen under certain conditions, such as the next edge they are due to travel long being heavily congested. A traveller might also take a “wrong“ turn due to human error. In which case the path must be regenerated.

Therefore, the criteria for path regeration can be expressed as:

if (path nextStep is invalid) or (random[0-1] < 0.01 + 0.01*len(next Edge Queue)):

     Regenerate

else:

     Maintain current path

0.01 is some tolerence value that represents the likelyhood of a traveller taking a wrong turn.

Additionally, the second part of the if … or … is arbitrary and will likely need to be reworked, the current placeholder is an example.

‌

Path generation:

We will use A* algorithm to generate the new route. This should have been covered in previous modules but additional resouces will be attached below.

https://www.geeksforgeeks.org/a-search-algorithm/

https://brilliant.org/wiki/a-star-search/

A* uses a heuristic function to prevent searching the entire search space (Omega). In this case our heuristic would be time to target, which is readily accessible in the routing tables of neighbouring nodes. Additional stochasticity can be implemented at a later date, although fine tuning as such would require a operational simulation. We also must omit the blocked edge from our search, to ensure that the previous path is not taken. The junction that the omitted edge leads to must not be omitted, since it may form part of a valid path to the target node.

The algorithm is not guarenteed to find the optimal solution, although that simulates uncertainty from human error, so can be embraced.

Specified by: Zdenek Plesek and Ted Proctor

Implemented by:

Validated by:

┆Issue is synchronized with this Trello card by Unito

[sync-by-unito[bot]]

➤ Zdenek Plesek commented:

Needs specific interfaces described, see comment on Routing tables