טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
Ph.D Thesis
Ph.D StudentGal Oren
SubjectUrban Terrain Analysis for Trajectory Planning of
Multi-Agents
DepartmentDepartment of Civil and Environmental Engineering
Supervisor Professor Emeritus Yerach Doytsher
Full Thesis textFull thesis text - English Version


Abstract

In the past few years, the 3D GIS domain has seen a rapid development, becoming increasingly accessible for different disciplines. Spatial analysis in a 3D environment appears to be one of the most challenging topics in the communities currently dealing with spatial data. One of the most basic problems in spatial analysis is related to visibility computation in such an environment.

The visibility problem has been extensively studied over the past twenty years, due to the importance of visibility in GIS, computer graphics, computer vision and robotics. Most previous works approximate the visible parts to find a fast solution in open terrains, and do not challenge or suggest solutions for a dense urban environment. More exact visibility methods are highly complex, and cannot be used for fast applications due to the long computation time.

In the first part of our research, we present a unique solution for the 3D visibility problem in built-up areas. A 3D visibility algorithm based on an analytic solution for basic building structures is introduced. Using simple geometric operations of projections and intersections between visible pyramid volumes, hidden surfaces between buildings are rapidly computed.

The algorithm, demonstrated using a schematic structure of an urban built-up environment and compared to the Line of Sight (LOS) method, demonstrates the computation time efficiency. Whereas the common visibility methods (LOS approach) require scanning all of the object’s points, the presented solution, by applying a continuous parameterization approximating of the building’s corners, successfully avoids the need to handle each point separately.

Generally, urban environments can be divided into static objects such as buildings, roads, etc., and dynamic objects such as moving cars, tree branches, pedestrians etc. Static objects, which are modeled by 3D GIS models, do not change frequently. On the other hand, dynamic objects cannot be modeled efficiently by a constant 3D model, and must be updated from on-line sources, such as web cameras, within a certain time period.

We present a unique formulation and concept of the dynamic object's effect on constant objects, such as buildings, dealing with visibility problems in 3D urban environments. Dynamic objects in a 3D urban environment are features such as cars, pedestrians and trees. In order to overcome this problem, we focused on modeling, predicting and estimating dynamic objects' future location in the environment.

We extended our visibility analysis and tested a multi-sensors placement solution for optimized coverage in dense urban environments from the point of view of visibility

In the second part of our research, we deal with visibility-based trajectory planning methods. We present efficient and fast visible trajectory planning for unmanned vehicles in a 3D urban environment.

In the last part, we extend our problem and explore visible trajectories planning for patrolling applications using heterogeneous multi-agents in 3D urban environments. We consider two kinds of agents, with different kinematic and perception capabilities. These key features allow for new planning of an optimal patrolling strategy for heterogeneous agents in an urban environment.