K. Brent Venable

AAMAS Conference 2026 Conference Paper

Encoding Goals as Graphs: Structured Objectives for Scalable Cooperative Multi-Agent Reinforcement Learning

• Alessandro Amato
• Raffaele Galliera
• K. Brent Venable
• Niranjan Suri

Many cooperative multi-agent tasks are naturally defined by graphstructured objectives, where agents must collectively achieve a desired relational configuration or satisfy a set of constraints. However, current goal-conditioned multi-agent reinforcement learning (MARL) methods rarely leverage such symbolic structure to guide learning. To address this challenge, we propose Graph Embeddings for Multi-Agent Coordination (GEMA), which augments any cooperative learner with a State-Graph Encoder (SGE). The SGE is pre-trainedcontrastivelytoembedstateandgoalgraphsinashared metric space. At run time, each agent constructs the state graph, queries the SGE, and computes a similarity score to the goal embedding. This similarity serves as an intrinsic reward, providing dense feedback on task progress, and is also incorporated into each agent’s observation. Experiments on cooperative navigation, load balancing, and the StarCraft Multi-Agent Challenge (v2) show that GEMA accelerates convergence and improves team returns.

AAAI Conference 2021 Conference Paper

Modeling Voters in Multi-Winner Approval Voting

• Jaelle Scheuerman
• Jason Harman
• Nicholas Mattei
• K. Brent Venable

In many real world situations, collective decisions are made using voting and, in scenarios such as committee or board elections, employing voting rules that return multiple winners. In multi-winner approval voting (AV), an agent submits a ballot consisting of approvals for as many candidates as they wish, and winners are chosen by tallying up the votes and choosing the top-k candidates receiving the most approvals. In many scenarios, an agent may manipulate the ballot they submit in order to achieve a better outcome by voting in a way that does not reflect their true preferences. In complex and uncertain situations, agents may use heuristics instead of incurring the additional effort required to compute the manipulation which most favors them. In this paper, we examine voting behavior in single-winner and multi-winner approval voting scenarios with varying degrees of uncertainty using behavioral data obtained from Mechanical Turk. We find that people generally manipulate their vote to obtain a better outcome, but often do not identify the optimal manipulation. There are a number of predictive models of agent behavior in the social choice and psychology literature that are based on cognitively plausible heuristic strategies. We show that the existing approaches do not adequately model our real-world data. We propose a novel model that takes into account the size of the winning set and human cognitive constraints; and demonstrate that this model is more effective at capturing real-world behaviors in multi-winner approval voting scenarios.

JAIR Journal 2021 Journal Article

Reasoning with PCP-Nets

• Cristina Cornelio
• Judy Goldsmith
• Umberto Grandi
• Nicholas Mattei
• Francesca Rossi
• K. Brent Venable

We introduce PCP-nets, a formalism to model qualitative conditional preferences with probabilistic uncertainty. PCP-nets generalise CP-nets by allowing for uncertainty over the preference orderings. We define and study both optimality and dominance queries in PCP-nets, and we propose a tractable approximation of dominance which we show to be very accurate in our experimental setting. Since PCP-nets can be seen as a way to model a collection of weighted CP-nets, we also explore the use of PCP-nets in a multi-agent context, where individual agents submit CP-nets which are then aggregated into a single PCP-net. We consider various ways to perform such aggregation and we compare them via two notions of scores, based on well known voting theory concepts. Experimental results allow us to identify the aggregation method that better represents the given set of CP-nets and the most efficient dominance procedure to be used in the multi-agent context.

AAMAS Conference 2018 Conference Paper

On the Distance Between CP-nets

• Andrea Loreggia
• Nicholas Mattei
• Francesca Rossi
• K. Brent Venable

Preferences play a key role in decision making by both single individuals and/or groups. In a multi-agent context, it is also important to know how to aggregate preferences to reach a collective decision. Moreover, being able to measure the distance between the preference of two individuals is important to identify the amount of disagreement and possibly reach consensus. In this paper we define a notion of distance between CP-nets, a formalism that can compactly encode conditional qualitative preferences. We consider the Kendall-tau distance between the partial orders induced by CPnets, and we define two tractable approximations of that distance, which can be computed in time polynomial in the number of features of the CP-nets. We then perform experiments to demonstrate the quality of these approximations compared to the Kendall-tau distance. We also relate our two notions of distance to the distance rationalizability of sequential plurality voting for CP-nets.

TIST Journal 2016 Journal Article

Designing Noise-Minimal Rotorcraft Approach Trajectories

• Robert Morris
• Matthew Johnson
• K. Brent Venable
• James Lindsey

NASA and the international aviation community are investing in the development of a commercial transportation infrastructure that includes the increased use of rotorcraft, specifically helicopters and civil tilt rotors. However, there is significant concern over the impact of noise on the communities surrounding the transportation facilities. One way to address the rotorcraft noise problem is by exploiting powerful search techniques coming from artificial intelligence to design low-noise flight profiles that can be then validated though field tests. This article investigates the use of discrete heuristic search methods to design low-noise approach trajectories for rotorcraft. Our work builds on a long research tradition in trajectory optimization using either numerical methods or discrete search. Novel features of our approach include the use of a discrete search space with a resolution that can be varied, and the coupling of search with a robust simulator to evaluate candidates. The article includes a systematic comparison of different search techniques; in particular, in the experiments, we are able to do a trade study that compares complete search algorithms such as A * with faster but approximate methods such as local search.

IJCAI Conference 2011 Conference Paper

Multi-Agent Soft Constraint Aggregation via Sequential Voting

• Giorgio Dalla Pozza
• Maria Silvia Pini
• Francesca Rossi
• K. Brent Venable

We consider scenarios where several agents must aggregate their preferences over a large set of candidates with a combinatorial structure. That is, each candidate is an element of the Cartesian product of the domains of some variables. We assume agents compactly express their preferences over the candidates via soft constraints. We consider a sequential procedure that chooses one candidate by asking the agents to vote on one variable at a time. While some properties of this procedure have been already studied, here we focus on independence of irrelevant alternatives, non-dictatorship, and strategy-proofness. Also, we perform an experimental study that shows that the proposed sequential procedure yields a considerable saving in time with respect to a non-sequential approach, while the winners satisfy the agents just as well, independently of the variable ordering and of the presence of coalitions of agents.

AIJ Journal 2010 Journal Article

Elicitation strategies for soft constraint problems with missing preferences: Properties, algorithms and experimental studies

• Mirco Gelain
• Maria Silvia Pini
• Francesca Rossi
• K. Brent Venable
• Toby Walsh

We consider soft constraint problems where some of the preferences may be unspecified. This models, for example, settings where agents are distributed and have privacy issues, or where there is an ongoing preference elicitation process. In this context, we study how to find an optimal solution without having to wait for all the preferences. In particular, we define algorithms, that interleave search and preference elicitation, to find a solution which is necessarily optimal, that is, optimal no matter what the missing data will be, with the aim to ask the user to reveal as few preferences as possible. We define a combined solving and preference elicitation scheme with a large number of different instantiations, each corresponding to a concrete algorithm, which we compare experimentally. We compute both the number of elicited preferences and the user effort, which may be larger, as it contains all the preference values the user has to compute to be able to respond to the elicitation requests. While the number of elicited preferences is important when the concern is to communicate as little information as possible, the user effort measures also the hidden work the user has to do to be able to communicate the elicited preferences. Our experimental results on classical, fuzzy, weighted and temporal incomplete CSPs show that some of our algorithms are very good at finding a necessarily optimal solution while asking the user for only a very small fraction of the missing preferences. The user effort is also very small for the best algorithms.

AAMAS Conference 2009 Conference Paper

Manipulation and Gender Neutrality in Stable Marriage Procedures

• Maria Silvia Pini
• Francesca Rossi
• K. Brent Venable
• Toby Walsh

EAAI Journal 2008 Journal Article

Fuzzy conditional temporal problems: Strong and weak consistency

• Marco Falda
• Francesca Rossi
• K. Brent Venable

In real life scenarios there is often the need for modeling conditional plans where external events determine the actual execution sequence. Conditional temporal problems (CTPs) have addressed such a need by extending the classical temporal constraint models with conditions on the occurrence of some events. Preferences are also a key aspect in many temporal reasoning tasks, since they allow for modeling in a natural way desires and different satisfaction levels. In this paper, we generalize CTPs to CTPPs by adding fuzzy preferences to the temporal constraints and by allowing fuzzy thresholds for the occurrence of some events. This allows us to generalize the conditions: events are allowed to determine not only which variables are executed, but also the preferences associated to their execution time. We consider two consistency notions (that is, strong and weak) and we provide their corresponding testing algorithms. We show that the complexity of these algorithms is not larger than their classical counterparts for CTPs. We also compare CTPPs with STPPUs, another temporal framework with uncertainty and preferences, by providing a polynomial mapping from STPPUs to CTPPs which allows to identify a strong theoretical connection among the two formalisms. Finally, we describe a tool to define CTPPs and to test if they are strongly or weakly consistent.

IJCAI Conference 2007 Conference Paper

• J
• eacute; r
• ocirc; me Lang
• Maria Silvia Pini
• Francesca Rossi
• K. Brent Venable
• Toby Walsh

Preferences can be aggregated using voting rules. We consider here the family of rules which perform a sequence of pairwise majority comparisons between two candidates. The winner thus depends on the chosen sequence of comparisons, which can be represented by a binary tree. We address the difficulty of computing candidates that win for some trees, and then introduce and study the notion of fair winner, i. e. candidates who win in a balanced tree. We then consider the situation where we lack complete informations about preferences, and determine the computational complexity of computing winners in this case.

IJCAI Conference 2005 Conference Paper

Disjunctive Temporal Planning with Uncertainty

• K. Brent Venable
• Neil

Driven by planning problems with both disjunctive constraints and contingency, we define the Disjunctive Temporal Problem with Uncertainty (DTPU), an extension of the DTP that includes contingent events. Generalizing existing work on Simple Temporal Problems with Uncertainty, we divide the time-points into controllable and uncontrollable classes, and propose varying notions of controllability to replace the notion of consistency.