Feature/valet: Reservation system for RMF

[arjo129]

This is the initial API and code for reserving locations. Eventually this code will be used for reserving resources like chargers and parking slots. The basic api can be found in rmf_traffic/include/reservations/reservation.hpp.

Additionally, for ros2 based systems a node and messages are provided in the rmf_traffic_ros2 package.

The core data structure used is an std::map which is used to sort the reservations by starting time. Upon a reservation being requested, the rmf_traffic::reservations::Implementation::is_free function is used to check if that specific reservation is available.

• For finite length reservations. It performs a simple binary search to see if the starting time and ending time fall within the same time gap. It then checks the previous reservation (if it exists) to see if there is overlap. Since we can assume the previous schedule is consistent, the current schedule should also be consistent. Time complexity for this is O(logn).

• For indefinite reservations we just look at the reservation with the last starting time in the map and compare if its end time is before or equal to the start time of the incoming reservation. Since we can assume the map contains a consistent schedule, therefore the item with the last starting time will also have the last ending time. This provides an O(1) lookup time.

Unit tests for the API are also provided in this PR.

Several follow-up PRs need to be added. The first PR will be related to parking. This PR will involve a small modification to the planner and loop requests so that the planner will allow for a certain waiting time. The second PR will add persistence to the reservation node so that it can be gracefully restarted.

[mxgrey]

I've created a Google Doc with an outline of the kinds of features and behaviors that I think we'll need out of the reservation system. The hope here is to make the reservation system more like the traffic system, where it can automatically adjust to the constantly changing conditions out in the field.

You'll find that the requested features and behaviors are going to add a lot of design and implementation complexity, so it's going to demand quite a bit more work for this PR.

Ultimately I think we'll want to have these following classes, each defined in their own header:

• rmf_traffic::reservations::Viewer: Pure abstract interface that allows reservations to be inspected, but not modified
• rmf_traffic::reservations::Writer: Pure abstract interface that allows reservations to be requested
• rmf_traffic::reservations::Database: Implementation for both Viewer and Writer. This will be the backbone of the reservation node.
• rmf_traffic::reservations::[Reservation|Ticket|Handle|Participant] I'm not exactly sure what to name this one, but it should be the reservation system's equivalent of the traffic schedule's Participant class.
• rmf_traffic::reservations::Snapshot: The reservation system equivalent of the rmf_traffic::schedule::Snapshot class.
• rmf_traffic_ros2::reservations::Node: Acts as the central authority over reservations, similar to rmf_traffic_ros2::schedule::Node and rmf_traffic_ros2::blockade::Node. The topics that this class listens to should be parameterized so that it can be used for multiple different reservation systems.
• rmf_traffic_ros2::reservations::Mirror: The reservation system equivalent of the rmf_traffic_ros2::schedule::Mirror. This allows ROS2 nodes to inspect the current reservations. It provides a snapshot feature so you can get a frozen snapshot of the current state of reservations at any time. The topics that this class listens to should be parameterized so that it can be used for multiple different reservation systems.
• rmf_traffic_ros2::reservations::Writer: The reservation system equivalent of the rmf_traffic_ros2::schedule::Writer. This allows ROS2 nodes to make reservation requests. It returns rmf_traffic::reservations::Reservation objects asynchronously, after receiving a reply from the rmf_traffic::reservations::Node. The topics that this class listens to should be parameterized so that it can be used for multiple different reservation systems.

[arjo129]

Noted. I'll spend the rest of the week and next few weeks reworking some of these features.

On Thu, 25 Feb 2021, 17:54 Grey, notifications@github.com wrote:

I've created a Google Doc https://docs.google.com/document/d/1YQkDUP-kuETGxCeXSpgHqWKEjlt4mHSutN-s9fBCkEc/edit?usp=sharing with an outline of the kinds of features and behaviors that I think we'll need out of the reservation system. The hope here is to make the reservation system more like the traffic system, where it can automatically adjust to the constantly changing conditions out in the field.

You'll find that the requested features and behaviors are going to add a lot of design and implementation complexity, so it's going to demand quite a bit more work for this PR.

Ultimately I think we'll want to have these following classes, each defined in their own header:

• rmf_traffic::reservations::Viewer: Pure abstract interface that allows reservations to be inspected, but not modified
• rmf_traffic::reservations::Writer: Pure abstract interface that allows reservations to be requested
• rmf_traffic::reservations::Database: Implementation for both Viewer and Writer. This will be the backbone of the reservation node.
• rmf_traffic::reservations::[Reservation|Ticket|Handle|Participant] I'm not exactly sure what to name this one, but it should be the reservation system's equivalent of the traffic schedule's Participant class https://github.com/osrf/rmf_core/blob/master/rmf_traffic/include/rmf_traffic/schedule/Participant.hpp .
• rmf_traffic::reservations::Snapshot: The reservation system equivalent of the rmf_traffic::schedule::Snapshot https://github.com/osrf/rmf_core/blob/master/rmf_traffic/include/rmf_traffic/schedule/Snapshot.hpp class.
• rmf_traffic_ros2::reservations::Node: Acts as the central authority over reservations, similar to rmf_traffic_ros2::schedule::Node and rmf_traffic_ros2::blockade::Node. The topics that this class listens to should be parameterized so that it can be used for multiple different reservation systems.
• rmf_traffic_ros2::reservations::Mirror: The reservation system equivalent of the rmf_traffic_ros2::schedule::Mirror. This allows ROS2 nodes to inspect the current reservations. It provides a snapshot feature so you can get a frozen snapshot of the current state of reservations at any time. The topics that this class listens to should be parameterized so that it can be used for multiple different reservation systems.
• rmf_traffic_ros2::reservations::Writer: The reservation system equivalent of the rmf_traffic_ros2::schedule::Writer. This allows ROS2 nodes to make reservation requests. It returns rmf_traffic::reservations::Reservation objects asynchronously, after receiving a reply from the rmf_traffic::reservations::Node. The topics that this class listens to should be parameterized so that it can be used for multiple different reservation systems.

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/osrf/rmf_core/pull/297#issuecomment-785769037, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAEEMQAVIL6VWP7XURTMRI3TAYM6XANCNFSM4XVWB2EA .

[arjo129]

Moving to new repo.