Game-Theoretic Controller Simulation for Sampling-Based Multi-Robot Motion Planning Algorithms
Open Access
- Author:
- Dillinger, Cody
- Area of Honors:
- Electrical Engineering
- Degree:
- Bachelor of Science
- Document Type:
- Thesis
- Thesis Supervisors:
- Minghui Zhu, Thesis Supervisor
Julio Urbina, Thesis Honors Advisor - Keywords:
- Robotics
Motion Planning
Control Theory
Optimization
Game Theory
Algorithms
Autonomous Systems - Abstract:
- Motion planning is the process of a robot, vehicle, or other system calculating a collision-free trajectory and the corresponding control inputs to move from a starting state to a goal state set. Motion planning is increasingly important with developments in autonomous systems within factory environments, on the roads, in the air, and within our homes. Autonomous solutions in these applications can create increased safety, saved time, or saved financial costs. In recent years, feasible motion planning has evolved into optimal motion planning for single and multi-system scenarios. This thesis expands the simulation data on the i-Nash Trajectory Algorithm, a sampling-based game-theoretic algorithm for multi-robot motion planning. It analyzes data on the computational speeds and trajectory costs; it analyzes general performance and drawbacks of the algorithm upon increasing dimensions of the state space; it integrates the algorithm design with existing techniques such as the k-d tree for nearest neighbor searching and dual tree method of RRT-connect; it provides a Python code base for further expansion of similar simulations. Computational linearity in relation to the number of robots is verified in simulation for many simulation cases. Robots are non-cooperative, and they successfully reach a Nash Equilibrium. They find dynamically feasible paths that avoid both inter-robot collisions and static obstacle collisions, and each robot chooses their path in a decentralized, iterative manner such that no individual robot could unilaterally choose a lower cost feasible trajectory from its current options. The algorithm is also anytime, meaning that once the robots converge to a Nash Equilibrium they can continue to improve upon the solution by searching for more paths. Successful simulations are shown for various static obstacle arrangements, starting states, and goal sets. This thesis explores the algorithm for a larger number of double-integrator 4-dimensional state-space disc robots.