Using search algorithms to help guide unmanned aerial vehicles in dense city environments

Unmanned aerial vehicles (UAV) have important uses ranging from aerial photography for agricultural and environmental monitoring to military and policing use. Much of the current UAV technology requires a line-of-sight connection with the UAV, meaning the operator can see it. The data collected by the UAV is then transmitted via free-space optical communication, which uses light in open spaces to send information. However, this technology is very vulnerable to signal blockage, especially in dense urban areas where the line of sight can be blocked by buildings and vegetation.

In a recently published paper, researchers have developed a method to find a near-optimal position of the UAV such that the UAV can establish guaranteed line-of-sight links with two ground users.

The paper was published in Intelligent and Converged Networks on March, 30.

“Line-of-sight conditions are required in many emerging communication systems. Taking advantage of their mobility in three-dimensional space, UAVs can easily establish line-of-sight links with ground users. However, most of the existing UAV deployment schemes adopt pure line-of-sight channel models or probabilistic channel models, and, thus, cannot guarantee line-of-sight conditions,” said Yuanshuai Zheng, a researcher at the School of Science and Engineering at the Chinese University of Hong Kong in Shenzhen, China.

To achieve this, researchers first calculated the optimal relay placement for a UAV and then used a two-stage search algorithm to solve a variety of calculations to help determine the best positioning for the UAV. The experiments were done over a real 3D city map. One necessary calculation is the building coverage ratio, which is used to quantify the building density of the area. These calculations help untangle the problems a UAV might encounter in the real world.

“Unlike radio frequency signals, which can penetrate some obstacles such as walls and trees, optical signals used in free-space optical communications are easily blocked by physical obstacles,” said Zheng. “Some other work uses 3D maps or radio maps to search for the optimal UAV position offline, but both the maintenance cost of maps and the complexity of offline computation are high. In this paper, an online search algorithm with line-of-sight guarantees is proposed. Numerical results demonstrate that the proposed scheme achieves over 95% of the performance of the exhaustive 3D search scheme within a 300-meter search length.”

Unlike other research into free-space optical communication systems for UAVs, this research took the actual landscape of the city into consideration. Searching on a theoretical equipotential surface is possible, but in the real world, machines run into problems. The algorithm that the researchers developed identified the equipotential surface between two users. An equipotential surface refers to the space between two users where the same performance can be obtained by them from the UAV. If the equipotential surface is curved, then additional calculations can be done to search for the best positioning on an approximated vertical plane.

When there are two users on the ground and some obstruction between them, buildings or trees, for example, and the users are in shadow, the algorithm can successfully determine search trajectories for the UAV to continue its trajectory. When compared to more manual exhaustive 3D search, the algorithm that the researchers developed was able to reach over 95% of performance of the exhaustive 3D search, making it a potentially viable option for this technology.

Looking ahead, researchers plan to investigate the capabilities of the developed algorithms. The current research relies on two users, but if there are more than two, the calculations proposed in this research cannot be applied directly. In future research, they will develop additional calculations that can account for more users.

“Ultimately, we want to propose an ultra-low complexity online UAV deployment scheme. Such a scheme can theoretically guarantee that the performance meets certain requirements, while at the same time enabling rapid response and deployment of multiple UAVs in extremely complex, unknown, and potentially changing environments,” said Zheng.

Provided by
Tsinghua University Press