Game Theory–Based Parameter Tuning for Energy-Efficient Path Planning on Modern UAVs

• Published in: ACM transactions on cyber-physical systems 2022-12, Vol.6 (4), p.1-29, Article 34
• Main Authors: Moolchandani, Diksha, Yadav, Kishore, Kulathunga, Geesara, Afanasyev, Ilya, Kumar, Anshul, Mazzara, Manuel, Sarangi, Smruti
• Format: Article
• Language: English
• Subjects: Computing methodologies; Evolutionary robotics; Modeling methodologies
• ISSN: 2378-962X; 2378-9638
• DOI: 10.1145/3565270

Present-day path planning algorithms for UAVs rely on various parameters that need to be tuned at runtime to be able to plan the best possible route. For example, for a sampling-based algorithm, the number of samples plays a crucial role. The dimension of the space that is being searched to plan the path, the minimum distance for extending a path in a direction, and the minimum distance that the drone should maintain with respect to obstacles while traversing the planned path are all important variables. Along with this, we have a choice of vision algorithms, their parameters, and platforms. Finding a suitable configuration for all these parameters at runtime is very challenging because we need to solve a complicated optimization problem, and that too within tens of milliseconds. The area of theoretical exploration of the optimization problems that arise in such settings is dominated by traditional approaches that use regular nonlinear optimization techniques often enhanced with AI-based techniques such as genetic algorithms. These techniques are sadly rather slow, have convergence issues, and are typically not suitable for use at runtime. In this article, we leverage recent and promising research results that propose to solve complex optimization problems by converting them into approximately equivalent game-theoretic problems. The computed equilibrium strategies can then be mapped to the optimal values of the tunable parameters. With simulation studies in virtual worlds, we show that our solutions are 5-21% better than those produced by traditional methods, and our approach is 10× faster.