Rethink workcell task queues for higher efficiency

[luca-della-vedova]

From what I understand, in the the current architecture workcells have a queue of tasks that they need to execute. These tasks can only be performed in the order they are received because of the FIFO structure used.
Furthermore, tasks are enqueued when the work order is created, not when the task actually needs to be executed.
I would argue this is not a great design and is suboptimal in many ways, let's look at two different scenarios:

Long + short work order

Let's say we have, in order of submission:

• A work order with 10 steps, with the last step being performed by workcell_1, submitted first and enqueued in the workcell as a first task.
• A new incoming work order with workcell_1 performing the very first step.

Delayed work order

On the opposite end, let's say we have, in order of submission:

• A two step work order, workcell_0 and workcell_1. Highly delayed because of an issue with workcell_0.
• A work order with 10 steps, with the last performed by workcell_1, that goes smoothly and reaches workcell_1 task while the first work order is still delayed.

With the current architecture, in both scenarios workcell_1 will not be able to perform the task in the second work order until the first one is finished, which is not optimal.

I believe there are two possible ways to change the current architecture that are technically possible but since I didn't design it in the first place I'm not sure they have any tradeoff I'm not aware of:

• Remove the task queueing that is done at the workcell level at work order creation and only queue a task when WorkcellRequest is called. I believe this has a potential drawback that we can't tell, at the workcell_orchestrator level, if the workcell will be used by any existing work orders or not so it's perhaps not the best solution.
• Change the workcell storage to a different data structure. I would propose a priority heap where we order the workcell tasks with a custom function of whether the task is executable, submission time, optionally priority, such as:
  • If an executable task is compared to a non executable task, the executable task will be placed on top of the heap.
  • If two executable tasks are compared, the one with the highest priority will be executed first (future development, we have no concept of priority yet).
  • If two same priority tasks are compared, the one with the earliest submission timestamp will be executed first.

We then just iterate through the heap here, and as soon as a non executable task is found stop iterating.

[aaronchongth]

Thanks for writing this up! I can certainly see some potential ideas here that can help deal with various scenarios, issues or edge cases. Pardon the following basic questions, I'm not very well versed with the expectation of production lines of workcells or industrial systems, so I have a few questions that may help us zero in on decisions,

• in an industrial setting, are there generally expectations that work orders should be completed in the order that they were submitted? For example, submitting in sequence work order A, B, C, should yield the outputs of A, B, C in sequence too, perhaps to ensure QC or subsequent steps is done in the right order too or some industrial standard being fulfilled

• in an industrial setting, where workcells are involved, are workcells generally expected to finish their one-and-only purpose for the work order in relatively quick fashion, and with relatively low cycle-time variance? For example how our demos with 2 workcells, each workcell is generally doing 1 specific thing only, with some minor changes in the form or parameterized jobs, but overall kinda always taking the same amount of time, and never orders-of-magnitudes longer

Depending on these perspectives, it may help shed some light as to whether it is up to nexus to resolve the potential delays mentioned, or if the these potential delays are problems of the individual workcells (and the workcell should be re-designed or debugged, etc)

A two step work order, workcell_0 and workcell_1. Highly delayed because of an issue with workcell_0.
A work order with 10 steps, with the last performed by workcell_1, that goes smoothly and reaches workcell_1 task while the first work order is still delayed.

[Yadunund]

I agree this is an important bottleneck to address among other load balancing tasks.

I would be in favor of removing task queuing at the workcell level and have the orchestrator manage queues and update the positions of workcell tasks in queues based on the evolving states of work orders and workcells.

The advantage of having workcells manage queues is so that the workcells themselves can decide what tasks to process in what in order / parallelism based on the equipment and capabilities of the cell. But with this approach we would need to introduce interfaces between the system & workcell orchestrators to manage the workcell queues (append, delete, update priorities, etc). But the policy to handle different priorities gets offloaded to the workcells. For better determinism at the system level, having the system orchestrator manage these queues is starting to make sense to me.

in an industrial setting, are there generally expectations that work orders should be completed in the order that they were submitted? For example, submitting in sequence work order A, B, C, should yield the outputs of A, B, C in sequence too, perhaps to ensure QC or subsequent steps is done in the right order too or some industrial standard being fulfilled

@aaronchongth not necessarily, usually the objective would be to maximize throughput of the line.

in an industrial setting, where workcells are involved, are workcells generally expected to finish their one-and-only purpose for the work order in relatively quick fashion, and with relatively low cycle-time variance?

Ideally yes but certain operations can have longer cycle times.

[luca-della-vedova]

I see, so instead of introducing a priority heap to let the workcell manage the queue you would prefer to let the system orchestrator do that.

In that case, would it make sense to split the current Context storage into two? From:

std::list<std::shared_ptr<Contexts>> _ctxs;

into

std::unordered_map<std::string, std::shared_ptr<Contexts>> _assigned_ctxs;
std::list<std::shared_ptr<Contexts>> _running_ctxs;

We could store tasks that have been assigned into the hashmap, by their id, when the QueueWorkcellTaskService is called.
After that, when WorkcellRequest is called, we can move them into the _running_ctxs and use a FIFO logic to let the workcell operate on them in parallel, if capable to.
Then the system orchestrator itself can use whatever logic after the tasks are assigned to decide when the workcell should do the specific task.

Does that make sense?

Edit: On second thought this is pretty much what the prority heap would do, split into two data structures.

[Yadunund]

I was thinking more along having priority queues for each workcell stored within and managed by the system orchestrator.

std::unordered_map<std::string, std::priority_queue<Context>> _assigned_ctxs;

The SO would no longer make a QueueWorkcellTaskService call over the network? It would directly append the queue it manages.

[luca-della-vedova]

I was thinking more along having priority queues for each workcell stored within and managed by the system orchestrator.

std::unordered_map<std::string, std::priority_queue<Context>> _assigned_ctxs;

The SO would no longer make a QueueWorkcellTaskService call over the network? It would directly append the queue it manages.

Note that storing Contexts makes sense in the workcell_orchestrator (a context is for a workcell task), but not really at the system orchestrator level (a context is for a work order). I'm not sure how clean this would end up being.
Currently, the system orchestrator has two main "storages":

• The class itself, holds the work orders, some utility structures and the ROS 2 interfaces.
• The Context, which holds all information about a specific work order.

This proposal would require introducing a global storage for "all the tasks that each workcell is doing". This can't be in Context because there is only knowledge about one work order there. It will likely become a class variable of the system orchestrator with the big caveat that we will have to be careful about keeping in sync the internal storage of Jobs (which hold the contexts for each job) with this new aggregated information about which task is being done by which workcell and what their statuses are.
As soon as a workcell task changes its state we will effectively have to update it in two places and make sure they are in sync at all times.

I suspect keeping this in the workcell orchestrator would be the cleanest.