How should the Destination Server support priorities between robots?

[mxgrey]

The most basic implementation of the Destination Server would just assign destinations on a first-come-first-serve basis, which is what the old Open-RMF reservation system currently does. This might not be suitable in cases where some robot tasks are higher priority than others.

An example is if one robot is fetching linens while another robot is fetching medications from the same supply closet. The medications might be higher priority than the linens to the point that fetching the linens should be intentionally delayed in order to ensure the medications are delivered as quickly as possible.

The question is, how should this prioritization be expressed?

Simple integer

A common way to express competing priorities in a distributed system is with an integer priority level. In this case we'll suppose a higher integer value means a higher priority.

Usually in such a priority scheme, higher priority items completely trump lower priority items no matter how large the difference in their priority levels. In the supply closet example, this means fetching the linens could be given a priority level of 1 while fetching medications could be given a priority level of 2, and this would be exactly the same as if linens had a priority of 1 and medications had a priority of 10000.

In this kind of priority scheme, typically anything of a lower priority must completely give way to anything of a higher priority, even if the difference is only 1, and no matter what other circumstances may be ongoing. This means we should expect the robot fetching the linens to always be diverted to give way for the robot fetching medications, even if the linens are just about to be picked up while the robot coming for the medications is still very far away.

While this makes it relatively simple to reason about priority levels and what to expect based on how they're assigned, this easily leads to outcomes that aren't really optimal.

Cost-based Priority

An alternative way to reason about priorities is in terms of makespan cost. We could consider what it would cost the makespan of the overall operation to give priority to a certain task over others, and then the priority level of a task can be based on how much of that added makespan cost we are willing to absorb (ignore) in order for the task to be prioritized.

For example if we measure the makespan cost in seconds, then a prioritization cost of 600.0 would effectively say "It is preferable to delay other tasks by up to 10 minutes in total in order to prioritize this task."

We could also put a lower bound on this such as a prioritization tolerance of 30.0 could mean "I am willing to wait up to 30s to allow other tasks to finish before I take priority from them."

I suspect these cost bounds will be better at reflecting the real intention behind the prioritization than a simple integer representation of priority. We could still consider using integers as a tie breaker in cases where multiple agents simultaneously have elevated priorities.

Where to represent this?

Besides how to represent priorities we should also consider where it should be represented.

One option could be to include it in certain messages such as DestinationGoal.msg. However I can think of two issues with that:

• Are we confident enough that this priority scheme is general enough to always be how deployments will want to represent priority?
• What about other places where prioritization may have an impact, such as traffic planning? Do we then need to weave this priority information through the whole chain of messages?

Instead we could consider having a ~/priority topic per robot and then publishing this priority information there to be consumed by both the Destination Server and the Traffic Planning Server. Whenever a priority update occurs, each of these servers should recalculate their current plans to account for this new prioritization.

If we use this structure, we will probably want the priority message to include a session ID that associates it with the original goal message.

[arjo129]

This is a well-articulated proposal addressing a critical limitation of the current first-come-first-served destination assignment. The need for a more nuanced approach to task prioritization, especially in scenarios involving diverse robot tasks, is clear.

Prioritization Schemes - Embracing Diversity, Time, and Context

While I agree that a simple integer priority scheme, while straightforward, is likely to lead to suboptimal outcomes in many cases, and the cost-based priority approach, framed in terms of makespan cost, appears to be a far more robust and intuitive solution for a significant range of applications. It shifts the focus from an abstract priority level to a tangible impact on the system's efficiency, which is what truly matters, and the inclusion of a "prioritization tolerance" is a valuable addition.

However, I'd like to emphasize a critical consideration: the vast and varied landscape of real-world robot applications suggests that no single "priority scheme" may be universally optimal. Different deployment scenarios will inherently have different objectives, constraints, and definitions of what constitutes "priority."

Furthermore, there are a few additional dimensions to consider:

Hard Time Constraints / Schedule Adherence:

In many industrial or collaborative robot settings, it's not just about minimizing delay or cost, but about meeting specific, well-defined deadlines or rendezvous times. Think of:

• Item Exchange: Two robots needing to be at a specific point at the same time for a handover.

• Resource Sharing: A robot needing to access a shared resource like a lift or a charging station at a scheduled slot.

• Synchronized Processes: In manufacturing, robots may need to arrive at work cells in perfect synchronization with an assembly line.

For these scenarios, a purely cost-based system might not adequately capture the criticality of a missed deadline, which could have cascading failures or safety implications far beyond a simple makespan increase. This points to the need for a deadline-based or schedule-aware prioritization mechanism, where adherence to a specified time is the primary driver, potentially overriding even high-cost deferrals if a deadline is imminent.

Environmental Determinism and its Impact on Scheduling Needs

The degree of external interaction and predictability in a robot's operating environment significantly impacts the very need for and complexity of a dynamic reservation/prioritization system.

• Highly Deterministic Environments (e.g., Controlled Factories): In environments where we can engineer away most non-determinism (e.g., dedicated robot paths, controlled interaction with machinery), the need for a real-time reservation system might be significantly reduced or even eliminated. Pre-computed, rigid schedules and fixed resource allocations could suffice, as robot travel times and task durations are highly predictable. The primary challenge here might shift to initial schedule optimization rather than dynamic re-prioritization.

• Highly Non-Deterministic Environments (e.g., Public Malls, Hospitals with Pedestrians): Conversely, in environments where robot travel times are inherently unknown and variable due to unpredictable external interactions (pedestrians, human-operated equipment, dynamic obstacles), a robust, dynamic reservation and prioritization system becomes absolutely essential. The system must constantly account for unexpected delays, re-route, and re-prioritize to minimize disruptions and meet objectives despite the inherent chaos.

Given this diversity in task types (cost-based, deadline-based) and environmental contexts (deterministic, non-deterministic), focusing exclusively on a single scheme, even one as promising as cost-based prioritization, would inherently limit our system's applicability and effectiveness. We need a framework that can accommodate these varied requirements.

[mxgrey]

@arjo129 I completely agree on all the points you've raised, and thanks for raising them.

We need a framework that can accommodate these varied requirements.

One thing that I neglected to make clear in the original problem statement is that I'm looking to define what kind of prioritization scheme we should support for the out-of-the-box open source implementations that we provide for the Destination Server and the Traffic Planning Server.

Ultimately both the Destination Server and the Traffic Planning Server should be swappable with custom implementations made by system integrators or perhaps vendors of facility management software. One of the goals for the interface design process is to categorize the interface definitions according to features / capabilities / product fit, so vendors can declare which categories of interfaces are needed to run their platforms, and system integrators can declare which categories of interfaces are compatible with the overall system-of-systems.

Here are my goals for this issue ticket, in order of highest priority to lowest:

1. Identify what kind of prioritization scheme(s) we should offer an out-of-the-box implementation of.
2. Learn about use cases that are not covered by the proposal for the out-of-the-box scheme(s) and clearly disclose those use cases as being out-of-scope for the out-of-the-box implementation.
3. Maybe try to put together guidance / recommendations for how to configure systems that need custom prioritization, but do not define a standard for them unless we are willing/able to put together a reference implementation for that standard.

In my mind the highly non-deterministic environments are the ones that make the most sense for us to target our out-of-the-box efforts on, because those use cases allow the greatest flexibility of outcomes and the least rigid requirements, making it feasible for us to implement something that cover a broad category of use cases without too much ad hoc configuring.

On the other hand, my expectation for highly deterministic use cases is that they probably won't use the Destination Server at all. I think it's more likely that their Task Management Server would publish directly to the ~/destination topic, or perhaps their VDA5050-style Master Control will publish directly to ~/plan and ~/plan/release, which would potentially skip all the places that we'd be using this prioritization scheme.

That being said, in case we do define more priority schemes in the future, we should probably use more specific topic names to disambiguate them. For example the scheme that I proposed above could potentially be called something like ~/prioritization/makespan to distinguish it from a different scheme that could be named something like ~/prioritization/deadline.

[arjo129]

It might be worth pointing out that the prototype rmf_reservation handles costs and deadlines differently. A reservation request looks something like (this is based on discussion of this several years ago):

let reservation_request = vec![
    ReservationRequestAlternative {
        parameters: ReservationParameters {
            resource_name: chargers[0].clone(),
            duration: Some(Duration::minutes(120)),
            start_time: StartTimeRange {
                earliest_start: Some(start_time),
                latest_start: Some(latest_start_time),
            },
        },
        cost_function: Arc::new(StaticCost::new(1.0)),
    },
    ReservationRequestAlternative {
        parameters: ReservationParameters {
            resource_name: chargers[1].clone(),
            duration: Some(Duration::minutes(120)),
            start_time: StartTimeRange {
                earliest_start: Some(start_time),
                latest_start: Some(latest_start_time),
            },
        },
        cost_function: Arc::new(StaticCost::new(1.0)),
    }];

Obviously this is a bit hacky. It is possible to describe transition costs for resources the reservation system as well. This could potentially be translated. Alternatively based on a user choice you could totally ignore the cost function and just use the total makespan as a cost function.