Consider a large piece of land that is to be split in a fair manner among several farmers, who all have an equal entitlement to a share of this land. They all have different plans for their allotted pieces – growing a variety of crops, using the land as a pasture, or putting up a solar farm – so each of them has their own preferences over the land, depending on the type of soil, incline, access to water, etc. There may also be constraints on the shape of each individual piece: e.g., it is probably a bad idea to partition the land into pieces that are 800m long and 2m wide, even if such a partition is perfectly fair. The problem of allocating the land in a fair manner under these constraints has been considered in prior work (Segal-Halevi et al., Fair and square: Cake-cutting in two dimensions, Journal of Mathematical Economics 2017; Segal-Halevi et al., Envy-free division of land, Mathematics of Operations Research 2020), for two classic notions of fairness, namely, proportionality (if there are N agents, each of them should value their piece at least as highly as V/N, where V is the value they assign to the entire piece of land) and envy-freeness (no agent considers another agent's piece to be more valuable than their own). In our work, we consider a variant of this problem where, in addition to geometric constraints on the shapes of the individual pieces, we require the pieces to be separated: there is a separation parameter s such that any two pieces belonging to two different agents have to be at distance at least s from each other. Such a constraint is motivated by practical considerations, e.g., providing access or avoiding cross-pollination; if the "land" to be divided is, say, an exhibition hall or a market square, the separation requirement can be used to capture social distancing constraints.

Bomberland is a new 1v1 AI competition developed by Coder One. It features a multi-agent adversarial environment inspired by the classic console game, Bomberman. Your task is to program an intelligent agent navigating a 2D grid world. Your agent controls a team of units collecting powerups and placing explosives, with the ultimate goal of taking your opponent down. Bomberland is a challenging problem for out-of-the-box machine learning algorithms.

While there has been an increasing focus on the use of game theoretic models for autonomous driving, empirical evidence shows that there are still open questions around dealing with the challenges of common knowledge assumptions as well as modeling bounded rationality. To address some of these practical challenges, we develop a framework of generalized dynamic cognitive hierarchy for both modelling naturalistic human driving behavior as well as behavior planning for autonomous vehicles (AV). This framework is built upon a rich model of level-0 behavior through the use of automata strategies, an interpretable notion of bounded rationality through safety and maneuver satisficing, and a robust response for planning. Based on evaluation on two large naturalistic datasets as well as simulation of critical traffic scenarios, we show that i) automata strategies are well suited for level-0 behavior in a dynamic level-k framework, and ii) the proposed robust response to a heterogeneous population of strategic and non-strategic reasoners can be an effective approach for game theoretic planning in AV.

Despite the surprising power of many modern AI systems that often learn their own representations, there is significant discontent about their inscrutability and the attendant problems in their ability to interact with humans. While alternatives such as neuro-symbolic approaches have been proposed, there is a lack of consensus on what they are about. There are often two independent motivations (i) symbols as a lingua franca for human-AI interaction and (ii) symbols as (system-produced) abstractions use in its internal reasoning. The jury is still out on whether AI systems will need to use symbols in their internal reasoning to achieve general intelligence capabilities. Whatever the answer there is, the need for (human-understandable) symbols in human-AI interaction seems quite compelling. Symbols, like emotions, may well not be sine qua non for intelligence per se, but they will be crucial for AI systems to interact with us humans--as we can neither turn off our emotions nor get by without our symbols. In particular, in many human-designed domains, humans would be interested in providing explicit (symbolic) knowledge and advice--and expect machine explanations in kind. This alone requires AI systems to at least do their I/O in symbolic terms. In this blue sky paper, we argue this point of view, and discuss research directions that need to be pursued to allow for this type of human-AI interaction.

A particular challenge for both autonomous and human driving is dealing with risk associated with dynamic occlusion, i.e., occlusion caused by other vehicles in traffic. Based on the theory of hypergames, we develop a novel multi-agent dynamic occlusion risk (DOR) measure for assessing situational risk in dynamic occlusion scenarios. Furthermore, we present a white-box, scenario-based, accelerated safety validation framework for assessing safety of strategic planners in AV. Based on evaluation over a large naturalistic database, our proposed validation method achieves a 4000% speedup compared to direct validation on naturalistic data, a more diverse coverage, and ability to generalize beyond the dataset and generate commonly observed dynamic occlusion crashes in traffic in an automated manner.

In visual semantic navigation, the robot navigates to a target object with egocentric visual observations and the class label of the target is given. It is a meaningful task inspiring a surge of relevant research. However, most of the existing models are only effective for single-agent navigation, and a single agent has low efficiency and poor fault tolerance when completing more complicated tasks. Multi-agent collaboration can improve the efficiency and has strong application potentials. In this paper, we propose the multi-agent visual semantic navigation, in which multiple agents collaborate with others to find multiple target objects. It is a challenging task that requires agents to learn reasonable collaboration strategies to perform efficient exploration under the restrictions of communication bandwidth. We develop a hierarchical decision framework based on semantic mapping, scene prior knowledge, and communication mechanism to solve this task. The results of testing experiments in unseen scenes with both known objects and unknown objects illustrate the higher accuracy and efficiency of the proposed model compared with the single-agent model.

Effective latent representations need to capture abstract features of the external world. We hypothesise that the necessity for a group of agents to reconcile their subjective interpretations of a shared environment state is an essential factor influencing this property. To test this hypothesis, we propose an architecture where individual agents in a population receive different observations of the same underlying state and learn latent representations that they communicate to each other. We highlight a fundamental link between emergent communication and representation learning: the role of language as a cognitive tool and the opportunities conferred by subjectivity, an inherent property of most multi-agent systems. We present a minimal architecture comprised of a population of autoencoders, where we define loss functions, capturing different aspects of effective communication, and examine their effect on the learned representations. We show that our proposed architecture allows the emergence of aligned representations. The subjectivity introduced by presenting agents with distinct perspectives of the environment state contributes to learning abstract representations that outperform those learned by both a single autoencoder and a population of autoencoders, presented with identical perspectives. Altogether, our results demonstrate how communication from subjective perspectives can lead to the acquisition of more abstract representations in multi-agent systems, opening promising perspectives for future research at the intersection of representation learning and emergent communication.

Recently, a boxology (graphical language) with design patterns for hybrid AI was proposed, combining symbolic and sub-symbolic learning and reasoning. In this paper, we extend this boxology with actors and their interactions. The main contributions of this paper are: 1) an extension of the taxonomy to describe distributed hybrid AI systems with actors and interactions; and 2) showing examples using a few design patterns relevant in multi-agent systems and human-agent interaction in general and, specifically, in the manufacturing domain.

Language models (LMs) are sentence-completion engines trained on massive corpora. LMs have emerged as a significant breakthrough in natural-language processing, providing capabilities that go far beyond sentence completion including question answering, summarization, and natural-language inference. While many of these capabilities have potential application to cognitive systems, exploiting language models as a source of task knowledge, especially for task learning, offers significant, near-term benefits. We introduce language models and the various tasks to which they have been applied and then review methods of knowledge extraction from language models. The resulting analysis outlines both the challenges and opportunities for using language models as a new knowledge source for cognitive systems. It also identifies possible ways to improve knowledge extraction from language models using the capabilities provided by cognitive systems. Central to success will be the ability of a cognitive agent to itself learn an abstract model of the knowledge implicit in the LM as well as methods to extract high-quality knowledge effectively and efficiently. To illustrate, we introduce a hypothetical robot agent and describe how language models could extend its task knowledge and improve its performance and the kinds of knowledge and methods the agent can use to exploit the knowledge within a language model.

In the assignment problem, items must be assigned to agents who have unit demands, based on agents' ordinal preferences. Often the goal is to design a mechanism that is both fair and efficient. In this paper, we first prove that, unfortunately, the desirable efficiency notions rank-maximality, ex-post favoring-higher-ranks, and ex-ante favoring-higher-ranks, which aim to allocate each item to agents who rank it highest over all the items, are incompatible with the desirable fairness notions strong equal treatment of equals (SETE) and sd-weak-envy-freeness (sd-WEF) simultaneously. In light of this, we propose novel properties of efficiency based on a subtly different notion to favoring higher ranks, by favoring "eagerness" for remaining items and aiming to guarantee that each item is allocated to agents who rank it highest among remaining items. We prove that the eager Boston mechanism satisfies ep-FERI and sd-WSP, and that the uniform probabilistic respecting eagerness mechanism satisfies ea-FERI. We also prove that both mechanisms satisfy SETE and sd-WEF, and show that no mechanism can satisfy stronger versions of envyfreeness and strategyproofness while simultaneously maintaining SETE, and either ep-FERI or ea-FERI. X. Guo and Y. Cao are with Key Laboratory of High Confidence Software Technologies (MOE), Department of Computer Science and Technology, Peking University, Beijing 100871, China (e-mail: guoxiaoxi@pku.edu.cn; S. Sikdar is with Department of Computer Science, Binghamton University (email: ssikdar@binghamton.edu). H. Wang is with School of Computer Science and Cyber Engineering, Guangzhou University, China, and Key Laboratory of High Confidence Software Technologies (MOE), Department of Computer Science and Technology, Peking University, Beijing 100871, China (whpxhy@pku.edu.cn). This serves as a useful model for a variety of problems where the items may be either indivisible such as houses (Shapley and Scarf, 1974), dormitory rooms (Chen and Sönmez, 2002), and school choice without priorities (Miralles, 2009); or divisible such as natural resources like land and water (Segal-Halevi, 2016), and computational resources in cloud computing (Ghodsi et al., 2011, 2012; Grandl et al., 2014).