There may be infinite loop if there is no way from start point to goal point

[TachikakaMin]

libMultiRobotPlanning/include/libMultiRobotPlanning/a_star.hpp

Line 85 in b01a527

while (!openSet.empty()) {

I think it could have infinite loop if no way from start point to goal point since there is an additional parameter(time) in State. And when you add a State to the set and queue, timestep may be different for same (x,y) so the set won't have any effort.

Correct me if I'm wrong.

[whoenig]

For A*, the algorithm is correct. For CBS (and related variants), you are correct that they do not terminate if no solution exist. This is also the case in the original papers. Termination can be achieved by using CBS+SIPP at the low-level, or by first checking if a solution exists using suboptimal solvers (not implemented here).

[yfb10]

For A*, the algorithm is correct. For CBS (and related variants), you are correct that they do not terminate if no solution exist. This is also the case in the original papers. Termination can be achieved by using CBS+SIPP at the low-level, or by first checking if a solution exists using suboptimal solvers (not implemented here).

Hi,
Thanks for your information. Could you provide an example code for CBS+SIPP at the low level. And how do you expect the performance of SIPP as the low level search compared to A* in CBS?

[whoenig]

I don't have example code ready, but you essentially just replace the low-level planner template from Astar to SIPP. When I tried it a few years back, it was slightly slower than regular CBS.
However, other authors have reported advantages, see https://github.com/PathPlanning/Continuous-CBS/tree/master for link to papers and an alternative implementation.

[yfb10]

I don't have example code ready, but you essentially just replace the low-level planner template from Astar to SIPP. When I tried it a few years back, it was slightly slower than regular CBS. However, other authors have reported advantages, see https://github.com/PathPlanning/Continuous-CBS/tree/master for link to papers and an alternative implementation.

I assume aside from replacing the low-level search to Sipp, converting constraints of high level to safe interval of the cell is also needed, right?
Another confusion comes from the "wait" actions from Sipp and CBS. The CBS_a* takes an extra wait action in get_neighbors while a* explores the map, and SIPP adds a "wait" time. From what I'm understanding, it will be repeated if I directly merge CBS with SIPP. I should abandon the wait in get_neighbors and use the wait time in SIPP, right?

[whoenig]

Correct (to both questions). If you get it working it would be nice if you share it. I remember having implemented it before with this library, but it doesn't seem to be in any of the branches.

[yfb10]

Correct (to both questions). If you get it working it would be nice if you share it. I remember having implemented it before with this library, but it doesn't seem to be in any of the branches.

Thanks. Will pull the request once I make it works.

One more question comes with setting the safe intervals from constraints for an agent.
It's quite straightforward to set safe intervals from vertex constraints. But how should we deal with the edge constraints?
Following the convention in sipp.hpp, I should iterate over all constraints and use "setCollisionIntervals" to save all safe intervals in m_safeIntervals. And m_safeIntervals is iterated and checked when exploring neighbors. Another method I came up with is to iterate over the constraints and build corresponding safe intervals directly in the process of getting neighbors. That is to build SI based on whether constraints are found upon the next location and time of the "neighbors". This method will be theoretically a bit faster than the previous one as it gets rid of m_safeinterval, right?

[yifan96]

For A*, the algorithm is correct. For CBS (and related variants), you are correct that they do not terminate if no solution exist. This is also the case in the original papers. Termination can be achieved by using CBS+SIPP at the low-level, or by first checking if a solution exists using suboptimal solvers (not implemented here).

I don't think having SIPP at the low level can terminate the CBS for unsolvable instances. Can you elaborate more on it?

[yucswx]

您好！       您发送的邮件已收到。谢谢。 祝您生活愉快！

[whoenig]

The issue with regular CBS is that it searches in space-time and has no reason to terminate as it can always add additional wait actions to try another solution. An upper bound on time fixes this. SIPP also explicitly contains an upper-bound, as you now plan over space and time intervals (rather than space-time).

[yifan96]

The issue with regular CBS is that it searches in space-time and has no reason to terminate as it can always add additional wait actions to try another solution. An upper bound on time fixes this. SIPP also explicitly contains an upper-bound, as you now plan over space and time intervals (rather than space-time).

But as far as I understand, converting the regular CBS vertex/edge constraints to a time interval makes no difference, as SIPP will still add wait actions and find the same solution as A*. I have tried https://github.com/Jiaoyang-Li/CBSH2-RTC which supports CBS-SIPP, but it does not terminate for unsolvable instances.