In-depth Practice of Dynamic Obstacle Avoidance with myAGV

Introduction

In a previous article, I mentioned the purchase of a myAGV, a mobile robot controlled by a Raspberry Pi 4B. The previous article introduced how myAGV achieved mapping, navigation, and static obstacle avoidance, but we know that this is only the foundation for the robot's autonomous navigation capability. In practical application scenarios, robots need to face complex dynamic environments, such as crowds and obstacles. How to achieve reliable dynamic obstacle avoidance is a problem that we are constantly exploring and challenging. In this article, we will share our practice and experience in exploring dynamic obstacle avoidance, hoping to provide some reference and inspiration for other makers and robot enthusiasts.

Previous article

Production

myAGV

Before delving into dynamic obstacle avoidance, let me introduce the myAGV, the robot I am using.The myAGV is a mobile robot produced by Elephant Robotics. It is controlled by a Raspberry Pi 4B, with an Ubuntu 18 system and ROS compilation environment built-in. It is also equipped with a 360° Lidar and a high-definition camera. The myAGV adopts competition-level mecanum wheels and has a fully enclosed design with a metal frame.

Dynamic Obstacle Avoidance

Dynamic obstacle avoidance refers to the technology used by intelligent mobile devices such as mobile robots or autonomous vehicles to perceive changes in the surrounding environment in real-time and take corresponding measures to avoid collisions with obstacles during movement. To achieve dynamic obstacle avoidance, it is necessary to perceive changes in the environment in real-time, such as monitoring the position, size, shape, and motion status of obstacles. Then, by processing and analyzing this information, appropriate action commands are generated to enable the robot or vehicle to avoid collisions with obstacles and continue moving forward.

Here is a case used by others, the content is about the record of fast dynamic obstacle avoidance of UAV

Obstacles that appear suddenly need to be avoided immediately to avoid damage to the drone. What we want to achieve today is that myAGV can avoid obstacles in time during automatic navigation.The dynamic obstacle avoidance algorithm provided by Elephant Robot is based on TEB and DWA algorithms.

TEB algorithm

TEB (Timed-Elastic-Band) is an algorithm used for trajectory optimization, which can be applied to dynamic obstacle avoidance and path planning for robots. It mainly modifies the initial global trajectory generated by the global path planner in order to optimize the robot's motion trajectory, which belongs to local path planning. During the trajectory optimization process, this algorithm has various optimization objectives, including but not limited to: overall path length, trajectory running time, distance to obstacles, passing through intermediate path points, and compliance with robot dynamics, kinematics, and geometric constraints.

The starting point and target point states are both determined by the global planner, with N control points inserted in between, controlled by rubber bands in a set shape. This path is deformable, and the deformation is based on all the constraints acting as external forces on the rubber band, such as the distance to obstacles, maximum speed and angular velocity of the mobile robot, maximum turning radius, etc. These constraints ensure the safety and stability of the mobile robot.

The TEB algorithm is implemented through the following steps:

1. Generate an initial path based on the robot's current position and target position.

2. Represent the path as a series of line segments over time, known as trajectory segments. Each trajectory segment represents the robot's path of motion along a straight line during a time interval.

3. Optimize each trajectory segment to satisfy the robot's motion constraints and obstacle avoidance requirements. The optimization objective is to minimize the length and motion time of the trajectory segment, while avoiding collisions with obstacles.

4. Concatenate the optimized trajectory segments to form the robot's final motion trajectory. If the robot encounters an obstacle, it can regenerate the trajectory segments and optimize them again.

The advantages of the TEB algorithm are that it can dynamically avoid obstacles during motion and handle the robot's dynamic motion. Additionally, the TEB algorithm can be combined with other obstacle avoidance algorithms, such as model predictive control algorithms, to improve the effectiveness of obstacle avoidance.

Image from:https://www.mdpi.com/1424-8220/21/24/8312

DWA algorithm

DWA (Dynamic Window Approach) is an algorithm used for dynamic obstacle avoidance in mobile robots. It aims to search for the optimal motion trajectory within the robot's motion range to avoid obstacles. The DWA algorithm represents the robot's motion trajectory as a combination of (v, w) velocity and angular velocity, and then searches and evaluates these combinations to find the optimal motion trajectory.

The implementation process of the DWA algorithm is as follows:

1. Generate a set of candidate velocities and angular velocities, known as the velocity window, based on the robot's current position and target position.

2. For each velocity and angular velocity combination in the velocity window, calculate the robot's achievable positions over the next time interval, i.e., the motion trajectory.

3. Evaluate each motion trajectory to determine whether it collides with obstacles. Evaluation methods include calculating the cost function along the trajectory, such as distance to obstacles and velocity.

4. Based on the evaluation results, select the motion trajectory with the lowest cost function, and use it as the robot's motion command.

TEB-DWA algorithm

TEB has certain advantages in implementing dynamic obstacle avoidance. However, the TEB algorithm also has limitations, which include:

● Strong dependence on the initial path: The TEB algorithm's performance is highly dependent on the quality of the initial path. If the initial path has significant bias or error, the TEB algorithm may become stuck in an unsolvable dilemma.

● Strong dependence on the environment model: The TEB algorithm requires an accurate environment model, including information on obstacle position and shape. If the environment model has bias or errors, the TEB algorithm may have path planning errors.

● High demand for computational resources: The TEB algorithm requires significant computation and optimization, with high time complexity and computing resource demands.

The DWA algorithm can also search and evaluate trajectories to select the optimal path solution, but it also has limitations, which include:

● Inability to handle high-speed moving obstacles: The DWA algorithm is based on the robot's motion model and environment perception, searching and evaluating velocity and angular velocity combinations to find the optimal motion trajectory to avoid obstacles. However, in the case of high-speed moving obstacles, the DWA algorithm may not perceive and process them in time, resulting in collisions and safety issues.

● High demand for environment model: The DWA algorithm requires the robot to have good environmental perception ability to obtain information on obstacle position, shape, and size. If the environment model is inaccurate or incomplete, the DWA algorithm may not evaluate the cost function of the motion trajectory correctly, resulting in erroneous robot motion and obstacle avoidance failure.

● Inability to handle uncertain environments: The DWA algorithm is based on the assumption of a static environment where obstacle positions do not change. However, in uncertain environments, such as scenes with frequent dynamic obstacles, the DWA algorithm may not be effective in avoiding obstacles, resulting in collisions and safety issues.

● Difficulty in handling multi-robot cooperative obstacle avoidance: The DWA algorithm is usually designed for single robot obstacle avoidance and may have difficulty handling multi-robot cooperative obstacle avoidance. In multi-robot cooperative obstacle avoidance, it is necessary to consider the interaction and coordination between robots to design more complex and advanced obstacle avoidance algorithms.

To address the limitations of the TEB and DWA algorithms and achieve more refined and efficient dynamic obstacle avoidance and path planning, the TEB-DWA algorithm has been proposed. The core idea of the TEB-DWA algorithm is to combine the advantages of the TEB and DWA algorithms to design a more refined and efficient dynamic obstacle avoidance algorithm. Specifically, the TEB-DWA algorithm uses the elastic band method of the TEB algorithm to achieve path planning and optimization, while also using the velocity window method of the DWA algorithm to search and evaluate velocity and angular velocity, thus achieving dynamic obstacle avoidance and path planning for mobile robots.

The implementation process of the TEB-DWA algorithm mainly includes the following steps:

1. Establishment of robot motion model: Based on the robot's motion constraints and dynamic model, establish the robot's motion model to calculate the robot's motion trajectory and velocity constraints.

2. Environment perception and obstacle detection: Obtain information on the position, shape, and size of obstacles in the environment through the robot's sensors, perform obstacle detection and classification, and determine the robot's motion path and obstacle avoidance strategy.

3. Elastic band path planning: Generate the robot's motion path using the elastic band method based on the robot's start and end points, and consider the robot's motion constraints and obstacle avoidance needs to achieve path planning and optimization.

4. Velocity window search and evaluation: Using the DWA algorithm, search for the optimal speed and angular velocity combination for the robot based on the robot's motion model and environment perception information, and evaluate the cost function of each speed and angular velocity combination to determine the robot's motion trajectory and obstacle avoidance strategy.

5. Motion control and execution: Implement the robot's motion control and execution based on the calculated optimal speed and angular velocity combination using a control algorithm to achieve dynamic obstacle avoidance and path tracking for the robot.

Get started

In ROS, the Move Base package can be used to implement the TEB-DWA algorithm. Move Base is a commonly used path planning and navigation package in ROS, which provides various path planning algorithms and navigation functions, including the TEB-DWA algorithm. The following are the steps to use the TEB-DWA algorithm in ROS:

1. Install the Move Base package: To install the Move Base package in ROS, you can use the following command: "sudo apt-get install ros--move-base".

2. Configure the Move Base parameters: Before using the TEB-DWA algorithm, it is necessary to configure the parameters of Move Base. The move_base.launch file can be used to configure parameters, such as setting the robot's start and end points, map information, motion constraints, and obstacle avoidance parameters. The parameters can be adjusted and optimized according to specific application scenarios and task requirements.

3. Run the Move Base node: After configuring the parameters, the Move Base node can be started using the following command: "roslaunch move_base move_base.launch".

4. Publish the target point: After running the Move Base node, the move_base/goal topic can be used to publish the robot's target point. The rostopic pub command can be used to publish the target point.

5.Monitor the robot's status and feedback: After the robot starts moving, the /move_base/status topic can be used to monitor the robot's status and feedback information. The rostopic echo command can be used to monitor the status and feedback information. “rosdep echo /move_base/status”

Mapping

We first build a map and conduct an experiment of obstacle avoidance.

Open the terminal and run the command to start the radar.

cd myagv_ros
source ./devel/setup.bash
roslaunch myagv_odometry myagv_active.launch

and then run the gmapping scripts to build map.

roslaunch myagv_navigation myagv_slam_laser.launch

Let's use the default configuration and see how it works.

This seems to achieve dynamic obstacle avoidance, but it seems a little stupid, and it goes around to scan the environment when obstacles are found.

We modified the parameters of the algorithm configuration - planned frequency and re-tested. It looks better.

Summary

We have been using the myAGV for some time now. First of all, I really like its appearance. It looks cool and there are no exposed structural components. The internal components are well protected, and there is some level of protection in case of collisions. Secondly, the accompanying documentation is very detailed and provides a quick and easy-to-use template, which is very helpful for someone who is new to the product.

Overall, It is easy to use. Additionally, there are many communities based on Raspberry Pi that provide help and support, and there are many excellent examples available. However, there are some aspects that need improvement. For example, when building maps, the accuracy is sometimes not very precise, possibly due to obstructions caused by the shell. Also, it would be great if the usage time could be longer.