build details

Show: section status errors & todos local changes recent changes last change in-page changes feedback controls

Explicit coordination: final report

Modified 2018-05-06 by Andrea Censi

The final result

Modified 2018-06-25 by Andrea Censi

Video of the final result:

The video is at https://vimeo.com/257762830.

Explicit coordination's video

To reproduce the results please see the operation manual .

Mission and Scope

Modified 2018-02-21 by ValentinaCavinato

Our mission is to coordinate the intersection navigation safely and cleverly through explicit communication.

Motivation

Modified 2018-02-23 by ValentinaCavinato

Duckietowns are complex systems where the traffic situations of a real city should be emulated. These towns contain three- and four-way intersections: the Duckiebots should be able to navigate them without crashing into each other and this requires a clever coordination scheme. Intersections represent a key element of a smooth city navigation.

There are two ways of coordinating Duckiebots: - Using a traffic light, - Using a communication protocol between the vehicles.

Hence, we aim to have both a centralised and a decentralised solution as well as an integration of the two. While the centralised solution boils down to understand the signal emitted by a referee (i.e., a traffic light), the decentralised coordination scheme should allow the Duckiebots to operate on their own, i.e., to communicate between each other and to take decisions without any external help.

Existing solution

Modified 2018-02-23 by Nicolas Lanzetti

A prior implementation for intersection coordination was already available from the 2016’s MIT class. The principle was simple: When a Duckiebot comes at an intersection and stops at the red line. Then, In the case with a traffic light, the Duckiebot detects the frequency at which the traffic light is blinking and acts based on the road rules. In the case without traffic light, the Duckiebot detects the frequency at which the other bots are blinking and adjusts its emitted frequency depending on its state. From an implementation perspective, the distinction was made a priori, i.e., the Duckiebots were not making use of the information coming from the Apriltags detection and therefore not were able to navigate systems with both types of intersection.

From the description above, we can distinguish two modules:

  • LED emission and detection,
  • Coordination based on the detected signals.

For the emission, three signals can be produced: each signal is encoded with a specific color and frequency. While Duckiebots are designed to recognise only frequencies, color are used to allow humans to easily understand the signals emitted by the Duckiebots. The signals represent the states: negotiation (and in which phase of the negotiation it is) or navigation of the intersection.

For the detection, the position and frequency of blinking LEDs are registered.

For the coordination, with the assumption that each vehicle can only see other vehicles on its right but not on its left, the Duckiebot yields its position if the only visible car is on the right, otherwise the Duckiebot waits (light green or red) or crosses (yellow light).

Opportunity

Modified 2018-02-23 by Nicolas Lanzetti

The existing solution had essentially two drawbacks:

  • The overall success rate was about 50%: The algorithm for LED-detection, and/or coordination failed, leading to a potential crash of the Duckiebots.
  • In case of success, the LED-detection and/or coordination algorithms required an average of four minutes to clear an intersection with four Duckiebots. This results in an extremely slow process, which would block a city with dozens of Duckiebots.

Although the solution was problematic, it still gave us some important intuitions on how to solve the problem.

First of all, using a LED-communication protocol is a brilliant idea to let the Duckiebots communicate with each other. Since the previous communication algorithm had the only disadvantage of being slow (also because of several bugs), we started by re-thinking the coordination algorithm. The existing implementation for the coordination was rather complex and articulated, resulting in confused strategies which led to the failure rate of 50%. In order to develop a simpler and lighter algorithm we took inspiration from an existing media access control protocol (MAC): the so called Carrier Sense Multiple Access (CSMA, https://en.wikipedia.org/wiki/Carrier-sense_multiple_access). This algorithm gave us the basic idea behind our strategy and allowed us to have a lighter protocol.

In the second place, we re-designed the LED-detection/-interpreter to be more efficient and robust based on the detection of blobs and not only on the detection of frequencies.

Lastly, we wanted to have a demo that could deal with both intersections, i.e. with and without a traffic light, as opposed to the two available demos from MIT 2016’s class.

Definition of the problem

Modified 2018-02-21 by ValentinaCavinato

Contribution / Added functionality

Modified 2018-02-22 by ValentinaCavinato

Formal performance evaluation / Results

Modified 2018-02-23 by Nicolas Lanzetti

Performance Evaluation
Situation Performance measure Required Obtained
One Duckiebot at the intersection Clearing time 60s 12s
One Duckiebot at the intersection Success rate 90% 98%
Two Duckiebots at the intersection Clearing time 60s 25s
Two Duckiebots at the intersection Success rate 80% 89%
Three Duckiebots at the intersection Clearing time 60s 50s
Three Duckiebot at the intersection Success rate 70% 89%
One Duckiebot at a traffic light type intersection Clearing time 60s 25s
One Duckiebot at a traffic light type intersection Success rate 90% 92%

Failures were mainly caused by the following reasons: - Duckiebots detecting the wrong sign (i.e., expecting a traffic light instead of a normal intersection). - Blobs not properly detected. This is mainly due of failures in the parameters and in the camera calibration. - Duckiebots crashing because of poor intersection navigation.

Future avenues of development

Modified 2018-02-21 by ValentinaCavinato

There is room for improvement for the coordination part of this project. Our approach, in the case of an intersection without traffic light, prioritises robustness rather than efficiency (in some cases all the Duckiebots at an intersection could turn off and restart the whole protocol again) and it is easy to imagine a scenario with an improved efficiency (tradeoff with complexity).

An idea would be to encode in the signal also the intentions of the Duckiebot and, by doing so, allow multiple Duckiebots to navigate the intersection at the same time if their directions are compatible. In fact, if two Duckiebots wanted to go straight they could move at the same time. The clearing time could also be reduced in the case of an intersection with traffic light if the latter was able to see where the vehicles are (prevent the light to turn green in a direction where no vehicle is waiting to cross).

Because of mathjax bug

No questions found. You can ask a question on the website.