GRAPH-BASED METHODS FOR PATH PLANNING WITH DYNAMIC OBSTACLES USING LINEAR TEMPORAL LOGIC

Postgraduate

Abstract
Autonomous vehicles are expected to play a key role in rescue and transportation. Planning an optimal path with the minimum computational effort for these vehicles in their missions improves their efficiency and adds safety for the vehicles and third parties on the ground. The objective of this thesis is to study the computational effort of four planning methods that implement linear temporal logic (LTL) to translate the high-level mission requirements and environmental specifications. The Potential Field Method and the Critical Path method required less computational effort to find one of the shortest paths for the mission The Multigraph Network Planning method and the Critical Path method can find all the possible paths with predetermined path length.

Motivation

Motion planning is an important problem in various areas such as robot navigation, driverless cars, robotic surgery, protein folding, and safety and accessibility in computer-aided architectural design. The research in this thesis is motivated by the problem of motion planning for unmanned aerial vehicles (UAV).

 The idea of building flying machines was first conceived around 2,500 years ago in ancient Greece and China. In 425 BC, Archytas, known as Leonardo da Vinci of the Ancient World, built the first known autonomous mechanical bird, “the pigeon”, which is reported to be able to fly about 200 meters. During the same era, the Chinese experimented different types of flying machines, such as hot air balloons, rockets, and kites. These machines were used both for entertainment and military. Historical records show that a “wooden hawk” was used for reconnaissance around 450 BC, and Ming Dynasty armies used a kite in the shape of a crow to bomb enemy positions. Before the appearance of manned aviation in the late 1700s, these flying machines had already shown their potential in various areas. Around the time of First World War (1916), unmanned aircraft appeared.

In recent years, autonomous robots have replaced a lot of people to do the “dull, dirty, and dangerous” work over the years. While autonomous on-land vehicles (selfdriving cars) have been used to improve our driving experience, unmanned aerial vehicles, have had many applications as well. Johns Hopkins researcher Timothy

Amukele et al. demonstrated that drones are safe for transportation of blood products. In Amukele’s experiment, his team not only showed that a drone could transfer blood samples in places like coastal Haiti after earthquake, where the land is rough, but waterways are clear, but also successfully tested that blood temperature would be kept in acceptable levels after 8 to 12 miles travelling at around 330 feet above the ground. Microdrones' demonstration with the German Lifeguard Association also showed that if a drone carries a self-inflating flotation device, it can help the swimmer float and give time to lifeguards to react. Amukele’s study and Microdrones both showed that UAVs

have the potential in helping save lives in emergency situations.

In terms of reacting to industrial accidents or other dangerous situations, UAVs plays a more important role nowadays, such as radiation detecting for toxic leaks and tracking hurricanes. Dronemakers FlyCam UAV partnered with US Nuclear Corp., a radiation detection company, demonstrated that “The UAVs can be used to detect radiation leaks in nuclear power plants or flown into plumes of smoke from a burning building to give first responders immediate data about what kinds of hazards might be present. It can also be used for to monitor public events, sea ports or geographic areas to detect possible dirty radiological bombs or the use of chemical and biological agents.” NASA’s RQ-4 Global Hawk is built for watching disasters unfold. In 2016, NASA used the Global Hawk to drop expendable sensors to record temperatures, pressure, relative humidity, and wind speed and direction, and transfer the information to scientists to track Hurricane Matthew. 

UAVs with their ability to fly, has not only been used in those extreme environments, but also been used in our everyday life. It has taken roles such as inspection and monitoring in highly risky fields, surveying and mapping cities, condition survey in civil engineering field, and imaging for HD films, videos, and HR photos. Both in military and civil operations, more and more complicated tasked are excepted to be done by UAVs.


Problem Definitions

This thesis focuses on finding a shortest path for unmanned vehicles under high-level specifications in dynamic environment.