Research Interests:
My research interests lie in the intersection of control theory, game theory and cyber-physical systems. My thesis was on extending routing game models to Markov Decision Processes (MDP) to study competition between ride-sharing drivers as well as several other game theoretic models in transportation. At UW, I worked on extensions of the game theory models in my thesis as well as other aspects of learning in games. I also collaborated with Prof. Behcet Ackimese and his team on trajectory planning algorithms using convex optimization.
We are working on a collection of monographs that teach linear algebra and optimization from a thoroughly geometric/spatial perspective.
Papers:
Technical Summary:
In this project, we develop a convex optimization framework that combines traditional routing games with a linear programming formulation of bipartite matching problems to solve a routing problem where agents also must be assigned between origin destination pairs. To extend this technique to large scale practical multi-agent path finding (MAPF) problems, we use a Dantzig-Wolfe style decomposition to break up grid world environments into smaller chunks, train a nonlinear model of congestion in each subregion using several types of neural networks (CNN, GCN, LSTM), and then use these nonlinear congestion models in our routing game framework.
Applications:Multi-agent pathfinding and task assignment for large scale robot distributions centers
Papers:
Master's Thesis: Kelly Ho (advisors: Dan Calderone, Lillian Ratliff)
Bipartite Matching and Routing with Congestion Costs:
A convex approach to robot task assignment and the multi-agent pathfinding problem
monograph
Decomposition and Learning Congestion For Multi-Agent Path Finding and Task Assignment Joseph Sullivan, Dan Calderone, Jake Gonzalez, Lillian Ratliff. (UNDER REVIEW) LCSS 2024
Technical Summary:
Using information from the dual variables for each subproblem, we develop a scheme for tuning problem hyperparameters to practically improve solutions to successive convex programming for trajectory optimization.
Applications:Hypersonic reentry, rocket landing, quadrotor dynamics.
Papers:Hyper-parameter Autotuning for Trajectory Planning via Successive Convex Programming Using Dual Variables LCSS 2024 (UNDER REVIEW)
Technical Summary:
Traditional population games consider only populations that are fully uniform, ie. all agents are the same. We extend this framework to situations where populations are modeled as a mass distribution (measure) over a "type space". The location of each agent (or their infinitesimal bit of mass) in the type space indicates that agent's relative preference for various options available to them. The type space has dimension equal to the options available. We consider both the one dimensional case, where all options can be compared on one axis; and the multi-dimensional case where we can model relative preferences among many options. We formulate the appropriate equilibrium concept for these population games and show how this equilibrium can be computed via a potential function. We are currently studying the dual of this potential optimization problem and it's interpretation.
Applications:This framework combines smoothly with traditional congestion game notions and we use it to model hetergeneous populations making transportation choices between disparate options such as driving, walking, biking, or taking various forms of public transit.
Papers:
Multi-Dimensional Continuous Type Population Potential Games: Primal-Dual Formulations Dan Calderone and Lillian J. Ratliff. IEEE LCSS/CDC, 2024 (under review).
A Hybrid Routing Game/Vehicle Routing Approach to Multi-Modal Transportation Choice in Chattanooga Tennesse, Dan Calderone, Agrima Khanna, Abhishek Dubey, Lillian J. Ratliff 2024 (in preparation)
Multi-Dimensional Continuous Type Population Potential Games. Dan Calderone and Lillian J. Ratliff. IEEE CDC, 2019. paper talk
External-cost continuous-type wardrop equilibria in routing games. Dan Calderone, Roy Dong, S. Shankar Sastry ITSC 2017 paper talk
Technical Summary:
Project link: example and animations
Leveraging tools from the study of linear fractional transformations and algebraic Riccati equations, a local characterization of consistent conjectural variations equilibrium is given for two player games on continuous action spaces with costs approximated by quadratic functions. Further, a discrete time dynamical system in the space of conjectures is derived and its stability properties are characterized.
Papers:Consistent Conjectural Variations Equilibrium: Characterization & Stability for a Class of Continuous Games. Dan Calderone, Ben Chasnov, Sam Burden, Lillian Ratliff. LCSS 2023 paper (arxiv)
Consistent Conjectural Variations Equilibrium: Dynamic Decompositions and Asymptotic Behavior. Dan Calderone, Ben Chasnov, Sam Burden, Lillian Ratliff. (UNDER REVIEW) LCSS 2024
Technical Summary:
We extend traditional routing game models to scenarios where agents are solving Markov Decision Processes (MDPs) as opposed to shortest path problems. These models essentially replace the shortest path of objective of agents in a routing game with a stochastic shortest path objective. Our work presents this model in both the finite and infinite horizon cases and serves as a bridge between routing games and mean-field games on graphs, bringing stochastic network transitions into the routing game framework and extending traditional routing game concepts such as price of anarchy and Braess paradox to the mean-field game setup.
Applications:Competition among ride-sharing drivers in urban areas
Competition among urban drivers looking for street parking
Papers:Markov Decision Process Routing Games. Dan Calderone and S. Shankar Sastry. ICCPS 2017. paper
Infinite-horizon average-cost Markov decision process routing games. Dan Calderone and S. Shankar Sastry. ITSC 2017 paper talk
Congestion-Aware Path Coordination Game With Markov Decision Process Dynamics. Sarah H.Q. Li, Dan Calderone, Behcet Acikmese LCSS 2023 paper
Adaptive Constraint Satisfaction for Markov Decision Process Congestion Games: Application to Transportation Networks. Sarah H.Q. Li, Yue Yu, Nico Miguel, Dan Calderone, Lillian J. Ratliff, Daniel Calderone b Lillian J. Ratliff, Behcet Acikmese, Automatica 2022. paper
Variable Demand and Multi-commodity Flow in Markovian Network Equilibrium. Yue Yu, Dan Calderone, Sarah H. Q. Li, Lillian J. Ratliff, Behcet Acıkmese Automatica 2022 paper
Sensitivity Analysis for Markov Decision Process Congestion Games. Sarah H.Q. Li, Dan Calderone, Behcet Acikmese CDC 2019 paper
Tolling for Constraint Satisfaction in Markov Decision Process Congestion Games Sarah H.Q. Li, Yue Yu, Dan Calderone, Lillian J. Ratliff, Behcet Acikmese, ACC 2019 paper
Technical Summary: Braess paradox is the (in)famous phenomena in routing games where adding roads to a congested network can actually make congestion worse due to the competitive nature of traffic flow. In this work, we provide an in-depth algebraic characterization of this network phenomena in terms of the graph incidence and Laplacian matrices. We also present a graph theoretic exposition of several classical results about Braess paradox; in particular that Braess paradox cannot occur in a series-parallel network. Our current work is extending these results to hypergraphs which covers the case of Braess paradox in MDP congestion games.
Papers
Sensitivity Analysis for Markov Decision Process Congestion Games. Sarah H. Q. Li, Dan Calderone, Lillian Ratliff, Behcet Acikmese preprint arxiv Sept 2019. paper
Technical Summary: We apply stability notions from linear system theory to study learning dynamics in two-player games with continuous action sets. We present a complete picture of when gradient play is stable (and unstable) in the scalar action case (2x2 game Jacobians). Though straightforward, these results provide much qualitative insight into learning dynamics in different types of games such as potential games, zero-sum games, etc. We then generalize some of these results to the vector action case.
Papers
Stability 1. Stability of Gradient Learning Dynamics in Continuous Games: Scalar Action Spaces Benjamin J. Chasnov, Daniel Calderone, Behcet Acikmese, Samuel A. Burden, Lillian J. Ratliff, IEEE CDC 2020 paper
Stability of Gradient Learning Dynamics in Continuous Games: Vector Action Spaces Benjamin J. Chasnov, Daniel Calderone, Behcet Acikmese, Samuel A. Burden, Lillian J. Ratliff paper
Technical Summary: We add competition for optimal parking spots to routing game models. Our model combines traditional routing game notions with queue theory to formulate a congestion game and corresponding Wardrop equilibrium notion. We then solve this potential game via the appropriate potential function.
Applications Competition among drivers for urban parking.
Papers
Understanding the impact of parking on urban mobility via routing games on queue-flow networks. D. Calderone, E. Mazumdar, L. J. Ratliff, and S. S. Sastry. IEEE CDC, 2016. paper talk