A computationally efficient approach to decentralized routing of swarms via a family of pre-fractal curves
| Autor: | Milad Farzad, Siamak G. Faal, Shadi Tasdighi Kalat |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
010101 applied mathematics
Mathematical optimization Optimization problem Computer science Bounded function Swarm behaviour Interval (mathematics) 0101 mathematics Routing (electronic design automation) Representation (mathematics) 01 natural sciences Infimum and supremum Domain (software engineering) |
| Zdroj: | ACC |
| DOI: | 10.23919/acc.2019.8814996 |
| Popis: | In this paper, we introduce a method to reduce the computations required to solve a combinatorial optimization problem for a swarm system. In particular, we focus on finding a solution to assignment problems where the agents are required to visit a number of targets periodically while minimizing a cost functional. Our methodology utilizes a family of pre-fractal curves as a mapping from a bounded two dimensional domain to a bounded real interval. Using this map, we obtain a one dimensional representation of the optimization problems that yields a near-optimal solution in a swarm with 500 agents in less than 0.2 seconds on a regular desktop computer. Moreover, we compute the least upper bound of the optimality, which is defined as the ratio of the cost of the obtained solution to the optimal cost. The effectiveness and efficiency of the method is evaluated through more than 100 simulations with different number of agents and targets. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|