Clarifications regarding the Task Allocation Planner (#147)

Open-RMF Open-RMF General
1

Posted by @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.
  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 :slight_smile:

Chosen answer

Answer chosen by @jkeshav-bvignesh at 2022-05-17T12:01:39Z.
Answered by @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.
2

Posted by @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.

This is the chosen answer.

3

Posted by @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?

4

Posted by @mxgrey:

Thanks for clarifying. I’ll go back to this question:

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.

The A* search is free to explore the entire navigation graph, but since the search uses a heuristic, it will typically only expand a relatively small subset of the graph vertices while still producing an optimal solution. The heuristic it uses is what I call the “minimal travel heuristic” which calculated by a bidirectional Dijkstra search over the navigation graph. The minimal travel heuristic gives the shortest amount of time that the robot could spend traveling from a vertex to its goal, taking into account acceleration/deceleration, turning, waiting for doors to open and close, traveling in lifts, and any other consistently predictable events that are known to happen along the path.

The Dijkstra search trees that calculate these heuristics, and the final results of the heuristic calculations are all aggressively cached in hashmaps so that we never suffer from any redundant search effort. After that, the higher level A* search will generate motion plans that allow the robots to navigate around moving obstacles. We then use that to generate multi-robot motion plans by having the planner take turns treating different robots as moving obstacles, similar to conflict-based search.

I believe the whole graph is always considered even if it consists of disjoint sets

If there are completely disjoint vertices, then the Dijkstra search will not be able to expand into the disjoint part of the set. When that happens, the planner will detect that it is impossible to find a plan and report that fact. If the fleet adapter receives a task request that would require an impossible motion plan, then the fleet adapter is programmed to reject the request. If a request becomes impossible after it was already accepted (e.g. a necessary lane has been closed) then the fleet adapter will report that fact as an error for human operators to take note of, and it will periodically retry the search until a path is found or until the task request is canceled.

I was curious about the data in both these parameters when the operation space is very large.

The largest navigation graph that we’ve used the planner on so far has ~7000 vertices spread over an area covering several square-kilometers. Without any obstacles to avoid, the planner finishes in milliseconds. We haven’t tested the performance with obstacle avoidance turned on because that hasn’t been necessary for that specific application, but in theory the runtime should scale based on the quantity and difficulty of the obstacles rather than based on the size of the graph because the heuristic has perfect knowledge of the graph topology. By the time obstacles are introduced, there isn’t any search effort wasted on exploring the shape or size of the graph.

Does best_candidates always consist of all the robots?

best_candidates is a method in the candidates field of PendingTask. It typically provides the one robot that can finish the pending task at the “lowest cost” (usually that means it will get the task done soonest) taking into account all other tasks that have already been assigned to all the robots. However, it’s possible that two or more robots could “tie” and all be able to finish the task in the same amount of time, so we allow best_candidates to provide multiple robots instead of only one. But when multiple robots are provided, they are all equally “best”.

I couldn’t completely understand how the best candidates for a given task are chosen given that pending tasks could be reordered.

When the task allocation planner generates a new node, it locks in a decision about which task will be performed next by which robot for that node. The first set of nodes generated will each have one task decided and that one task will be assigned to one robot. Each first generation node is making a decision for a different task, so if there are N tasks then there will be N nodes in the first generation. When those first-generation nodes are expanded, the planner will generate a new generation of nodes which each lock in a second task. The best candidate chosen for performing the second task will take into account the decision that was made by the parent node about which robot will perform the first task.

Each new generation of nodes account for all the decisions made by their ancestor nodes, and there are many different lineages of nodes being expanded where the different lineages made different decisions early on about which task is being assigned first, second, third, and so on. In this way, the planner will explore many (but typically not all) combinations of how the tasks could be ordered and distributed across the robots.

5

Posted by @jkeshav-bvignesh:

Thank you for the detailed clarifications Grey! It definitely clears up many of my doubts.

We have also been experimenting with larger simulations to observe the task and traffic planners’ behaviours (thanks to the recent ApiRequest update with robot_task_request and dispatch_task_request). I will probably come back in a while to discuss my observations as well.

But many of the observed behaviours seem to be directly related to the Evaluator function in use. Is there a reason why LeastFleetDiffCostEvaluator is set as the default instead of QuickestFinishEvaluator? I ask this because, intuitively, it feels like the latter would lead to faster task completions.

6

Posted by @Yadunund:

As of this PR Set default evaluator to QuickestFinishEvaluator by Yadunund · Pull Request #134 · open-rmf/rmf_ros2 · GitHub, the default evaluator is QuickestFinishEvaluator

7

Posted by @jkeshav-bvignesh:

Oh. I had followed this comment:

and this auctioneer creation in Dispatcher.cpp:

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

8

Posted by @Yadunund:

Looks like PR Support Flexible Task Definitions by Yadunund · Pull Request #168 · open-rmf/rmf_ros2 · GitHub 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 :grinning_face_with_smiling_eyes:

Edited by @Yadunund at 2022-05-19T12:45:53Z

9

Posted by @jkeshav-bvignesh:

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

10

Posted by @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.

11

Posted by @jkeshav-bvignesh:

Thanks and sure! Will do👍🏾