WORK PACKAGE 4
Key applications of geometric networks: network-based algorithms for unmanned aerial vehicles and music information retrieval Details
In Work Packages 1 - 3, the main focus was mostly theoretical, even though all the topics that will be studied are highly applicable. However, it is also a goal of this project to bring part of the developed theories on geometric networks close to the applications domains. Two concrete domains have been chosen for this: algorithms for unmanned aerial vehicles (UAVs), and music information retrieval (MIR).
One of the main challenges in the development of multi-UAVs systems is path planning [ADCPO13, B00]. For instance, for surveillance missions in applications in oceanography, forest fire prevention or oil spill monitoring, teams of autonomous robots can monitor changing environments. This requires robots to consistently traverse the environment in trajectories designed to optimize certain performance criteria, such as quality or frequency of sensor measurements [AADVMO13, AADVMO14, CADAMO14, CMKB04, PDB12, RCH07]. Many problems related to cooperative UAVs rely on geometric networks when a discretization of the problem is considered. We illustrate this with two concrete examples: (1) Search problems in continuous regions can be discretized by sampling the region of interest at locations with high target probability, reducing the problem to optimization in a finite network [MSW13, SSR12]. (2) The synchronization problem for information exchange [DCBLMO15] consists in, given the planned trajectories of a set of UAVs, scheduling each vehicle’s movement along its trajectories so that every pair of neighboring vehicles is guaranteed to be close enough at some point in time, allowing to synchronize information with all other vehicles. It can be showed that the system can be synchronized if and only if the communication graph is bipartite. It follows that the use of geometric networks to represent different scenarios like the ones above implies that many domain-specific questions can be naturally translated into geometric graph problems, and vice-versa.
Music information retrieval (MIR) focuses on tools that extract intrinsic properties from musical audio, related to pitch, rhythm, timbre, harmony, etc. Graphs in MIR have been used for indexing music collections [PVDWV07], representation of pitch class sequences and other relevant music features [PT08] or acoustic-based music recommender systems [BTCWWZH10]. Most advances in audio-based feature extraction and classification have focused on Western classical and popular music. However, they do not perform well in ethnic music, as this music does not always correspond to the Western concepts [CLML10]. For instance, the computational analysis of flamenco music poses a variety of challenging mathematical and algorithmic problems [GDGM14, ACDFON15, BCDFP16]. The following three research lines will be particularly important in this project: 1) Graph clustering for melody categorization. Related studies have evaluated approaches to automatic melody categorization based on their performance in a supervised k-NN-classification task [KT10, DR14, GMGD16]. However, when using an unsupervised approach we have to compute a similarity graph from a similarity matrix, and sophisticated clustering algorithms tailored to the characteristics of melodic similarity are needed [KPMD15, CVD04]. 2) Phylogenetic graphs. Phylogenetic tree algorithms are useful to map pairwise similarities computed in a dataset to a twodimensional space. Consequently, phylogenetic analysis is a powerful tool to gain deeper understanding of musicological concepts, such as the evolution of styles. Computing “ancestral” nodes in phylogenetic graphs in a challenging task both in bioinformatics and music [CDP15]. 3) Music information visualization and retrieval. For enhancing the user experience in automatic music recommendation and contentbased retrieval, data visualization plays an important role: graphical user interfaces allow content-based browsing and exploring of large collections in an intuitive manner. Consequently, the development of algorithms mapping high-dimensional relations between data instances to two- and three-dimensional spaces is an important open challenge.
