Alessandro Zanardi

Last Name

Zanardi

First Name

Alessandro

ORCID

0000-0002-1341-6529

Show all metadata

Search Results

Publications 1 - 10 of 14

Urban Driving Games: Structure, Computation, and Risk
Zanardi, Alessandro (2023)
As autonomous technologies burgeon and integrate into our complex, multifaceted world, the necessity for a systematic and rational methodology for interactions among agents becomes of paramount importance. This thesis explores the pivotal role of game theory in orchestrating strategic interactions among autonomous agents on urban roads. The game-theoretic lens naturally entails the study of rational behaviors in social situations where every player's move is contingent on the anticipated countermoves of others. We identify this as a crucial step to overcome the current ``passivity'' in AVs' decision-making. The discourse is anchored in three key research questions: discerning the fundamental structures and properties embedded in urban driving interactions and their implications; addressing the computational explosion in complexity of multi-agent scenarios to maintain tractability; and defining and evaluating the riskiness of behaviors amidst the myriad of uncertainties present on the roads. The thesis unfolds by defining and exploring the inherent structures of the so-called Urban Driving Games. Along the journey, it is shown that such games are well modeled as games of self-interested agents with some high-priority communal objectives. Such a structure is sufficient to derive conditions for the existence of efficient Nash Equilibria and provide novel bounds on the Price of Anarchy. Furthermore, the thesis introduces the concept of "factorization" to tackle the computational challenges posed by the exponential increase in complexity with the number of agents in dynamic games and multi-agent planning. Factorization simplifies the computation of solutions by recognizing that the solutions of certain players can be computed independently beyond specific states over the planning horizon, thereby reducing computational burden and maintaining problem tractability. This concept instantiated at real-world intersections with 4 actors, reduces the solution time of dynamic games by 98%. Lastly, this thesis addresses the assessment of risk in road interactions. The proposed framework allows one to compare the riskiness of observed behaviors from data that do not necessarily contain rare events such as collisions. This provides a mechanism to mine critical scenarios from large datasets and facilitates the quantitative capture of risk for vehicles operating in a specific ODD. An instrument that is valuable for tech developers as well as regulatory entities and insurances.
Wormhole Learning
Zanardi, Alessandro; Zilly, Julian; Aumiller, Andreas; et al. (2019)
2019 International Conference on Robotics and Automation (ICRA)
Factorization of Dynamic Games over Spatio-Temporal Resources
Zanardi, Alessandro; Bolognani, Saverio; Censi, Andrea; et al. (2022)
2022 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)
Dynamic games feature a state-space complexity that scales superlinearly with the number of players. This makes this class of games often intractable even for a handful of players. We introduce the factorization process of dynamic games as a transformation leveraging the independence of players at equilibrium to build a leaner game graph. When applicable, it yields fewer nodes, fewer players per game node, hence much faster solutions. While for the general case checking for independence of players requires to solve the game itself, we observe that for dynamic games in the robotic domain there exist exact heuristics based on the spatio-temporal occupancy of the individual players. We validate our findings in realistic autonomous driving scenarios showing that already for a 4-player intersection we have a reduction of game nodes and solving time close to 99%.
A benchmark study on the model-based estimation of the go-kart side-slip angle
D’Inverno, M.; Arricale, Vincenzo M.; Zanardi, Alessandro; et al. (2021)
Journal of Physics: Conference Series
Nowadays, the active safety systems that control the dynamics of passenger cars usually rely on real-time monitoring of vehicle side-slip angle (VSA). The VSA can’t be measured directly on the production vehicles since it requires the employment of high-end and expensive instrumentation. To realiably overcome the VSA estimation problem, different model-based techniques can be adopted. The aim of this work is to compare the performance of different model-based state estimators, evaluating both the estimation accuracy and the computational cost, required by each algorithm. To this purpose Extended Kalman Filters, Unscented Kalman Filters and Particle Filters have been implemented for the vehicle system under analysis. The physical representation of the process is represented by a single-track vehicle model adopting a simplified Pacejka tyre model. The results numerical results are then compared to the experimental data acquired within a specifically designed testing campaign, able to explore the entire vehicle dynamic range. To this aim an electric go-kart has been employed as a vehicle, equipped with steering wheel encoder, wheels angular speed encoder and IMU, while an S-motion has been adopted for the measurement of the experimental VSA quantity.
Posetal Games: Efficiency, Existence, and Refinement of Equilibria in Games With Prioritized Metrics
Zanardi, Alessandro; Zardini, Gioele; Srinivasan, Sirish; et al. (2022)
IEEE Robotics and Automation Letters
Modern applications require robots to comply with multiple, often conflicting rules and to interact with the other agents. We present Posetal Games as a class of games in which each player expresses a preference over the outcomes via a partially ordered set of metrics. This allows one to combine hierarchical priorities of each player with the interactive nature of the environment. By contextualizing standard game theoretical notions, we provide two sufficient conditions on the preference of the players to prove existence of pure Nash Equilibria in finite action sets. Moreover, we define formal operations on the preference structures and link them to a refinement of the game solutions, showing how the set of equilibria can be systematically shrunk. The presented results are showcased in a driving game where autonomous vehicles select from a finite set of trajectories. The results demonstrate the interpretability of results in terms of minimum-rank-violation for each player.
Game Theoretical Motion Planning
Zanardi, Alessandro; Bolognani, Saverio; Censi, Andrea; et al. (2021)
The scope of this manuscript is to ease the initial steps for a reader interested in modeling the strategic nature of motion planning problems in a multi-agent environment. Historically, game theory has been devoted to studying rational decision-making in numerous fields: social science, economics, system science, logic, computer science, and many more. Today, as robots leave the factory floors for a more complex world, we do believe that many of the game theoretical concepts are well suited to capture the dynamic and interactive nature of multi-agent motion planning. The promise (and hope) is that explicitly taking into account the others' decision making in its own, endows standard techniques with a richer descriptive power. If this promise holds true, a better decision making for our robots will facilitate a seamless integration in our society.
Image Representation of a City and Its Taxi Fleet for End-To-End Learning of Rebalancing Policies
Gächter, Joel; Zanardi, Alessandro; Ruch, Claudio; et al. (2021)
2021 IEEE International Conference on Robotics and Automation (ICRA)
In recent years, mobility on demand has experienced a major revival due to various ride-hailing companies entering the market. Competing in this field requires an efficient operation. Therefore, the applied policy, which cares for vehicle-to-customer assignment and vehicle repositioning, has to achieve good customer service and minimize cost while trying to keep the impact on the environment as low as possible. A promising approach is to coordinate the control of the entire fleet, which is foreseen to become even easier with the possibility of autonomous vehicles in mind. Anticipating future demand requires a good understanding of the spatiotemporal distributions of request origins and destinations, and the resulting imbalance between vehicle demand and availability. This results from a multitude of topological, demographic, and social effects, which are almost impossible to sufficiently capture in a handcrafted model of reasonable complexity. This can be circumvented by leveraging machine learning approaches. In this paper, an image-like representation of the city and its fleet's state is introduced. It is comprehensive and intuitive to use as input to convolutional neural networks, which in the past have already been proven to capture spatial relationships very well. This allows operating on realistic, full-sized traffic networks without greatly increasing the number of parameters the neural network has to learn and, hence, keeps the training effort low. Additionally, this state is combined with a similarly constructed repositioning action, reflecting a 2D distribution of a well-performing operational policy. This approach allows replacement of complex, handcrafted mathematical models by a single, compact, auto-encoder-like neural network.
Game-theoretic Energy Management Strategies With Interacting Agents in Formula 1
Fieni, Giona; Neumann, Marc-Philippe; Zanardi, Alessandro; et al. (2025)
IEEE Transactions on Vehicular Technology
This paper presents an interaction-aware energy management optimization framework for Formula 1 racing. The scenario considered involves two agents and a drag reduction model. Strategic interactions between the agents are captured by a Stackelberg game in the form of a bilevel program. To address the computational challenges associated with bilevel optimization, the problem is reformulated as a single-level nonlinear program employing the Karush-Kuhn-Tucker conditions. The proposed framework contributes towards the development of new energy management and allocation strategies, caused by the presence of another agent. For instance, it provides valuable insights on how to redistribute the energy in order to optimally exploit the wake effect, showcasing a notable difference with the behavior studied in previous works. Robust energy allocations can be identified to reduce the lap time loss associated with unexpected choices of the other agent. It allows to recognize the boundary conditions for the interaction to become relevant, impacting the system’s behavior, and to assess if overtaking is possible and beneficial. Overall, the framework provides a comprehensive approach for a two-agent Formula 1 racing problem with strategic interactions, offering physically intuitive and practical results.
How Bad is Selfish Driving? Bounding the Inefficiency of Equilibria in Urban Driving Games
Zanardi, Alessandro; Sessa, Pier Giuseppe; Käslin, Nando; et al. (2023)
IEEE Robotics and Automation Letters
We consider the interaction among agents engaging in a driving task and we model it as general-sum game. This class of games exhibits a plurality of different equilibria posing the issue of equilibrium selection. While selecting the most efficient equilibrium (in term of social cost) is often impractical from a computational standpoint, in this work we study the (in)efficiency of any equilibrium players might agree to play. More specifically, we bound the equilibrium inefficiency by modeling driving games as particular type of congestion games over spatio-temporal resources. We obtain novel guarantees that refine existing bounds on the Price of Anarchy (PoA) as a function of problem-dependent game parameters. For instance, the relative trade-off between proximity costs and personal objectives such as comfort and progress. Although the obtained guarantees concern open-loop trajectories, we observe efficient equilibria even when agents employ closed-loop policies trained via decentralized multi-agent reinforcement learning.
Factorization of Multi-Agent Sampling-Based Motion Planning
Zanardi, Alessandro; Zullo, Pietro; Censi, Andrea; et al. (2023)
2023 62nd IEEE Conference on Decision and Control (CDC)
Modern robotics often involves multiple embodied agents operating within a shared environment. Path planning in these cases is considerably more challenging than in single-agent scenarios. Although standard Sampling-based Algorithms (SBAs) can be used to search for solutions in the robots' joint space, this approach quickly becomes computationally intractable as the number of agents increases. To address this issue, we integrate the concept of factorization into sampling-based algorithms, which requires only minimal modifications to existing methods. During the search for a solution, we can decouple (i.e., factorize) different subsets of agents into independent lower-dimensional search spaces once we certify that their future solutions will be independent of each other using a factorization heuristic. Consequently, we progressively construct a lean hypergraph where certain (hyper-)edges split the agents to independent subgraphs. In the best case, this approach can reduce the growth in dimensionality of the search space from exponential to linear in the number of agents. On average, fewer samples are needed to find high-quality solutions while preserving the optimality, completeness, and anytime properties of SBAs. We present a general implementation of a factorized SBA, derive an analytical gain in terms of sample complexity for PRM*, and showcase empirical results for RRG.

Publications 1 - 10 of 14

Alessandro Zanardi

Last Name

First Name

ORCID

Organisational unit

Filters

Search Results