The determination of the computational complexity of multi-agent pathfinding on directed graphs has been an open problem for many years. For undirected graphs, solvability can be decided in polynomial time, as has been shown already in the eighties. Further, recently it has been shown that a special case on directed graphs is solvable in polynomial time. In this paper, we show that the problem is NP-hard in the general case. In addition, some upper bounds are proven.

November 13, 2019 Abstract Collision avoidance is one of the most primary problems in the decentralized multiagent navigation: while the agents are moving towards their own targets, attentions should be paid to avoid the collisions with the others. In this paper, we introduced the concept of the local action cell, which provides for each agent a set of velocities that are safe to perform. Consequently, as long as the local action cells are updated on time and each agent selects its motion within the corresponding cell, there should be no collision caused. Furthermore, we coupled the local action cell with an adaptive learning framework, in which the performance of selected motions are evaluated and used as the references for making decisions in the following updates. The efficiency of the proposed approaches were demonstrated through the experiments for three commonly considered scenarios, where the comparisons have been made with several well studied strategies. 1 Introduction Collision-free navigation is a fundamental and important problem in the design of the multiagent systems, which are widely applied in the fields such as robots control and traffic engineering.

Keep it Consistent: T opic-A ware Storytelling from an Image Stream via Iterative Multi-agent Communication Ruize Wang 1, Zhongyu Wei 2, Piji Li 3, Haijun Shan 4, Ji Zhang 4, Qi Zhang 5, Xuanjing Huang 5 1 Academy for Engineering and Technology, Fudan University, China 2 School of Data Science, Fudan University, China 3 Tencent AI Lab, China 4 Zhejiang Lab, China 5 School of Computer Science, Fudan University, China { rzwang18,zywei,qz,xjhuang} @fudan.edu.cn; Abstract Visual storytelling aims to generate a narrative paragraph from a sequence of images automatically. Existing approaches construct text description independently for each image and roughly concatenate them as a story, which leads to the problem of generating semantically incoherent content. In this paper, we proposed a new way for visual storytelling by introducing a topic description task to detect the global semantic context of an image stream. A story is then constructed with the guidance of the topic description. In order to combine the two generation tasks, we propose a multi-agent communication framework that regards the topic description generator and the story generator as two agents and learn them simultaneously via iterative updating mechanism. We validate our approach on VIST, where quantitative results, ablations, and human evaluation demonstrate our method's good ability in generating stories with higher quality compared to state-of-the-art methods. 1 Introduction Image-to-text generation is an important topic in artificial intelligence (AI) which connects computer vision (CV) and natural language processing (NLP). Popular tasks include image captioning (Karpathy and Fei-Fei 2015; Ren et al. 2017; Vinyals et al. 2017) and question answering (Antol et al. 2015; Y u et al. 2017; Fan et al. 2018a; Fan et al. 2018b), aiming at generating a short sentence or a phrase conditioned on certain visual information. It requires the model to understand the main idea of the image stream and generate coherent sentences. Most of existing methods (Huang et al. 2016; Liu et al. 2017; Y u, Bansal, and Berg 2017; Wang et al. 2018a) for visual storytelling extend approaches of image captioning without considering topic information of the image sequence, which causes the problem of generating semantically incoherent content.

The capability to learn and adapt to changes in the driving environment is crucial for developing autonomous driving systems that are scalable beyond geo-fenced operational design domains. Deep Reinforcement Learning (RL) provides a promising and scalable framework for developing adaptive learning based solutions. Deep RL methods usually model the problem as a (Partially Observable) Markov Decision Process in which an agent acts in a stationary environment to learn an optimal behavior policy. However, driving involves complex interaction between multiple, intelligent (artificial or human) agents in a highly non-stationary environment. In this paper, we propose the use of Partially Observable Markov Games(POSG) for formulating the connected autonomous driving problems with realistic assumptions. We provide a taxonomy of multi-agent learning environments based on the nature of tasks, nature of agents and the nature of the environment to help in categorizing various autonomous driving problems that can be addressed under the proposed formulation. As our main contributions, we provide MACAD-Gym, a Multi-Agent Connected, Autonomous Driving agent learning platform for furthering research in this direction. Our MACAD-Gym platform provides an extensible set of Connected Autonomous Driving (CAD) simulation environments that enable the research and development of Deep RL- based integrated sensing, perception, planning and control algorithms for CAD systems with unlimited operational design domain under realistic, multi-agent settings. We also share the MACAD-Agents that were trained successfully using the MACAD-Gym platform to learn control policies for multiple vehicle agents in a partially observable, stop-sign controlled, 3-way urban intersection environment with raw (camera) sensor observations.

Game theory plays a fundamental factor in modern artificial intelligence(AI) solutions. Specifically, deep reinforcement learning(DRL) is an area of AI that embraced game theory as a first-class citize. From single-agent programs to complex multi-agent DRL environments, gamifying dynamics are present across the lifecycle of AI programs. The fascinating thing is that the rapid evolution of DRL has also triggered a renewed interesting in game theory research. The relationship between game theory and DRL seems trivial.

Hybrid Intelligence (HI) is the combination of human and machine intelligence, expanding human intellect instead of replacing it. HI takes human expertise and intentionality into account when making meaningful decisions and perform appropriate actions, together with ethical, legal and societal values. Our goal is to design Hybrid Intelligent systems, an approach to Artificial Intelligence that puts humans at the centre, changing the course of the ongoing AI revolution. By providing intelligent artificial collaborators that interact with people we strengthen our human capacity for learning, reasoning, decision making and problem solving. This interaction has the potential to amplify both human and machine intelligence by combining their complementary strengths.

Many studies have illustrated the import ance to accurately and precisely measure the attributes of an urban transport system. Due to the rise of Big Data and Internet of Things, there are numerous machine learning methods to measur e attributes of the transport system . Chow ( 1) provides an overview of these techniques including several appl ications like Allahviranloo and Recker ( 2) for activity pattern prediction; Cai et al. ( 3) for short - term traffic forecasting; Luque - Baena et al. ( 4) for vehicle detection; Lv et al. ( 5) for t raffic flow prediction; and Ma et al. ( 6) for network congestion prediction. However, generic machine learning techniques are not specifically designed to exploit the unique structure of urban transport networks. As a result, in recent years a theory of inverse problems (see 7) have emerged to capture network structure, dubbed " inverse transportation problems " by Xu et al. ( 8).

Collaborative decision making in multi-agent systems typically requires a predefined communication protocol among agents. Usually, agent-level observations are locally processed and information is exchanged using the predefined protocol, enabling the team to perform more efficiently than each agent operating in isolation. In this work, we consider the situation where agents, with complementary sensing modalities must co-operate to achieve a common goal/task by learning an efficient communication protocol. We frame the problem within an actor-critic scheme, where the agents learn optimal policies in a centralized fashion, while taking action in a distributed manner. We provide an interpretation of the emergent communication between the agents. We observe that the information exchanged is not just an encoding of the raw sensor data but is, rather, a specific set of directive actions that depend on the overall task. Simulation results demonstrate the interpretability of the learnt communication in a variety of tasks.

The paper investigates the second-order blameworthiness or duty to warn modality "one coalition knew how another coalition could have prevented an outcome". The main technical result is a sound and complete logical system that describes the interplay between the distributed knowledge and the duty to warn modalities.

Imagine an autonomous vehicle navigating a smoke-filled mine looking for survivors, personal belongings or any other clues to find anyone who might be alive. It identifies objects it sees and decides which paths to take first. As it reaches the limit of where it can explore, a drone sitting on the vehicle flies off to explore the hard-to-reach corners of the mine. All of this is done without any communication with the outside world. Team Explorer from Carnegie Mellon University and Oregon State University did exactly this to win the first event of the Defense Advanced Research Projects Agency (DARPA) Subterranean Challenge.