Multi-objective multigraph feature extraction for the shortest path cost prediction

As emerging urban air mobility concepts such as air taxis, on-demand aircraft, and large unmanned aerial vehicles become integrated into daily life, ensuring their smooth interaction with existing conventional airport infrastructures is imperative for achieving a sustainable civil aviation industry.

To optimise operational efficiency and energy consumption while maintaining safety in future mixed-traffic mode airport environments, researchers use aircraft trajectories to formulate airport ground movement as a search problem on a multi-objective multigraph (MOMG). Swift estimation of the shortest path costs is crucial for conducting heuristic searches for optimal paths on MOMGs, however, previous work mainly employed exact search algorithms to obtain the costs, which is computationally expensive.

A paper published in the journal Green Energy and Intelligent Transportation  in 20 January 2024 extracts MOMG features for estimating shortest path costs efficiently by regression prediction. The paper focuses on benchmark MOMGs, proposes and compares two extraction methods: a statistics-based method that summarises 22 node physical patterns from graph theory principles, and a learning-based method that utilises node embedding technique to encode graph structures into a discriminative vector space.

In the statistics-based extraction method, the paper authors adopt principal component analysis to assess the node physical patterns and uncover their individual importance for predicting shortest path costs. Regarding the learning-based extraction method, given that node embedding algorithms typically rely on single-objective simple graphs to generate embedding vectors, the paper authors introduce and compare two multigraph simplification methods: node duplication and edge trimming. Then, three regression models, multi-layer perceptron (MLP), polynomial regression (PR) and gradient boosted regression trees (GBRT), are tested to show their predicting abilities. Finally, experiments are performed on randomly generated benchmark MOMGs and show that (i) the statistics-based extraction method underperforms on characterising small distance values due to severe overestimation; (ii) A subset of essential physical patterns can achieve comparable or slightly better prediction accuracy than that based on a complete set of patterns; And (iii) the learning-based extraction method consistently outperforms the statistics-based method, while maintaining a competitive level of computational complexity.

In future efforts, the paper authors will focus on six directions: (i) the exploration of additional node physical patterns; (ii) The development of mechanism to handle the overestimation of small distances when using node physical patterns to predict shortest path costs; (iii) The fine-tuning of hyperparameters for PR and GBRT; (iv) The conduct of further research and experimentation on more regression models to evaluate their performance of predicting shortest path costs; (v) The research on hyperparameters of node embedding algorithm node2vec, which control the number of random walks generated for each node; And (vi) the application of the proposed methods to real-world airport cases, incorporating techniques to handle constraints encountered in actual operations.

###

References

Authors: Songwei Liu, Xinwei Wang, Michal Weiszer, Jun Chen*

Title of original paper: Extracting multi-objective multigraph features for the shortest path cost prediction: Statistics-based or learning-based?

Article link:https://www.sciencedirect.com/science/article/pii/S2773153723000658

Journal: Green Energy and Intelligent Transportation

DOI: 10.1016/j.geits.2023.100129

Affiliation: School of Engineering and Materials Science, Queen Mary University of London, Mile End Road, London E1 4NS, United Kingdom