New Zealand

Antonio Sgorbissa (December 1st 2006). Multi-Robot Systems and Distributed Intelligence: The ETHNOS Approach to Heterogeneity, Mobile Robotics, Moving Intelligence, Jonas Buchli, IntechOpen, DOI: 10.5772/4733. 

Ammar Mohammed, Ulrich Furbach and Frieder Stolzenburg (January 1st 2010). Multi-Robot Systems: Modeling, Specification, and Model Checking, Robot Soccer, Vladan Papi&#263;, IntechOpen, DOI: 10.5772/7349. 

Konstantinos Manousakis, Panayiotis Kolios and Georgios Ellinas (June 21st 2017). Multi-Period Attack-Aware Optical Network Planning under Demand Uncertainty, Optical Fiber and Wireless Communications, Rastislav Roka, IntechOpen, DOI: 10.5772/intechopen.68491.

When planning for multi-robot navigation tasks under uncertainty, the presence of multiple robots in the same part of the environment simultaneously can have an adverse effect on navigation performance. We refer to this effect as congestion. Existing solutions fail to model congestion at planning time, which leads to inefficient behaviour. In this presentation, I will detail how to probabilistically model congestion, presenting a structure called the probabilistic reservation table that summarises the plans of robots using continuous-time Markov chains. I will then show how this structure can be used for planning by outlining an approach that, for each robot, sequentially builds and solves a Markov decision process where the transition probabilities are obtained by querying the probabilistic reservation table.


AAMAS 2020

Multi-Robot Planning Under Uncertainty with Congestion-Aware Models

temporal uncertainty

multi-robot systems

planning under uncertainty

markov models

AAMAS is the leading scientific conference for research in autonomous agents and multi-agent systems. The AAMAS conference series was initiated in 2002 as the merging of three respected scientific meetings: the International Conference on Multi-Agent Systems (ICMAS), the International Workshop on Agent Theories, Architectures, and Languages (ATAL), and the International Conference on Autonomous Agents (AA). The aim of the joint conference is to provide a single, high-profile, internationally-respected archival forum for scientific research in the theory and practice of autonomous agents and multi-agent systems.

Browse keynotes, discussions, panels and over 300 presentations.


AAMAS is the leading scientific conference for research in autonomous agents and multi-agent systems. The AAMAS conference series was initiated in 2002 as the merging of three respected scientific meetings: the International Conference on Multi-Agent Systems (ICMAS), the International Workshop on Agent Theories, Architectures, and Languages (ATAL), and the International Conference on Autonomous Agents (AA). 

technical paper

Sparse reward problems present a challenge for reinforcement learning (RL) agents. Previous work has shown that choosing start states according to a curriculum can significantly improve the learning performance. We observe that many existing curriculum generation algorithms rely on two key components: Performance measure estimation and a start selection policy. Therefore, we propose a unifying framework for performance-based start state curricula in RL, which allows to analyze and compare the performance influence of the two key components. Furthermore, a new start state selection policy using spatial performance measure gradients is introduced. We conduct extensive empirical evaluations to compare performance-based start state curricula and investigate the influence of performance measure model choice and estimation. Benchmarking on difficult robotic navigation tasks and a high-dimensional robotic manipulation task, we demonstrate state-of-the-art performance of our novel spatial gradient curriculum.

A Performance-Based Start State Curriculum Framework for Reinforcement Learning

By a combination of well-known results in judgment aggregation, it is essentially impossible to design an aggregation rule that simultaneously satisfies two crucial requirements: to always return an outcome that is logically consistent, and to be immune to strategic manipulation. To address this dilemma, we put forward a novel notion of strategyproofness, which requires immunity to strategic manipulation only in certain well-defined situations---namely when either the truthful profile of individual judgments or the profile a would-be manipulator is trying to reach are majority-consistent. We argue that this constitutes an attractive compromise for aggregation rules one may want to use in practice, and we prove that several important rules are strategyproof in this sense. This includes, in particular, all rules belonging to the family of additive majority rules, such as the Kemeny rule and the Slater rule.


Majority-Strategyproofness in Judgment Aggregation

We consider a requester who acquires a set of data (e.g. images) that is not owned by one party. In order to collect as many data as possible, crowdsourcing mechanisms have been widely used to seek help from the crowd. However, existing mechanisms rely on third-party platforms, and the workers from these platforms are not necessarily helpful and redundant data are also not properly handled. To combat this problem, we propose a novel crowdsourcing mechanism based on social networks, where the rewards of the workers are calculated by information entropy and a modified Shapley value. This mechanism incentivizes the workers from the network to not only provide all data they have but also further invite their neighbours to offer more data. Eventually, the mechanism is able to acquire all data from all workers on the network and the requester’s cost is no more than the value of the data acquired. The experiments show that our mechanism outperforms traditional crowdsourcing mechanisms.


Collaborative Data Acquisition

Detection of anomalies and faults is a key element for long-term robot autonomy, because, together with subsequent diagnosis and recovery, allows to reach the required levels of robustness and persistency. In this paper, we propose an approach for detecting anomalous behaviors in autonomous robots starting from data collected during their routine operations. The main idea is to model the nominal (expected) behavior of a robot system using Hidden Markov Models (HMMs) and to evaluate how far the observed behavior is from the nominal one using variants of the Hellinger distance adopted for our purposes. We present a method for online anomaly detection that computes the Hellinger distance between the probability distribution of observations made in a sliding window and the corresponding nominal emission probability distribution. We also present a method for offline anomaly detection that computes a variant of the Hellinger distance between two HMMs representing nominal and observed behaviors. The use of the Hellinger distance positively impacts on both detection performance and interpretability of detected anomalies, as shown by results of experiments performed in two real-world application domains, namely, water monitoring with aquatic drones and socially assistive robots for elders living at home. In particular, our approach improves by 6% the area under the ROC curve of standard online anomaly detection methods. The capabilities of our offline method to discriminate anomalous behaviors in real-world applications are statistically proved.


Optimal Swarm Strategy for Dynamic Target Search and Tracking

In the literature we can find many kinds of modular robot that can build a wide variety of structures. In general, finding an assembly order to reach the final configuration, while respecting the insertion constraints of each kind of modular robot is a difficult process that requires system-specific tuning. 
In this article, we introduce a generic assembly planner by constrained disassembly (GAPCoD) which works with all kinds of modular robots. It outputs a directed acyclic graph where vertices are modules needing to be placed before his child nodes. This graph is obtained through the disassembly of the desired structure submitted to user chosen constraints. We detail the compiler as well as the way to choose constraints and their influence on performance. The robots embed simple path planning algorithm to reach the destination and act as decentralized agents.
Examples are provided to show the possibilities that the compiler offers with two very different robot systems and constraints.

GAPCoD: A Generic Assembly Planner by Constrained Disassembly

Over the course of a day, people often attend many appointments, like meetings or doctor’s appointments, with time and location constraints, as well as perform other tasks like stopping by the grocery store with only location constraints. Optimally scheduling the day’s agenda typically requires a high cognitive load, where people reason about all their constraints at once. An agent that aids a person in scheduling the day’s agenda can potentially reduce the stress associated with scheduling but must be able to 1) perform fast updates and 2) produce new agendas that can be readily understood by the people they are helping. In order to understand how people reason about agenda changes, we first performed a study where participants are asked to perform a series of scheduling tasks and captured their update strategy both subjectively (self-reporting) and objectively (by tracking their reasoning). Our results that show that people use spatial cues and meeting time information to reduce the rescheduling task to a more reasonable size. We then present a novel heuristic for adding tasks to agendas that targets rescheduling to clusters of appointments that are spatio-temporally near the new task. We show that this heuristic approach always finds the optimal solution, while greatly reducing rescheduling time, and performs rescheduling in a way that is similar to our participants’ strategies.

Human-Centered Decision Support for Agenda Scheduling

Previous work has shown the unreliability of existing algorithms in the batch Reinforcement Learning setting, and proposed the theoretically-grounded Safe Policy Improvement with Baseline Bootstrapping (SPIBB) fix: reproduce the baseline policy in the uncertain state-action pairs, in order to control the variance on the trained policy performance. However, in many real-world applications such as dialogue systems, pharmaceutical tests or crop management, data is collected under human supervision and the baseline remains unknown. In this paper, we apply SPIBB algorithms with a baseline estimate built from the data. We formally show safe policy improvement guarantees over the true baseline even without direct access to it. Our empirical experiments on finite and continuous states tasks support the theoretical findings. It shows little loss of performance in comparison with SPIBB when the baseline policy is given, and more importantly, drastically and significantly outperforms competing algorithms both in safe policy improvement, and in average performance.


Safe Policy Improvement with an Estimated Baseline Policy

The computational problem of Influence maximization concerns
the selection of an initial set of nodes in a social network such that,
by sending this set a certain message, its exposure through the
network will be the highest.We propose to study this problem from
a utilitarian point of view. That is, we study a model where there are
two types of messages; one that is more likely to be propagated but
gives a lower utility per user obtaining this message, and another
that is less likely to be propagated but gives a higher utility. In our
model the utility from a user that receives both messages is not
necessarily the sum of the two utilities. The goal is to maximize
the overall utility.
Using an analysis based on bisubmodular functions, we show a
greedy algorithm with a tight approximation ratio of ½. We develop
a dynamic programming based algorithm that is more suitable to
our setting and show through extensive simulations that it outperforms
the greedy algorithm.

Viral Vs. Effective: Utility Based Influence Maximization

We propose a novel technique for Active Malware Analysis (AMA) formalized as a Bayesian game between an analyzer agent and a malware agent, focusing on the decision making strategy for the analyzer. In our model, the analyzer performs an action on the system to trigger the malware into showing a malicious behavior, i.e., by activating its payload. The formalization is built upon the link between malware families and the notion of types in Bayesian games. A key point is the design of the utility function, which reflects the amount of uncertainty on the type of the adversary after the execution of an analyzer action. This allows us to devise an algorithm to play the game with the aim of minimizing the entropy of the analyzer's belief at every stage of the game in a myopic fashion. Empirical evaluation indicates that our approach results in a significant improvement both in terms of learning speed and classification score when compared to other state-of-the-art AMA techniques

Bayesian Active Malware Analysis

First price auctions are widely used in government contracts and ads auctions. In this paper, we consider the Bayesian Nash Equilibrium (BNE) in first price auctions with discrete value distributions. We study the characterization of the BNE in the first price auction and provide an algorithm to compute the BNE at the same time. Moreover, we prove the existence and the uniqueness of the BNE. Some of the previous results in the case of continuous value distributions do not apply to the case of discrete value distributions. In the meanwhile, the uniqueness result in discrete case cannot be implied by the uniqueness property in the continuous case. Unlike
in the continuous case, we do not need to solve ordinary differential equations and thus do not suffer from the solution errors therein. Compared to the method of using continuous distributions to approximate discrete ones, our experiments show that our algorithm is both faster and more accurate."


Downloads

Next from AAMAS 2020

A Performance-Based Start State Curriculum Framework for Reinforcement Learning

Similar lecture

Towards Multi-Robot Coordination under Temporal Uncertainty (Doctoral Consortium)

.css-70qvj9{display:-webkit-box;display:-webkit-flex;display:-ms-flexbox;display:flex;-webkit-align-items:center;-webkit-box-align:center;-ms-flex-align:center;align-items:center;}Downloads

Next from AAMAS 2020

A Performance-Based Start State Curriculum Framework for Reinforcement Learning

Similar lecture

Towards Multi-Robot Coordination under Temporal Uncertainty (Doctoral Consortium)

Downloads