Goto-1: Planning with Dijkstra
Project Resources
- Objective: Having a Duckiebot drive autonomously from a starting position to any compliant ending position in Duckietown., and stopping there.
- Approach: Implementing Dijkstra's algorithm for route planning and achieving global localization leveraging the Duckietown appearance specifications and indefinite navigation framework.
- Authors: Johannes Boghaert
Why planning with Dijkstra?
Planning is one of the three main components, or “blocks”, in a traditional robotics architecture for autonomy: “to see, to plan, to act” (perception, planning, and control).
The function of the planning “block” is to provide the autonomous decision-making part of the robots’ mind, i.e., the controller, with a reference path to follow.
In the context of Duckietown, planning in applied at different hierarchical levels, from lane following to city navigation.
This project aimed to build upon the vision-based lane following pipeline, introducing a deterministic planning algorithm to allow one Duckiebot to go to from any location (or tile) on a compliant Duckietown map to a specific target tile (hence the name: Goto-1).
Dijkstra algorithm is a graph-based methodology to determine, in a computationally efficient manner, the shortest path between two nodes in the graph.
Autonomous Navigation: the challenges
The new planning capailities of Duckiebots enable autonomous navigation building on pre-existing functionalities, such as “lane following”, “intersection detection and identification”, and “intersection navigation” (we are operating in a scenario with only one agent on the map, so coordination and obstacle avoidance are not central to this progect).
Lane following in Duckietown is mainly vision-based, and as such suffers from the typical challenges of vision in robotics: motion blur, occlusions, sensitivity to environmental lighting conditions and “slow” sampling.
Intersection detection in Duckietown relies on the identification of the red lines on the road layer. Identification of the type of intersection, and relative location of the Duckiebot with respect to it, is instead achieved through the detection and interpretation of fiducial markers, appropriately specified and located on the map. In the case of Duckietown, April Tags (ATs) are used. Each AT, in addition to providing the necessary information regarding the type of intersection (3- or 4-way) and the position of the Duckiebot with respect to the intersection, is mapped to a unique ID in the Duckietown traffic sign database.
These traffic signs IDs can be used to unamiguosly define the graph of the city roads. Based on this, and leveraging the lane following pipeline state estimator, it is possible to estimate the location (with tile accuracy) of the Duckiebot with respect to a global map reference frame, hence providing the agent sufficient information to know when to stop.
After stopping at an intersection, detecting and identifying it, Duckiebots are ready to choose which direction to go next. This is where the Dijkstra planning algorithm comes into play. After the planner communicates the desired turn to take, the Duckiebot drives through the intersection, before switchng back to lane following behavior after completing the crossing. In Duckietown, we refer to the combined operation of these states as “indefinite navigation”.
Switching between different “states” of the robot mind (lane following, intersection detection and identification, intersection navigation, and then back to lane following) requires the careful design and implementation of a “finite state machine” which, triggered by specific events, allows for the Duckiebot to transition between these states.
Integrating a new package within the existing indefinite navigation framework can cause inconsistencies and undefined behaviors, including unreliable AT detection, lane following difficulties, and inconsistent intersection navigation.
Performance evaluation of the GOTO-1 project involved testing three implementations with ten trials each, revealing variability in success rates.
Project Highlights
Here is the output of their work. Check out the GitHub repository for more details!
Autonomous Navigation: Results
Autonomous Navigation: Authors
Johannes Boghaert is a former Duckietown student of class Autonomous Mobility on Demand at ETH Zurich, and currently serves as the CEO of Superlab Suisse, Switzerland.
Merlin Hosner is a former Duckietown student and teaching assistant of the Autonomous Mobility on Demand class at ETH Zurich, and currently works as Process Development Engineer at Climeworks, Switzerland. Merlin was a mentor on this project.
Gioele Zardini is a former Duckietown student and teaching assistant of the Autonomous Mobility on Demand class at ETH Zurich, and currently is an Assistant Professor at MIT. Merlin was a mentor on this project.
Learn more
Duckietown is a modular, customizable and state-of-the-art platform for creating and disseminating robotics and AI learning experiences.
It is designed to teach, learn, and do research: from exploring the fundamentals of computer science and automation to pushing the boundaries of knowledge.