What sensors are commonly used for obstacle avoidance?
Whether for navigation planning or obstacle avoidance, perceiving the surrounding environment is the first step. For obstacle avoidance, mobile robots need to acquire real-time information about obstacles around them using sensors, including their size, shape, and position. Various sensors are used for obstacle avoidance, each with different principles and characteristics. Commonly used sensors include visual sensors, laser sensors, infrared sensors, and ultrasonic sensors. Below, I will briefly introduce the basic working principles of these sensors.
ultrasound
The basic principle of an ultrasonic sensor is to measure the time of flight of an ultrasonic wave, using the formula d = vt/2 to measure distance, where d is the distance, v is the speed of sound, and t is the time of flight. Since the speed of ultrasound in air is related to temperature and humidity, more accurate measurements require taking into account changes in temperature and humidity, as well as other factors.
The diagram above illustrates an ultrasonic sensor signal . A wave packet composed of ultrasonic pulses with a frequency of tens of kHz is generated by a piezoelectric or electrostatic transmitter. The system detects the reverse sound wave above a certain threshold, and then calculates the distance using the measured time of flight.
Ultrasonic sensors generally have a short operating range, typically several meters, but with a minimum detection blind zone of tens of millimeters. Due to their low cost, simple implementation, and mature technology, ultrasonic sensors are commonly used in mobile robots. However, ultrasonic sensors also have some drawbacks, as shown in the following diagram.
Because sound travels in a cone shape, the distance we actually measure is not a single point, but rather the distance to the nearest object within a certain cone angle. Furthermore, ultrasonic measurements have a relatively long cycle; for example, it takes approximately 20 milliseconds for sound waves to travel the distance to an object about 3 meters away. Additionally, different materials reflect or attract sound waves differently, and multiple ultrasonic sensors may interfere with each other; these are all factors that need to be considered in practical applications.
Infrared
Most infrared ranging methods use the principle of triangulation. An infrared emitter emits an infrared beam at a certain angle. When the beam encounters an object, it reflects back. By detecting the reflected light and using the geometric triangulation relationships of the structure, the distance D to the object can be calculated.
When the distance D is close enough, the value of L in the above diagram will be quite large. If it exceeds the detection range of the CCD, the sensor may not be able to see the object even though it is very close. When the distance D is large, the value of L will be very small, and the measurement accuracy will deteriorate. Therefore, common infrared sensors have relatively short measurement distances, less than ultrasonic sensors, and there are also minimum distance limitations for long-distance measurements. In addition, infrared sensors cannot detect the distance to transparent or nearly blackbody objects. However, compared to ultrasonic sensors, infrared sensors have a higher bandwidth.
laser
Common lidar is based on time- of -flight (ToF), which measures the distance by measuring the time it takes for the laser to travel, d=ct/2, similar to the ultrasonic ranging formula mentioned earlier, where d is the distance, c is the speed of light, and t is the time interval from transmission to reception.
A lidar system consists of a transmitter and a receiver . The transmitter illuminates the target with a laser, and the receiver receives the reflected light waves. Mechanical lidar includes a mechanism with a mirror; the rotation of the mirror allows the beam to cover a plane, enabling the measurement of distance information on that plane. Different methods exist for measuring time of flight. One method uses pulsed lasers, similar to the previously mentioned ultrasonic approach, to directly measure the time taken. However, because the speed of light is much higher than the speed of sound, very high-precision time measurement elements are required, making it very expensive. Another method involves emitting a frequency-modulated continuous laser wave and measuring the difference in frequency between the received reflected waves to determine the time.
Figure 1
Figure 2
A relatively simple approach is to measure the phase shift of the reflected light. The sensor emits modulated light of a certain amplitude at a known frequency and measures the phase shift between the emitted and reflected signals, as shown in Figure 1 above. The wavelength of the modulated signal is lamda = c/f, where c is the speed of light and f is the modulation frequency. After measuring the phase shift difference theta between the emitted and reflected beams, the distance can be calculated using lamda * theta / 4π , as shown in Figure 2 above.
LiDAR can measure distances of tens or even hundreds of meters, with high angular resolution, typically reaching a few tenths of a degree, and high ranging accuracy. However, the confidence level of the measured distance is inversely proportional to the square of the received signal amplitude. Therefore, distance measurements of black bodies or distant objects are not as accurate as those of bright, nearby objects.
Furthermore, lidar is ineffective against transparent materials such as glass. Also, due to its complex structure and high component costs, lidar is very expensive. Some low-end lidar systems use triangulation for ranging. However, their range is limited, generally within a few meters, and their accuracy is relatively low. But for SLAM in low-speed indoor environments or obstacle avoidance in outdoor environments, they are still quite effective.
Visual
There are many commonly used computer vision solutions, such as binocular vision, Time-of-Flight (TOF) based depth cameras, and structured light based depth cameras. Depth cameras can simultaneously acquire RGB images and depth maps. However, whether based on TOF or structured light, their performance is not ideal in bright outdoor lighting conditions because they both require active light emission.
Like structured light-based depth cameras, the emitted light generates relatively random yet fixed speckle patterns. These specks, when they hit an object, are captured at different positions by the camera due to varying distances. The offset of the captured specks from a calibrated standard pattern at different positions is then calculated. Using parameters such as camera position and sensor size, the distance between the object and the camera can be determined. However, our current E-Patrol robot primarily operates in outdoor environments, where active light sources are significantly affected by sunlight and other conditions. Therefore, a passive vision solution based on binocular vision is more suitable. Thus, our vision solution is based on binocular vision.
Binocular vision ranging is essentially a triangulation method. Because the two cameras are positioned differently, much like our two eyes, they see objects differently. The same point P seen by both cameras will have different pixel positions during imaging. Triangulation can then be used to measure the distance to this point. Unlike structured light methods, where the points calculated are actively emitted and known, binocular algorithms typically calculate points using image features captured by the algorithm, such as SIFT or SURF features. This results in a sparse image.
For effective obstacle avoidance, sparse maps are insufficient; we need dense point clouds containing depth information for the entire scene. Dense matching algorithms can be broadly categorized into two types: local algorithms and global algorithms. Local algorithms use local pixel information to calculate depth, while global algorithms utilize all information within the image. Generally, local algorithms are faster, but global algorithms offer higher accuracy.
Both of these categories have many different specific algorithm implementations. From their output, we can estimate the depth information of the entire scene. This depth information helps us find walkable areas and obstacles in the map scene. The overall output is similar to a 3D point cloud map output by LiDAR, but it provides much richer information. Compared to LiDAR, visual LiDAR has the advantage of being much cheaper, but its disadvantages are also obvious: lower measurement accuracy and much higher computational requirements. Of course, this difference in accuracy is relative and is perfectly adequate for practical applications. Furthermore, our current algorithm can run in real-time on our NVIDIA TK1 and TX1 platforms.
Images collected by KITTI
In the actual output depth map, different colors represent different distances.
In practical applications, we read continuous video frame streams from cameras. We can use these frames to estimate the motion of target objects in the scene, build motion models for them, and estimate and predict their direction and speed of motion. This is very useful for actual walking and obstacle avoidance planning. The above are some of the most common types of sensors, each with its own advantages and disadvantages. In real-world applications, a combination of different sensors is generally used to maximize the robot's ability to correctly perceive obstacle information under various application and environmental conditions. Our company's E-Patrol robot's obstacle avoidance solution primarily uses binocular vision, supplemented by various other sensors, to ensure that obstacles within a 360-degree spatial range around the robot can be effectively detected, guaranteeing the robot's walking safety.
Common obstacle avoidance algorithm principles
Before discussing obstacle avoidance algorithms, we assume the robot already has a navigation planning algorithm to plan its movement and follow the planned path. The task of the obstacle avoidance algorithm is to update the target trajectory in real time and avoid obstacles when the robot is performing normal walking tasks, based on the sensor input detecting the presence of obstacles.
Bug algorithm - Zhihu user Wufang expressed no opinion
The Bug algorithm is probably the simplest obstacle avoidance algorithm. Its basic idea is to walk around the detected obstacle's outline after it is detected, thus avoiding it. There are many variations of the Bug algorithm, such as the Bug1 algorithm, where the robot first completely circles the object and then leaves from the point with the shortest distance to the target. The Bug1 algorithm is inefficient, but it guarantees that the robot will reach the target.
Bug1 Algorithm Example
In the improved Bug2 algorithm, the robot initially tracks the outline of the object, but does not circle the object completely. When the robot can move directly to the target, it can separate directly from the obstacle, thus achieving a shorter total robot walking path.
Bug2 Algorithm Example
Besides these, there are many other variations of the Bug algorithm, such as the tangent Bug algorithm. In many simple scenarios, the Bug algorithm is relatively easy and convenient to implement, but it doesn't take into account limitations such as robot dynamics, making it less reliable and effective in more complex real-world environments.
Potential Field Method (PFM)
In fact, the potential field method can be used not only for obstacle avoidance but also for path planning. The potential field method treats the robot as a point within a potential field, moving with the field. The target represents a low point, i.e., an attractive force to the robot, while obstacles act as high points in the potential field, i.e., repulsive forces. All these forces superimpose on the robot, smoothly guiding it towards the target while avoiding collisions with known obstacles. When the robot detects a new obstacle during its movement, the potential field needs to be updated and the path planning re-established.
The image above is a typical example of a potential field. In the top image (a), the starting point is in the upper left corner, the target point is in the lower right corner, and the three squares in the middle represent obstacles. The middle image (b) is an equipotential diagram. Each continuous line in the diagram represents an equipotential line, and the dashed line represents a path planned within the entire potential field. Our robot walks along the direction indicated by the potential field, and you can see that it will bypass the relatively tall obstacle.
The bottom diagram shows the potential field formed by the attraction of our entire target and the repulsion generated by all our obstacles. You can see that the robot starts from the top left corner and moves along the downward direction of the potential field to reach the final target point. The potential field of each obstacle is on a very high platform, so the planned path will not go over this obstacle.
An extended approach adds two additional potential fields to the basic potential field: a transport potential field and a task potential field. These additionally consider the interaction between the robot's own motion direction, speed, and other states, and obstacles.
Rotational potential fields consider the relative orientation of obstacles and the robot. When the robot moves towards an obstacle, the repulsive force increases; when moving parallel to the obstacle, the repulsive force decreases because it's obvious it won't collide with it. Task potential fields eliminate obstacles that don't affect the robot's near-term potential energy based on its current speed, thus allowing for a smoother trajectory. Other improved methods include harmonic potential fields. While potential field methods have theoretical limitations, such as the problem of local minima or oscillations, they are quite effective in practical applications and relatively easy to implement.
Vector Field Histogram (VFH)
During its execution, the algorithm creates a local map of the mobile robot's current surroundings based on polar coordinates. This local map uses a raster representation and is updated with the most recent sensor data. The polar coordinate histogram generated by the VFH algorithm is shown in the figure below:
In the diagram, the x-axis represents the angle of the obstacle perceived by the robot, and the y-axis represents the probability p of the obstacle existing in that direction. In practical applications, this histogram is used to first identify all sufficiently large gaps that the robot can pass through. Then, the cost function of each of these gaps is calculated, and finally, the path with the lowest cost function is selected for passage.
The cost function is influenced by three factors: the target direction, the robot's current direction, and the previously selected direction. The final cost is a weighted average of these three factors, and the robot's selection preference can be adjusted by changing different weights. The VFH algorithm also has other extensions and improvements; for example, the VFH+ algorithm considers the constraints of robot kinematics.
Due to differences in their underlying motion structures, the actual movement capabilities of machines are limited. For example, the structure of a car prevents it from turning on the spot at will. The VFH+ algorithm considers the obstruction effect of obstacles on the robot's actual movement trajectory, filtering out trajectories that, although not blocked by obstacles, are practically unattainable due to their obstruction. Our E-Patrol robot uses a two-wheel differential drive motion form, which is very flexible and less affected by these factors in practical applications.
Please see this diagram for details:
There are many traditional obstacle avoidance methods like this. In addition, there are many other intelligent obstacle avoidance technologies, such as neural networks and fuzzy logic. Neural network methods train and model the robot's entire walking path from its initial position to the target position. When applied, the input of the neural network is the robot's previous pose and velocity, as well as the sensor input, and the output is the desired next target or direction of motion.
The core of the fuzzy logic method is the fuzzy controller , which requires writing multiple fuzzy logic statements to control the robot's obstacle avoidance process, based on the knowledge of experts or the experience of operators. For example, fuzzy logic could be as follows: First, if an obstacle is detected far to the right, turn slightly to the left; second, if an obstacle is detected close to the right, decelerate and turn further to the left; and so on.
