Scheduling

[rhaschke]

This ZenHub epic is used to collect ideas and (later) concrete TODOs for a rework of scheduling. The current "round-robin" scheduling, requires hierarchically calling canCompute() and compute() and the whole pipeline.

Main goals

• Task maintains a job queue of computable (leaf) stages.
• Allow parallel processing of computable stages.
  • Requires thread-safe access to (cost-ordered) interface queues. Note: cost updates are propagated through the entire solution branch, i.e. might entail significant locking effort.
• Offer various schedulers operating on the job queue, which will differently prioritize jobs

Proposal

• This list could be filled by a call to canCompute(). To this end, it's API would be augmented by a reference to the job queue.
• For more flexibility (and safety), I suggest using boost::signals2 instead, which will be set up once during init(), setting up all signal-slot connections.
  • A stage would provide one signal: canCompute(bool).
  • Generators will activate themselves during initialization.
  • MonitoringGenerators will activate if they received a solution.
  • Propagators when they receive new states in their input interfaces.
  • Connectors if they have compatible pairs.
  • Containers are not usually scheduled. Exceptions are some wrappers, e.g. ComputeIK.
  • If a stage runs out of options, it will deactivate itself via canCompute(false).
  • This approach will render the existing canCompute and onNewFailure methods superfluous. As outlined in https://github.com/ros-planning/moveit_task_constructor/issues/314, these methods are still needed to judge - by the container - whether a child should become inactive or not: We need to distinguish between temporarily inactive (i.e. child cannot compute) and exhausted (cannot compute + feeding stages are exhausted too.
  • Optionally, we might have a 2nd signal: priorityUpdated(Priority) to allow ordering of queued jobs by (state) priority.

Prioritization / Scheduler variants

• stage priority based on its lowest input state prio(s)
• average computation time per run: faster jobs should run more often to get a quick estimate of the cost distribution
• cost entropy: ratio of low-cost vs. high-cost/failure solutions: If we have lots of equally good solutions (e.g. from generators), focus more on the remaining pipeline, to increase the "depth" of solutions.

[DaniGarciaLopez]

Any updates on this feature? As I understand, this would greatly reduce the planning time as it allows parallel planning in different threads, right?

We are very interested in this feature as our planning time is already too long for our application. The main solution we have found is to precompute the task offline, as mentioned here, but sometimes it is necessary to do it in real time.

Are there any plans to implement it in the near future?

[rhaschke]

Unfortunately, we didn't have time to start working on this and I don't foresee any change of that situation. However, you are highly welcome to contribute to the project.