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 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.

 

Other contributors include Junting Chen and Yinjun Wang of the Chinese University of Hong Kong in Shenzhen, China.

 

The National Key R&D Program of China, the Basic Research Project of Hetao Shenzhen-HK S&T Cooperation Zone, the National Natural Science Foundation of China, the Shenzhen Science and Technology Program, the Guangdong Research, and Guangdong Provincial Key Laboratory of Future Networks of Intelligence funded this research.

 

##

 

About Intelligent and Converged Networks 

 

Intelligent and Converged Networks is an international specialized journal that focuses on the latest developments in communication technology. The journal is co-published by Tsinghua University Press and the International Telecommunication Union (ITU), the United Nations specialized agency for information and communication technology (ICT). Intelligent and Converged Networks draws its name from the accelerating convergence of different fields of communication technology and the growing influence of artificial intelligence and machine learning.

 

About Tsinghua University Press

 

Established in 1980, belonging to Tsinghua University, Tsinghua University Press (TUP) is a leading comprehensive higher education and professional publisher in China. Committed to building a top-level global cultural brand, after 41 years of development, TUP has established an outstanding managerial system and enterprise structure, and delivered multimedia and multi-dimensional publications covering books, audio, video, electronic products, journals and digital publications. In addition, TUP actively carries out its strategic transformation from educational publishing to content development and service for teaching & learning and was named First-class National Publisher for achieving remarkable results.

 

---

---