Optimizing Urban LiDAR Flight Path Planning Using a Genetic Algorithm and a Dual Parallel Computing Framework

This paper introduces a genetic algorithm (GA) and a beam tracing algorithm incorporated within a dual parallel computing framework to optimize urban aerial laser scanning (ALS) missions to maximize vertical façade data capture, as needed for many three-dimensional reconstruction and modeling workfl...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Anh Vu Vo, Debra F. Laefer, Jonathan Byrne
Formato:	article
Lenguaje:	EN
Publicado:	MDPI AG 2021
Materias:	LiDAR point cloud aerial laser scanning aerial mapping flight path planning spatial optimization Science Q
Acceso en línea:	https://doaj.org/article/f60bd1d39b004301a722651d85ca3c50
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:f60bd1d39b004301a722651d85ca3c50
record_format	dspace
spelling	oai:doaj.org-article:f60bd1d39b004301a722651d85ca3c502021-11-11T18:56:42ZOptimizing Urban LiDAR Flight Path Planning Using a Genetic Algorithm and a Dual Parallel Computing Framework10.3390/rs132144372072-4292https://doaj.org/article/f60bd1d39b004301a722651d85ca3c502021-11-01T00:00:00Zhttps://www.mdpi.com/2072-4292/13/21/4437https://doaj.org/toc/2072-4292This paper introduces a genetic algorithm (GA) and a beam tracing algorithm incorporated within a dual parallel computing framework to optimize urban aerial laser scanning (ALS) missions to maximize vertical façade data capture, as needed for many three-dimensional reconstruction and modeling workflows. The optimization employs a low-density point cloud from the site of interest as a spatial representation of the urban scene. The GA is suitable for LiDAR flight path optimization due to its capability of handling open-ended problems that have many solutions. However, GAs require evaluating a very large number of candidates. The use of an initial point cloud allows realistic modeling of the urban environment in the optimization at the cost of high data input volumes. To cope with the computational and data demands, a dual parallel computing framework was devised. The parallel computing framework consists of two layers of parallelization. In the upper layer, multiple evaluators work in parallel and in conjunction with a main multi-threading GA optimizer to perform GA operations and evaluate the flight paths. In the lower layer, to evaluate assigned flight paths, each evaluator distributes its data and computation to multiple executors, which can reside on multiple physical nodes of a distributed-memory computing cluster. In addition to parallelism, the data partitioning on the lower layer allows out-of-core computation. Namely, data partitions are efficiently transferred between disks and memory so that only relevant subsets of data are kept in the main memory. The objective of the proposed method is threefold: (1) search for flight paths that yield the highest numbers of vertical points, (2) create a means to explicitly consider the detailed spatial configuration of urban environments, and (3) assure that the proposed optimization strategy is fast and can scale to large problem sizes. Multiple experiments were conducted and demonstrated the success of the proposed method. Converged results were achieved after dozens of generations within two hours. Two flight paths identified by the GA as the most and the least optimal candidates were deployed in real flight missions. The optimal flight path captured 16% more vertical points than the least optimal one, slightly higher than the 13% predicted. Both layers of parallelization were efficient: 13.1/16 for the lower layer and 3.2/4 for the upper layer. The two complementary layers of parallelization allowed flexible and efficient use of distributed computing resources to reduce the runtime. The scalability of the proposed approach was successfully demonstrated up to a data size of 460 million points. The optimization results were realistic and aligned well with the test flight results.Anh Vu VoDebra F. LaeferJonathan ByrneMDPI AGarticleLiDARpoint cloudaerial laser scanningaerial mappingflight path planningspatial optimizationScienceQENRemote Sensing, Vol 13, Iss 4437, p 4437 (2021)
institution	DOAJ
collection	DOAJ
language	EN
topic	LiDAR point cloud aerial laser scanning aerial mapping flight path planning spatial optimization Science Q
spellingShingle	LiDAR point cloud aerial laser scanning aerial mapping flight path planning spatial optimization Science Q Anh Vu Vo Debra F. Laefer Jonathan Byrne Optimizing Urban LiDAR Flight Path Planning Using a Genetic Algorithm and a Dual Parallel Computing Framework
description	This paper introduces a genetic algorithm (GA) and a beam tracing algorithm incorporated within a dual parallel computing framework to optimize urban aerial laser scanning (ALS) missions to maximize vertical façade data capture, as needed for many three-dimensional reconstruction and modeling workflows. The optimization employs a low-density point cloud from the site of interest as a spatial representation of the urban scene. The GA is suitable for LiDAR flight path optimization due to its capability of handling open-ended problems that have many solutions. However, GAs require evaluating a very large number of candidates. The use of an initial point cloud allows realistic modeling of the urban environment in the optimization at the cost of high data input volumes. To cope with the computational and data demands, a dual parallel computing framework was devised. The parallel computing framework consists of two layers of parallelization. In the upper layer, multiple evaluators work in parallel and in conjunction with a main multi-threading GA optimizer to perform GA operations and evaluate the flight paths. In the lower layer, to evaluate assigned flight paths, each evaluator distributes its data and computation to multiple executors, which can reside on multiple physical nodes of a distributed-memory computing cluster. In addition to parallelism, the data partitioning on the lower layer allows out-of-core computation. Namely, data partitions are efficiently transferred between disks and memory so that only relevant subsets of data are kept in the main memory. The objective of the proposed method is threefold: (1) search for flight paths that yield the highest numbers of vertical points, (2) create a means to explicitly consider the detailed spatial configuration of urban environments, and (3) assure that the proposed optimization strategy is fast and can scale to large problem sizes. Multiple experiments were conducted and demonstrated the success of the proposed method. Converged results were achieved after dozens of generations within two hours. Two flight paths identified by the GA as the most and the least optimal candidates were deployed in real flight missions. The optimal flight path captured 16% more vertical points than the least optimal one, slightly higher than the 13% predicted. Both layers of parallelization were efficient: 13.1/16 for the lower layer and 3.2/4 for the upper layer. The two complementary layers of parallelization allowed flexible and efficient use of distributed computing resources to reduce the runtime. The scalability of the proposed approach was successfully demonstrated up to a data size of 460 million points. The optimization results were realistic and aligned well with the test flight results.
format	article
author	Anh Vu Vo Debra F. Laefer Jonathan Byrne
author_facet	Anh Vu Vo Debra F. Laefer Jonathan Byrne
author_sort	Anh Vu Vo
title	Optimizing Urban LiDAR Flight Path Planning Using a Genetic Algorithm and a Dual Parallel Computing Framework
title_short	Optimizing Urban LiDAR Flight Path Planning Using a Genetic Algorithm and a Dual Parallel Computing Framework
title_full	Optimizing Urban LiDAR Flight Path Planning Using a Genetic Algorithm and a Dual Parallel Computing Framework
title_fullStr	Optimizing Urban LiDAR Flight Path Planning Using a Genetic Algorithm and a Dual Parallel Computing Framework
title_full_unstemmed	Optimizing Urban LiDAR Flight Path Planning Using a Genetic Algorithm and a Dual Parallel Computing Framework
title_sort	optimizing urban lidar flight path planning using a genetic algorithm and a dual parallel computing framework
publisher	MDPI AG
publishDate	2021
url	https://doaj.org/article/f60bd1d39b004301a722651d85ca3c50
work_keys_str_mv	AT anhvuvo optimizingurbanlidarflightpathplanningusingageneticalgorithmandadualparallelcomputingframework AT debraflaefer optimizingurbanlidarflightpathplanningusingageneticalgorithmandadualparallelcomputingframework AT jonathanbyrne optimizingurbanlidarflightpathplanningusingageneticalgorithmandadualparallelcomputingframework
_version_	1718431680823296000

Optimizing Urban LiDAR Flight Path Planning Using a Genetic Algorithm and a Dual Parallel Computing Framework

Ejemplares similares