Efficient Generation of Grids and Traversal Graphs in Compositional Spaces towards Exploration and Path Planning
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916467944980480 |
|---|---|
| author | Krajewski, Adam M. Beese, Allison M. Reinhart, Wesley F. Liu, Zi-Kui |
| author_facet | Krajewski, Adam M. Beese, Allison M. Reinhart, Wesley F. Liu, Zi-Kui |
| contents | Many disciplines of science and engineering deal with problems related to compositions, ranging from chemical compositions in materials science to portfolio compositions in economics. They exist in non-Euclidean simplex spaces, causing many standard tools to be incorrect or inefficient, which is significant in combinatorically or structurally challenging spaces exemplified by Compositionally Complex Materials (CCMs) and Functionally Graded Materials (FGMs). Here, we explore them conceptually in terms of problem spaces and quantitatively in terms of computational feasibility.
This work implements several essential methods specific to the compositional (simplex) spaces through a high-performance open-source library nimplex. Most significantly, we derive and implement an algorithm for constructing a novel n-dimensional simplex graph data structure, which contains all discretized compositions and all possible neighbor-to-neighbor transitions as pointer arrays. Critically, no distance or neighborhood calculations are performed, instead leveraging pure combinatorics and the ordering in procedurally generated simplex grids, keeping the algorithm $\mathcal{O}(N)$, so that graphs with billions of transitions take seconds to construct on a laptop. Furthermore, we demonstrate how such graph representations can be combined to express path-planning problem spaces and to incorporate prior knowledge while keeping the problem space homogeneous. This allows for efficient deployment of existing high-performance gradient descent, graph traversal search, and other path optimization algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_03528 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Efficient Generation of Grids and Traversal Graphs in Compositional Spaces towards Exploration and Path Planning Krajewski, Adam M. Beese, Allison M. Reinhart, Wesley F. Liu, Zi-Kui Materials Science Data Analysis, Statistics and Probability E.1; F.2; G.2.1; I.1.2; J.2; J.6 Many disciplines of science and engineering deal with problems related to compositions, ranging from chemical compositions in materials science to portfolio compositions in economics. They exist in non-Euclidean simplex spaces, causing many standard tools to be incorrect or inefficient, which is significant in combinatorically or structurally challenging spaces exemplified by Compositionally Complex Materials (CCMs) and Functionally Graded Materials (FGMs). Here, we explore them conceptually in terms of problem spaces and quantitatively in terms of computational feasibility. This work implements several essential methods specific to the compositional (simplex) spaces through a high-performance open-source library nimplex. Most significantly, we derive and implement an algorithm for constructing a novel n-dimensional simplex graph data structure, which contains all discretized compositions and all possible neighbor-to-neighbor transitions as pointer arrays. Critically, no distance or neighborhood calculations are performed, instead leveraging pure combinatorics and the ordering in procedurally generated simplex grids, keeping the algorithm $\mathcal{O}(N)$, so that graphs with billions of transitions take seconds to construct on a laptop. Furthermore, we demonstrate how such graph representations can be combined to express path-planning problem spaces and to incorporate prior knowledge while keeping the problem space homogeneous. This allows for efficient deployment of existing high-performance gradient descent, graph traversal search, and other path optimization algorithms. |
| title | Efficient Generation of Grids and Traversal Graphs in Compositional Spaces towards Exploration and Path Planning |
| topic | Materials Science Data Analysis, Statistics and Probability E.1; F.2; G.2.1; I.1.2; J.2; J.6 |
| url | https://arxiv.org/abs/2402.03528 |