This project focuses on designing algorithms and controls to enable the Jetbot to autonomously plan its path, move, explore, and build a map as required.
Original project documentation:
- Project Seminar 'Robotics and Computational Intelligence' 2024 presented by RIS | Technical University of Darmstadt
- Craft a maze from lasercut MDF walls and generate the corresponding AprilTag Bundle YAML
The seminar focuses on three main tasks:
- In a predefined maze, assign a start and end point for the Jetbot, which will autonomously plan its path and reach the designated location.
- In an undefined maze, the Jetbot explores autonomously and generates a maze YAML file.
- In an undefined maze, the Jetbot explores until it locates a specified object (AprilTag with a code above 900), then returns to the starting point.
The project comprises: client design (frontend UI + some backend algorithms), server design (based on socket communication), and a car system (subdivided below). The car system consists of four main modules: central processing, data acquisition, motor drive control, and pathfinding algorithms.
The client parses the YAML file, constructs a map class, communicates with the car server, and displays real-time data, including camera, motor, and path information. It also allows for real-time adjustment of PID parameters for debugging and modifies the car’s movement state.
Map construction involves analyzing the YAML file, establishing different wall classes based on each wall's center point and orientation, and placing them within a map (manager) class containing two matrices: an object matrix (containing actual wall objects for extracting wall information) and an abstract matrix (a binary matrix for path calculation using A*).
Primarily responsible for motor control, using PID or other control algorithms, including pose correction. The module receives data packets from the data acquisition unit to determine location and then executes movements as directed by the central processing algorithm.
Handles camera-based QR code recognition, identification of front-facing AprilTags on both sides, and IMU data processing. The data is packaged into a custom data class, JLocation, which is continuously transmitted to both the central processing and motor control modules.
The primary role is to pass the pathfinding results to the motor drive for execution. It also transmits data from the data acquisition module to the client for display in real-time and receives instruction packets from the client.
Responsible for path computation and planning, creating the map, and sending suggestions to the central processing unit. The pathfinding module employs two primary algorithms: A* and DFS* (Depth First Search).
- A* Algorithm
Used in tasks 1 and 3, with two path extension options: four-directional and eight-directional.
For a predefined maze, the algorithm results are as shown (using Manhattan distance):
The calculated path contains multiple waypoints. These points are then connected to form a route consisting of the start, end, and target actions, as illustrated below.
The car then moves according to the path instructions.
-
DFS Algorithm
Mainly used for tasks 2 and 3 to systematically explore each branch (node) in an unknown map. Two key challenges in this task include: Free Wall Problem: Can cause the car to revisit the same node indefinitely. Recognizing visited nodes is essential to prevent infinite loops. No Wall Problem: The car reliably detects AprilTags only one unit in front. When no AprilTag is detected ahead, a new node is added as a branch, potentially causing the same issue as the free wall problem.
-
BFS algorithm
It was not completed in time to compare with DFS.
- AprilTag Recognition Angle: In task 1, the Jetbot sometimes approaches AprilTags at a slant, leading to positioning errors and potential collisions.
- Reverse Backtracking in Task 3: Currently, the bot backtracks to the last node in reverse; this could be optimized by using the A* algorithm to calculate the shortest path back to the previous node.、