Clarifications regarding the Task Allocation Planner

[jkeshav-bvignesh]

Hi team,
I am trying to understand the Task Allocation Planner in rmf_task and since the official documentation is still in progress, I had a few questions that I require some clarity on.

1. Assuming the default BinaryPriorityCostCalculator is used with the TaskPlanner::complete_solve, Is this flow correct?
   • Every time the make_initial_node function is called in complete_solve, the cost is calculated.
   • The h_value of the cost requires the invariant_duration which is calculated using the corresponding Task::Model.
   • The Model in turn uses the rmf_traffic::agv::Planner to calculate the actual plan.
   • The default agv::planning::interface that is used here is the DifferentialDrivePlanner
   • DifferentialDrivePlanner.plan(state) then calls a_star_search on this state
     Please correct me if I am wrong as this is
2. If the above flow holds, does the a_star_search run on the complete node_graph or a subset of nodes? I am curious about the internal.queue.
3. Does the Task Planner reallocate previously assigned but still pending tasks among the fleet's robots when the new request is estimated? I believe this has got to do something with how the best_candidates are selected for an assignment.
   • I saw that Generalized Task Planning is in the works. Is this a high priority right now?
4. What happens when multiple bid notices arrive at the same time? Since the bid_notice_cb is executed per request, I assume, the TaskPlanner allocates one request at a time.
5. Since the final_assignment can take multiple iterations - there is a while(node) loop in complete_solve that runs with new estimates and every iteration has a new node creation that calls a_star - is there any limitation on the number of robots / requests or node graph size? Or is the bid ignored as the bidding_time_window defaults to 2 seconds?
6. I came across rmf_planner_viz in the old archived repo. I encountered some build errors related to some dependencies, but since the visualizer was not moved here, is this not valid anymore?
7. Will the official documentations for the planners be available soon? Are there any other open design docs for the task and traffic modules to enable new devs to understand the system faster and contribute?

Thanks in advance :)

[mxgrey]

1. Everything you described about the flow of the planner appears accurate.
2. I'm not sure what node_graph you're asking about. Could you clarify that? And which a_star_search? The task planner uses A* search and the path planner also uses A* search, so I'm not sure which you are referring to.
3. Yes, pending tasks that are assigned to a fleet may be reordered within the fleet when new tasks come in. Currently there is no mechanism for moving a task to a different fleet after it has been assigned to a fleet, but that is something we'd like to explore in the future. Expanding on our task planning implementation is currently waiting on a source funding for that work.
4. Correct, the task dispatcher will only hold one task auction at a time. A new task request will not be bid on until all previous requests have been assigned.
5. We currently do not put any explicit limitations on the number of robots or the number of tasks can be requested at once. (Although I can say that task planning seems to be faster with more robots because when there are more candidates we don't have to consider as many permutations of task ordering.) You're right to point out that if there are too many pending task requests then it's possible for the bidder to miss the 2-second window. In the use cases we've been involved with so far we haven't seen that issue, but it's definitely something we want to address in the future. Most likely we'd want the bidders to emit a heartbeat while they work on finding a solution, and the auctioneer would keep waiting until the heartbeats stop appearing.
6. rmf_planner_viz is very difficult to get built and running. We're going to be reworking the whole planner and providing a new easy-to-use visualizer for it. I'll try to remember to post about it here when it's ready for viewing.
7. This will depend largely on resource and time constraints. We're always looking for funding to improve documentation, but most customers are more interested in new/better features. Truthfully the existing task and path planning libraries are likely to end up as informative prototypes that will be deprecated in favor of new, better libraries. Our best chance at having good documentation might be to write it as we develop the successors to these libraries.

[jkeshav-bvignesh]

Thanks for the clarifications @mxgrey! Do you have any specific release timeline in mind for this new planner and visualizer?

Also, I was referring to the A* search in the path planner (rmf_traffic::agv::planning::a_star_search). I believe that the other A* search is the while loop in TaskPlanner::complete_solve. Specifically, I was referring to this line in DifferentialDrivePlanner.cpp:

const auto solution = a_star_search(expander, internal.queue);

This expander utilizes the SuperGraph built from the nav_graph ( agv::Graph) created by the traffic editor, right? The node_graph refers to this graph. Are there any other graphs in the planning & allocation flow?

I was curious about the data in both these parameters when the operation space is very large. Based on some of my experiments since then, I believe the whole graph is always considered even if it consists of disjoint sets. Apart from the hospital scenario, where there any other large scale use-cases considered?

I guess even the candidate maps are created from their initial states using this same graph. I couldn't completely understand how the best candidates for a given task are chosen given that pending tasks could be reordered. Does best_candidates always consist of all the robots?

[jkeshav-bvignesh]

Oh. I had followed this comment:
https://github.com/open-rmf/rmf_ros2/blob/b1676a0cbe7157a616f460c4fb9ed4db5c9bad7e/rmf_task_ros2/include/rmf_task_ros2/Dispatcher.hpp#L123

and this auctioneer creation in Dispatcher.cpp:
https://github.com/open-rmf/rmf_ros2/blob/b1676a0cbe7157a616f460c4fb9ed4db5c9bad7e/rmf_task_ros2/src/rmf_task_ros2/Dispatcher.cpp#L248-L257

So was I wrong in assuming the Dispatcher wants the evaluator to be LeastFleetDiffCostEvaluator?

[Yadunund]

Looks like PR open-rmf/rmf_ros2#168 that followed updated the signature of the Auctioneer::make() function to accept an ConstEvaluatorPtr evaluator and the instantiation in Dispatcher.cpp passes LeastFleetDiffCostEvaluator as you pointed out. We should probably fix that 😄

[jkeshav-bvignesh]

That would be great! Happy to raise a PR, if needed.

[mxgrey]

Thanks so much for bringing this to our attention, @jkeshav-bvignesh ! This was definitely a mistake that slipped in during that huge refactoring.

I've opened a PR to fix this. Please let us know if that helps your use case.

[jkeshav-bvignesh]

Thanks and sure! Will do👍🏾