Modified 2018-05-27 by Andrea Censi
TODO for Jacopo Tani: math formatting
The following was marked as "todo".
TODO for Jacopo Tani: math formatting
File book/fall2017_projects/21_fleet_planning/20-fleet-planning-intermediate-design-document.md.
File book/fall2017_projects/21_fleet_planning/20-fleet-planning-intermediate-design-document.md
in repo duckietown/docs-fall2017_projects branch master commit f551eedd
last modified by Andrea Censi on 2018-09-02 16:46:23
create_notes_from_elements
in module mcdp_docs.task_markers
.This document describes system that the Fleet-planning team is planning to implement. Part 1 describes the interfaces to other parts of the system. I.e. How it communicates with all of them. In Part 2 a plan for the demo and evaluation is presented. And finally part 3 focuses on data collection, annotation and analysis. As for this project not much annotated data is used, part 3 is rather short.
Modified 2017-12-04 by Sandro Meier
Modified 2017-12-06 by tanij
The fleet planning system shall provide a graphical interface for visualization of n Duckiebots in a Duckietown. Duckiebots shall provide their location regularly to a central “planning node” (not running on a Duckiebot). Furthermore, an interface should exist to generate “taxi” commands (i.e. pickup guest at tile k and bring him to tile m). For such a request the system shall react with a command sent to one of the duckies to pick that customer up and transport him.
See Figure 1 for an overview of the logical structure of the fleet planning system.
In detail the complete process consists of the following steps:
The communication between Duckiebots and the central planning node relies on the communication team of the distributed estimation project. To exchange messages on a fleet level we need this system to work reliably (i.e. no message loss) and with as little latency as possible (i.e. as little delay as possible between sending and receiving a message). We assume that the distributed estimation team can provide such a system within a reasonable timeframe. In part 2 of this document the interface to the communication layer is described. Based on this interface we can mock the communication and work out the fleet level planning part without a already working communication.
We further assume that the system has a map of Duckietown available. This map can be created by hand or with the system implemented by the distributed estimation team.
As described by the preliminary design document, the localization of the Duckiebot within Duckietown is out of scope. We utilize the existing april tag based localization from last years Duckietown course. First experiments are very promising and give good results. So we assume that the Duckiebot is able to localize himself within Duckietown if it is given a map of Duckietown. Furthermore, the localization can be enhanced by using the current speed information from the controllers. With that we can get an estimated position between intersections.
General assumptions that collision avoidance, line detection etc. function flawlessly are also made. Furthermore we ignore parking spots and parked Duckiebots and possible parking actions as they are not represented in our map. Lastly we assume that the clocks of the Duckiebots are reasonably in sync.
Modified 2017-12-04 by Sandro Meier
Fleet planning node [central Laptop]
This node knows the position and status of each Duckiebot in the network. It does the actual planning for the fleet. This consists of matching incoming transportation requests with available Duckiebots in such a way that the overall fleet is used in an optimal way.
Subscribed Topics:
Published Topics:
Visualization Node [central Laptop]
This node is responsible of visualizing n Duckiebots on a map.
Subscribed Topics:
Published Topics:
Taxi command execution node [local]
This node will run on the Duckiebot and listen to commands from the central fleet planning node. Whenever it receives a command it starts the appropriate actions.
A Duckiebot can be in one of three fleet-planning states: - Cruising/Rebalancing - Picking up Customer - Transporting Customer
A Duckiebot receives target locations from the central fleet planning node. It then calculates the shortest route to this location. For this the existing A*-path planning node is used. Given the Duckiebot’s current location and the target location, the path planning node can calculate instructions for how to get there. These instructions are then passed (on a per intersection basis) onto lower level navigation nodes (i.e. handled by navigator team).
Furthermore this node also handles the back right LED which we are allowed to indicate the taxi status of the Duckiebot. Its status is communicated by the central fleet planning node. Additionally, when a customer is picked up a pattern is played on all the LEDs with very low intensity.
Subscribed Topics:
Published Topics:
Localization is based on last year’s “localization” package. For this purpose the map data was updated to match this year’s Duckietown.
The fleet planning package is also based on last year’s “navigation” package. It provides software to handle the path planning and a GUI that allows to select start and target nodes and displays the calculated path for a single Duckiebot. Multiple Duckiebot handling does not exist. The Duckiebot is then made to follow these commands. By now, we were not able to reproduce this feature in a stable manner. Also, in this package no location information is taken into consideration, the path planning and execution is executed in an open-loop manner. This shall be closed loop this year.
Modified 2017-12-04 by Sandro Meier
Modified 2017-12-06 by tanij
The demo from last year consisted of a single Duckiebot. It was possible to click on the node in the graph where the Duckiebot currently is and a target now where the Duckiebot should go. A path planning node then calculated a shortest path to the target location and the Duckiebot drives to that location.
For this years demo we envision a system that builds on top of that. A map is presented to the user that contains the current locations of all Duckiebots. The user can generate a transportation request by using a GUI. The system then assigns one of the Duckiebots to that task. That Duckiebots drives to that location, picks the customer up, drives to the target location and drops the customer again. The pickup and dropoff action are visible in the visualization. Further, the pickup and drop off can be visualized using the LEDs by showing a fancy pattern. There is no physical interaction planed. The system will be able to handle multiple of such requests at the same time. Also, the system shall be robust in the face of dying Duckiebots (may they rest in peace), thus a customer shall be assigned to a new Duckiebot if the original one is lost on it’s way. A Duckiebot counts as out of service if he does not publish a new location within a certain time window. No customers waiting forever. Unfortunately we cannot guarantee safety for a customer that is on a lost duckie-taxi.
Setting up this demo is as quick as starting all Duckiebots with the correct mode of operation and putting them on the map.
Required Hardware
Modified 2017-12-06 by tanij
This project will introduce metrics that will be used to evaluate the performance of the fleet planning, providing a baseline for future groups working on further optimization. The metrics, introduced below, will be applied to a test-setup, which is described in the “proposed performance evaluation” section. The aim of the setup is to test the system’s reliability on the one hand (first scenario) and the capability to handle multiple requests at very high frequency and at the load limit, that is, at full capacity (number of requests at a given time == number of Duckiebots) on the other hand.
Customer requests fulfilled per minute for given number of Duckiebots (ie. throughput). This metric measures how many customer request are handled by the server and fulfilled by all Duckiebots combined. This would allow for the evaluation of different path planning algorithms and testing how well the rebalancing works.
Mean distance of closest Duckiebot to the origin of a request for a set of requests and a given number of Duckiebots. In the optimal case the Duckiebots will be distributed as homogeneously as possible in the Duckietown, minimizing the expected distance to each customer. This metric will enable the evaluation of how well a given implementation does this.
[Stretch goal] Lost customers In certain circumstances Duckiebots will fail (e.g. battery dies, Duckiebots gets stuck, etc.) and if this occurs while a Duckiebot is on the way to pick up a customer the fleet planning system should be able to send another available Duckiebot to fulfill the request instead. For the purpose of evaluation, several Duckiebots can be removed from the Duckietown at random and the system should still be able to fulfill all open requests. (A lost duckiebot can be detected using a timeout on the localization.
In the Duckietown in ML-J44, that is a 5x6 Duckietown, 4 Duckiebots will be placed at the intersections in the following locations:
- (0,3)
- (2,3)
- (4,3)
- (2,5)
See picture below for initial locations.
The Duckiebots should operate at a predefined speed which is consistent across all tests for comparability. There should be two scenarios running 10 minutes each with 10 customer requests per scenario.
Scenario 1: 10 requests evenly spaced out across 10 minutes. Scenario 2: 4 requests within the first minute, then 6 requests at 4,5,6,7,8,9 minutes respectively.
For each scenario, the method is the following:
Modified 2017-12-04 by Sandro Meier
Modified 2017-12-06 by tanij
We need data to do the formal performance evaluation. As the central fleet planning node has all the information about the Duckiebots (i.e. location at every point in time and taxi status) it is enough to log the information flowing through the topics to and from the central fleet planning node.
These logs will be used for the formal performance evaluation as described in Part 2 of this document.
Modified 2017-12-04 by Sandro Meier
None needed.
Modified 2017-12-06 by tanij
Analysis is done by hand on the acquired logs. As a stretch goal, a set of functions is made available that automates the process such that future teams working on improving this system can use the same evaluation strategy.
No questions found. You can ask a question on the website.