Multi-goal TA

[stark710]

Does this support multi-goal task allocation? That is, one robot visiting multiple goal locations?

[whoenig]

Not out of the box.

[stark710]

Okay, any directions on where to look to add code to support this? I am working on a course project for this, Any help is appreciated. Thanks!

[whoenig]

In a TSP fashion, or each robot just having a fixed sequence of goal locations?

[kaushikbalasundar]

Each robot having a fixed sequence of goal locations - so we can call our multi-goal low level planner to execute a sequence of goals.

[whoenig]

If the input is a fixed sequence of goal locations for one robot and the task assignment portion is just to identify which robot should execute which fixed sequence, then you just need to change the state space of the existing A* planner (adding a discrete variable, which tells you which goal state is next).

If the input is a set of goals, which need to be visited at least once, then you need to change the task assignment to solve the TSP problem, in addition to the multi-label A* search mentioned above. How to do that highly depends on your problem size, since TSPs are NP-hard. For very small problems, an enumeration and ordering of the n! permutations might be feasible, while for more realistic settings one might need to rely on a approximate solver. In that case, the main challenge would be to find an incremental solver, which can produce a second-best solution.

[kaushikbalasundar]

Thank you for the advice. This really helps.

As for the first case with fixed goal sequences, can the current code-base support tasks with multiple fixed goals?

[whoenig]

Everything is templated, including tasks. In this case, I believe you can keep the current tasks (to be Locations in the example, https://github.com/whoenig/libMultiRobotPlanning/blob/main/example/cbs_ta.cpp#L506), with the interpretation that the Location is the first goal of your multi-goal sequence. Then, the only required change is to update the Low-Level Search (which is also templated, so you can add an additional discrete state keeping track of the next goal index).