Chia-Yin Shih

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2022-245

December 1, 2022

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2022/EECS-2022-245.pdf

Multi-agent differential games are important and useful tools for analyzing many practical problems. With the recent surge of interest in using UAVs for civil purposes, the impor- tance and urgency of developing tractable multi-agent analysis techniques that provide safety and performance guarantees is at an all-time high. Hamilton-Jacobi (HJ) reachability has successfully provided safety guarantees to small-scale systems and is flexible in terms of system dynamics. However, the exponential complexity scaling of HJ reachability prevents its direct application to large scale problems when the number of vehicles is greater than two. In this paper, we address the scalability limitations of HJ reachability by using an integer linear program that exploits the properties of HJ solutions to provide higher-level control logic. Our proposed method provides safety guarantee for three-vehicle systems – a previously intractable task for HJ reachability – without incurring significant additional computation cost. Furthermore, our method is scalable beyond three vehicles and performs better than an extension of pairwise collision avoidance to multi-vehicle collision avoidance. We demonstrate our proposed method in simulations.

Advisors: Laurent El Ghaoui

---

BibTeX citation:

@mastersthesis{Shih:EECS-2022-245,
    Author= {Shih, Chia-Yin},
    Title= {Multi-Vehicle Collision Avoidance via Hamilton-Jacobi Reachability and Integer Linear Programming},
    School= {EECS Department, University of California, Berkeley},
    Year= {2022},
    Month= {Dec},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2022/EECS-2022-245.html},
    Number= {UCB/EECS-2022-245},
    Abstract= {Multi-agent differential games are important and useful tools for analyzing many practical problems. With the recent surge of interest in using UAVs for civil purposes, the impor- tance and urgency of developing tractable multi-agent analysis techniques that provide safety and performance guarantees is at an all-time high. Hamilton-Jacobi (HJ) reachability has successfully provided safety guarantees to small-scale systems and is flexible in terms of system dynamics. However, the exponential complexity scaling of HJ reachability prevents its direct application to large scale problems when the number of vehicles is greater than two. In this paper, we address the scalability limitations of HJ reachability by using an integer linear program that exploits the properties of HJ solutions to provide higher-level control logic. Our proposed method provides safety guarantee for three-vehicle systems – a previously intractable task for HJ reachability – without incurring significant additional computation cost. Furthermore, our method is scalable beyond three vehicles and performs better than an extension of pairwise collision avoidance to multi-vehicle collision avoidance. We demonstrate our proposed method in simulations.},
}

EndNote citation:

%0 Thesis
%A Shih, Chia-Yin 
%T Multi-Vehicle Collision Avoidance via Hamilton-Jacobi Reachability and Integer Linear Programming
%I EECS Department, University of California, Berkeley
%D 2022
%8 December 1
%@ UCB/EECS-2022-245
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2022/EECS-2022-245.html
%F Shih:EECS-2022-245