Abstract

Events during an emergency unfold in an unpredictable fashion which makes management of traffic duringemergencies pretty challenging. Furthermore, some vehicles would need to be evacuated faster than otherse.g., emergency vehicles or large vehicles carrying a lot more people. The Prioritized Routing Assistant forFlow of Traffic (PRAFT) enables prioritized routing during emergencies. However, the PRAFT solution doesnot compute multiple plans that can help handle better dynamic nature of emergencies. PRAFT maps theprioritized routing problem to the Minimum-Cost Maximum-Flow (MCMF) problem, hence its solution canaccommodate maximum flow while routing vehicles based on priority (maps higher priority vehicles to betterquality routes (i.e., ones with minimum cost)). We build upon the PRAFT solution to make the followingcontributions: (a) Develop a Pareto Minimum-Cost Maximum-Flow (Pareto-MCMF) algorithm which cancompute all the possible MCMF solutions. (b) Through a series of experiments performed using the wellknown traffic simulator SUMO, we could show that all the solutions generated by Pareto-MCMF indeed haveproperties similar to a MCMF solution thus providing multiple high quality options for traffic police to pickfrom depending on the situation.

Abstract

Negotiation is an important component of the interaction process among humans. With increasing automation, autonomous agents are expected to take over a lot of this interaction process. Much of automated negotiation literature focuses on agents having a static and known reservation value. In situations involving dynamic environments eg, an agent negotiating on behalf of a human regarding a meeting, agents can have a reservation value (RV) that is a function of time. This leads to a different set of challenges that may need additional reasoning about the concession behavior. In this paper, we build upon Negotiation algorithms such as ONAC (Optimal Non-Adaptive Concession) and Time-Dependent Techniques such as Boulware which work on settings where the reservation value of the agent is fixed and known. Although these algorithms can encode dynamic RV, their concession behavior and hence the …

Abstract

Automated negotiation between computational agents or between agents and humans has been a subject of active research with a focus on obtaining better quality solutions within reasonable time frames. The critical issue negotiators face during automated negotiation is that a negotiator may not always know the personality type of the opponent. Studies show that having information about the opponent improves the outcome of negotiation in general. However, unless there is prior knowledge, learning the opponent type in the limited amount of time or number of rounds in a negotiation is a difficult task. In this paper, we use a Partially Observable Markov Decision Process (POMDP) based modeling to perform better modeling of the opponent personality type. In particular, we focus on modeling the opponent into four different types to showcase that a better understanding of personality type can improve the outcome …

Abstract

Monitoring of wildlife is very important for maintaining sustainability of environment. In this paper, we pose Wildlife Monitoring as a Cooperative Target Observation (CTO) problem and propose a Multi Criteria Decision Analysis (MCDA) based algorithm named MCDA-CTO, to maximize the observation of different animal species by Unmanned Aerial Vehicles (UAVs) and to effectively handle multiple target types and the multiple criteria that arise due to targets and environmental factors, during decision making. UAVs have uncertainty in observation of targets which makes it challenging to develop a high-quality monitoring strategy. We therefore develop monitoring techniques that explicitly take actions to improve belief about the true type of targets being observed. In wildlife monitoring, it is often reasonable to assume that the observers may themselves be a subject of observation by unknown adversaries (poachers). Randomizing the observers actions can therefore help to make the target observation strategy less predictable. We then provide experimental validation which shows that the techniques we develop provide a higher (true positive/true negative) ratio along with better randomization than state of the art approaches.

Abstract

Periodic Double Auctions (PDAs) are commonly used in the real world for trading, eg in stock markets to determine stock opening prices, and energy markets to trade energy in order to balance net demand in smart grids, involving trillions of dollars in the process. A bidder, participating in such PDAs, has to plan for bids in the current auction as well as for the future auctions, which highlights the necessity of good bidding strategies. In this paper, we perform an equilibrium analysis of single unit single-shot double auctions with a certain clearing price and payment rule, which we refer to as ACPR, and find it intractable to analyze as number of participating agents increase. We further derive the best response for a bidder with complete information in a single-shot double auction with ACPR. Leveraging the theory developed for single-shot double auction and taking the PowerTAC wholesale market PDA as our testbed, we proceed by modeling the PDA of PowerTAC as an MDP. We propose a novel bidding strategy, namely MDPLCPBS. We empirically show that MDPLCPBS follows the equilibrium strategy for double auctions that we previously analyze. In addition, we benchmark our strategy against the baseline and the state-of-the-art bidding strategies for the PowerTAC wholesale market PDAs, and show that MDPLCPBS outperforms most of them consistently.

Abstract

Decentralized MDPs (Dec-MDPs) provide a rigorous framework for collaborative multi-agent sequential decisionmaking under uncertainty. However, their computational complexity limits the practical impact. To address this, we focus on a class of Dec-MDPs consisting of independent collaborating agents that are tied together through a global reward function that depends upon their entire histories of states and actions to accomplish joint tasks. To overcome scalability barrier, our main contributions are:(a) We propose a new actor-critic based Reinforcement Learning (RL) approach for event-based Dec-MDPs using successor features (SF) which is a value function representation that decouples the dynamics of the environment from the rewards;(b) We then present Dec-ESR (Decentralized Event based Successor Representation) which generalizes learning for event-based Dec-MDPs using SF within an end-to-end deep RL framework;(c) We also show that Dec-ESR allows useful transfer of information on related but different tasks, hence bootstraps the learning for faster convergence on new tasks;(d) For validation purposes, we test our approach on a large multi-agent coverage problem which models schedule coordination of agents in a real urban subway network and achieves better quality solutions than previous best approaches.

Abstract

One of the major drawbacks of RL is the low sample efficiency of the learning algorithms. In many cases domain expertise can help to mitigate this effect. Teacher-Student framework is one such paradigm, where a more experienced agent (teacher) upon being queried helps to accelerate the student’s learning by providing advice on the action to take in a given state. Real world teachers not only provide the action to take in a given state but also provide a more informative signal using the synthesis of knowledge they may have gained with experience. With this motivation, we propose a richer advising framework where the teacher augments the student’s knowledge by also providing the expected long term reward of following that action. The student can then use this value to steadily guide its Q-Network in the correct direction which can lead to a quicker convergence. To help student relive the advices received throughout its learning, we introduce an additional memory called the Advice Replay Memory (ARM). Results show that a student following our approach (a) is able to exploit the environment better, and (b) has a steeper learning curve.

Abstract

We describe the design of an autonomous electricity broker agent, VidyutVanika, the runner-up of the 2018 PowerTAC competition. The agent uses techniques from reinforcement learning, dynamic programming and other areas of machine learning to seek appropriate actions in tariff and wholesale market of the PowerTAC simulation environment. The novelty of our agent lies in defining the reward functions of suitably defined Markov decision processes (MDPs), solving these MDPs, and applying these solutions to real actions in the market. In addition, VidyutVanika uses a neural network to predict the energy consumption of various customers using weather data. The usage forecasts, so obtained, are used to place orders in day-ahead wholesale market. These forecasts also helps in reducing the balancing costs incurred by the broker.

Abstract

A smart grid is an efficient and sustainable energy system that integrates diverse generation entities, distributed storage capacity, and smart appliances and buildings. A smart grid brings new kinds of participants in the energy market served by it, whose effect on the grid can only be determined through high fidelity simulations. Power TAC offers one such simulation platform using real-world weather data and complex state-of-the-art customer models. In Power TAC, autonomous energy brokers compete to make profits across tariff, wholesale and balancing markets while maintaining the stability of the grid. In this paper, we design an autonomous broker VidyutVanika, the runner-up in the 2018 Power TAC competition. VidyutVanika relies on reinforcement learning (RL) in the tariff market and dynamic programming in the wholesale market to solve modified versions of known Markov Decision Process (MDP) formulations in the respective markets. The novelty lies in defining the reward functions for MDPs, solving these MDPs, and the application of these solutions to real actions in the market. Unlike previous participating agents, VidyutVanika uses a neural network to predict the energy consumption of various customers using weather data. We use several heuristic ideas to bridge the gap between the restricted action spaces of the MDPs and the much more extensive action space available to VidyutVanika. These heuristics allow VidyutVanika to convert near-optimal fixed tariffs to time-of-use tariffs aimed at mitigating transmission capacity fees, spread out its orders across several auctions in the wholesale market to procure energy at a lower price …

Abstract

Periodic Double Auctions (PDAs) are commonly used in the real world for trading, eg in stock markets to determine stock opening prices, and energy markets to trade energy in order to balance net demand in smart grids, involving trillions of dollars in the process. A bidder, participating in such PDAs, has to plan for bids in the current auction as well as for the future auctions, which highlights the necessity of good bidding strategies. In this paper, we perform an equilibrium analysis of single unit single-shot double auctions with a certain clearing price and payment rule, which we refer to as ACPR, and find it intractable to analyze as number of participating agents increase. We further derive the best response for a bidder with complete information in a single-shot double auction with ACPR. Leveraging the theory developed for single-shot double auction and taking the PowerTAC wholesale market PDA as our testbed, we proceed by modeling the PDA of PowerTAC as an MDP. We propose a novel bidding strategy, namely MDPLCPBS. We empirically show that MDPLCPBS follows the equilibrium strategy for double auctions that we previously analyze. In addition, we benchmark our strategy against the baseline and the state-of-the-art bidding strategies for the PowerTAC wholesale market PDAs, and show that MDPLCPBS outperforms most of them consistently.