Question about adapting PIBT for variable travel times between nodes

[weifuchow]

Hello @J-morag

I'd like to ask a question about improving the PIBT algorithm. I'm considering adapting my approach based on PIBT, but I've encountered a challenge when it comes to real-world scenarios.

In the original implementation of PIBT, the solvePIBT function assumes that moving from one node to an adjacent node always takes 1 time unit. However, in real-world situations, travel times between different nodes can vary significantly.

My question is: How can we modify the PIBT algorithm, especially the solvePIBT function, to accommodate variable travel times between nodes? How can we handle this more complex time model while maintaining PIBT's core advantages (such as dynamic priority adjustment and conflict resolution)?

Some initial thoughts:

1. Changing the environment model to a weighted graph, where edge weights represent travel times.
2. Implementing some form of event-driven or asynchronous update mechanism.
3. Modifying the time-stepping logic to use variable time steps.

What are your thoughts or suggestions on this issue? I greatly appreciate your time and expert opinion.

Thank you!

[J-morag]

Hello @weifuchow

First, you should form a concrete model of what travel times mean.

• Are travel times per edge known in advance? Are they stochastic? If so, do you learn the expected travel time as an agent starts moving, or only when it finishes? Is there some range or probability distribution, or is anything possible? etc.

The answers to these questions will dictate the most appropriate implementation (for example one of the ones you suggested)

There may be other important considerations, for example:

• When traversing an edge, do agents occupy both vertices until the move is finished?
• Can an agent stop moving in the middle of traversing an edge? If it does stop, how long does it take it to return to it's original vertex.