Communications and Path Planning of Drones

A small quadrocopter in the air

We develop solutions for wireless communications and flight path planning in multi-drone systems with application in disaster management and aerial transport. Methods range from algorithm design to experimental performance analysis with networked drones in the air.

Small drones fly routes in an autonomous manner, carry cameras for aerial photography, and transport goods from one place to another. The terms “unmanned aerial vehicle (UAV)” and “flying robot” are often used as synonyms for a drone. The spectrum of applications is broad, including aerial monitoring of industrial plants and agriculture fields as well as support for first time responders in case of disasters. For some applications, it is beneficial if a team of drones rather than a single drone is employed. Multiple drones can cover a given area faster or take photos from different perspectives at the same time. The development of such multi-drone systems is still at an early stage, such that profound research efforts are needed.

A team of professors with their groups in Klagenfurt has been working on multi-drone systems since 2008. They have developed solutions for wireless networking, movement path planning, distributed decision making and cooperation, aerial imaging, and, more recently, autonomous navigation. Research has covered novel algorithms, system-level emulation, and, in particular, experimental performance evaluations with drones in the air. The applications in focus are aerial area monitoring, search and rescue, and delivery of goods. Funded projects include cDrones (2008-2012), SINUS (2013-2015), SOSIE (2013-2015), Forest iMate (2016-2018), and a Karl Popper Science Kolleg in networked autonomous aerial vehicles (2017-2020). In this context, Christian Bettstetter and his team have been mainly working on wireless communications, path planning, and job selection.

Activities started in 2008 with the development of a prototype system for aerial surveillance to assist a rescue team in case of a disaster was developed. Image processing had to deal with the challenge of low altitude aerial photography. The developed software was successfully demonstrated at a series of events, including a firefighter drill. The project team has developed a system that provides functionality similar to Google Earth and Microsoft Virtual Earth but capturing small areas with much higher resolution: A user first outlines the area of interest on a map. Small drones fly over the specified area, take images, and provide an accurate and up-to-date overview picture of the environment. “Our solution requires mission planning and coordination for multiple aerial vehicles,” explains senior researcher Markus Quaritsch. The system computes the flight routes for the individual drones taking into account the maximum flight time due to battery constraints. A flight route consists of a sequence of waypoints specified in GPS coordinates, the flight altitude, and a set of actions for every waypoint such as taking a photo, setting orientation. The drones autonomously fly according to the computed plan without any need for human interaction. The drones are equipped with different sensors (e.g., thermal camera, conventional photo camera) to build a multi-layered overview image. The pictures taken are pre-processed on board the drone and sent to the ground station during flight. At the ground station the individual pictures are mosaicked to a large overview image. The pictures show significant perspective distortions due to the low altitude of less than 150 meters. Under guidance of Bernhard Rinner, the team has developed and patented an incremental approach for computing the overview picture that provides quick feedback to the user and is geometrically correct and visually appealing at the same time.

The real-world applicability of the system is a major objective. It was demonstrated several times in coordinating fire fighters performing service drills. “We recently participated in a large-scale forest fire exercise in the Austrian-Slovenian border region,” Quaritsch says. “Other demonstrations included the monitoring of a large construction site near Vienna and the observation of an industrial accident”.

Postdoctoral researchers Evsen Yanmaz and Aymen Fakhreddine and PhD students Samira Hayat and Raheeb Muzaffar have been working with Bettstetter on solutions for wireless communications in multi-drone systems. A drone network has air-to-ground and air-to-air links, where the wireless nodes are moving in three-dimensional space. Yanmaz explains: “Our first real-world experiments showed that off-the-shelf IEEE 802.11 systems lead to poor performance, but some antenna modifications make the system work.” The performance of different IEEE 802.11 technologies—such as 802.11a, 11s, 11n and 11ac—was evaluated by real-world measurements, and a multicast video streaming approach for drones has been developed. More recent research addresses drones connected to cellular networks (LTE-Advanced and 5G), in joint work with network operators. Real-world experiments show that quadrocopters, flying at the typical height and speed for commercial operation, face problems in terms of handovers and interference.

A higher-layer issue is the role of communication in the planning of flight paths and its adaptive online replanning. “We consider three phases of a search and research mission,” PhD candidate Samira Hayat says, “the search for a lost person, the notification of a ground station, and the maintenance of a multihop communication path with a certain quality of service.” Our algorithm, which was developed in collaboration with Timothy X Brown from Carnegie Mellon, can be tuned to give priority to a certain phase and tells us the optimum number of drones to be used in the mission. An alternative path planning solution, which takes into account the interference caused on the ground and is based on reinforcement learning, was developed at VirginiaTech in collaboration with Bettstetter.

Another PhD student, Pasquale Grippa, has been studying the concepts for employing a network of drones for delivery of goods. This service becomes an option if classical means of transportation, like trucks, trains, and planes are inappropriate. First, this comes about if roads, railway tracks, or landing facilities do not exist, if natural disasters make it impossible to use them, or if their use is too dangerous or too time-consuming. In this context, a compelling service would be the delivery of medicine, vaccinations, or laboratory samples for patients in remote areas and crisis regions. Second, such a service is also worthwhile in densely populated metropolitan areas, when congestion makes roads nearly impassable. In an interdisciplinary team with Friederike Wall and Doris Behrens, Bettstetter and Grippa analyzed job selection policies that control how an interconnected team of drones resolves service requests that are randomly distributed in space and time. The entities of the system are goods, customers, vehicles, and depots. Customers request goods that are stored in depots and delivered by vehicles. Service requests, also denoted as jobs or customer demands, are not known in advance and arrive over time for certain locations according to a space-time stochastic process. Instead of applying a centralized scheduler that intends to optimize the performance, the team employs a set of rules to be run in each vehicle. “Such a distributed approach is required if no central control entity is available,” Behrens states. In this sense, the system’s “intelligence” is literally embedded into each vehicle, meaning that each vehicle decides by its own which job to select next, thus raising the autonomy of vehicles to a level that goes beyond autonomous flying. Grippa is fascinated by the multidisciplinary aspects of his work. “It involves multi-agent systems, scheduling, logistics, queuing theory, and others,” he says.

Selected Publications

Keynotes

Publications

Systems

Wireless Connectivity

Path Planning and Swarm Formation