Francesco Amigoni

AAMAS Conference 2026 Conference Paper

Multi-Agent Pickup and Delivery with Heterogeneous Agents

• Benedetta Flammini
• Francesco Amigoni
• Bruno Lacerda

The Multi-Agent Pickup and Delivery (MAPD) problem involves a team of agents that plan collision-free paths to perform tasks, which appear over time, consisting of picking up and delivering items. Usually, agentsareconsideredhomogeneous. Forexample, an agent can move everywhere in the environment and can complete any task. In this paper, we study the MAPD problem in a setting with heterogeneous agents, where different classes of agents have distinct capabilities and can operate in different areas of the environment. Unlike classical MAPD formulations, our setting requires cooperation across agent classes to complete tasks, possibly spanning multiple operable zones, which requires agents of different classes to exchange items through handovers at frontier locations betweentheiroperablezones. Toaddressthischallenge, wepropose atwo-levelplanningframeworkthatfirstcomputeshigh-levelpaths for items across zones, determining where exchanges should occur, and then determines which agents will transport items along these high-level paths while generating collision-free low-level paths for each transporting agent. This approach coordinates item transfers and agent movements while respecting their heterogeneous capabilities. We evaluate our approach in simulated environments inspired by practical real-world scenarios.

AAMAS Conference 2025 Conference Paper

Multi-Agent Pickup and Delivery with Batteries

• Marcello Bavaro
• Francesco Amigoni

In Multi-Agent Pickup and Delivery (MAPD), a group of moving agents plan coordinated paths to execute pickup and delivery tasks appearing online in a known environment. The typical application of MAPD is in warehouses, where the agents are mobile robots powered by batteries. Current research on MAPD does not fully take into account the need for the agents to recharge their batteries when planning paths. In this paper, we study a variant of the MAPD problem, called MAPD-b, which considers battery consumption and charging stations, and we propose an algorithm to solve it.

ECAI Conference 2025 Conference Paper

Supporting Stability Analysis of Aircraft Flight Control Laws

• Luca Bonalumi
• Carmelo Raciti
• Francesco Amigoni

Traditionally, flight control laws are verified, among other analyses, by demonstrating robust stability in the flight envelope (namely, in the region of operation of aircraft). Stability requirements are given in terms of gain and phase margins. These margins give an indication of the robustness of the control laws in presence of unmodeled effects and uncertainty. This paper proposes an AI-based approach to support the stability analysis tasks by identifying a structured partition of the flight envelope, where each region of the partition exhibits locally homogeneous stability characteristics. Building on recursive partitioning methods from Machine Learning, the proposed approach leverages the interpretability of tree-based models to facilitate human expert validation and usage of the obtained results.

AAMAS Conference 2024 Conference Paper

A Distributed Approach for Fault Detection in Swarms of Robots

• Alessandro Carminati
• Davide Azzalini
• Simone Vantini
• Francesco Amigoni

Swarm Robotic Systems (SRSs) are multi-robot systems usually composed of relatively simple robots. Local decisions and communication between robots allow for the emergence of complex behaviors of the entire SRS. The distributed nature of the SRSs enables their use in many real-world applications. However, despite the common belief that these systems are inherently robust and fault tolerant, it has been shown that even a few faulty robots could considerably hinder the performance of the entire SRS. In this paper, we propose a distributed fault detection approach that exploits machine learning classifiers to allow each robot of a SRS to detect faults in other robots and/or in itself. The proposed fault detection approach is data-driven, requiring a reduced amount of explicit domain knowledge, and is based on data that can be easily collected by common swarm robotics platforms. We test the proposed fault detection approach in simulation and analyze the results using non-parametric statistical tests. Our extensive experimental campaign shows that our approach has good performance and is robust regardless of the ratio of faulty robots in the SRS.

AAMAS Conference 2024 Conference Paper

Preventing Deadlocks for Multi-Agent Pickup and Delivery in Dynamic Environments

• Benedetta Flammini
• Davide Azzalini
• Francesco Amigoni

The Multi-Agent Pickup and Delivery (MAPD) problem, in which a team of agents has to plan paths to accomplish incoming pickup and delivery tasks without collisions, has recently attracted significant attention both from academia and industry. In this paper, we consider a MAPD setting in which the environment is dynamic, namely it is populated by other moving agents, beyond those belonging to the team. For instance, in a warehouse, moving agents could be humans or cleaning robots. We assume that the team agents cannot communicate with the moving agents and cannot interfere with their tasks and paths, which are a priori unknown and cannot be modified. As a consequence, team agents have to reactively try to solve potential collisions when they appear. However, it can happen that some conflicts are not solvable without affecting the moving agents, resulting in deadlocks. Since deadlocks can become rather frequent, especially in crowded environments, in this paper we propose an approach that, by imposing minor constraints on the environment and the movements of the agents, solves potential collisions and prevents the formation of deadlocks by design. Experimental results show that our approach prevents deadlocks, even in very crowded environments, with negligible impact on the performance of task completion.

AAMAS Conference 2023 Conference Paper

Multi-Agent Pickup and Delivery in Presence of Another Team of Robots

• Benedetta Flammini
• Davide Azzalini
• Francesco Amigoni

In a Multi-Agent Pickup and Delivery (MAPD) problem, a group of agents has to accomplish subsequent pickup and delivery tasks while avoiding collisions. Tasks are provided at runtime, making MAPD a combination between classical Multi-Agent Path Finding (MAPF) and online task assignment. In this paper, we consider a new formulation of the MAPD problem, in which a guest team of agents has to solve its MAPD problem without interfering with the main team of agents, called home team, that is already carrying out its own MAPD problem in the same environment. The two teams are independent, and inter-teams communications are not allowed. We address the problem from the point of view of the guest agents, and we propose that they build a model of the behavior of the home team and exploit this information in planning their paths. Experimental results show that the inclusion of information about the behavior of home agents in guests’ planning phase reduces the number of potential collisions (and hence the replanning overhead) and decreases tasks’ completion time for guests.

AAMAS Conference 2023 Conference Paper

Multi-Agent Pickup and Delivery with Task Probability Distribution

• Andrea Di Pietro
• Nicola Basilico
• Francesco Amigoni

Multi-Agent Pickup and Delivery (MAPD) consists in completing a set of tasks by having agents move to the pickup location and then to the delivery location of each task. In MAPD, new tasks are dynamically added to the system throughout its lifetime and existing algorithms usually assume either complete ignorance or full knowledge about the position and the time at which future tasks will appear until they are actually added to the system. This paper introduces a novel MAPD problem in which a spatial and temporal probability distribution of future tasks is known and defines algorithms that take advantage of this knowledge to reduce the average time required to execute tasks. In particular, we build on an existing MAPD algorithm, Token Passing (TP), proposing different ways to exploit a given task probability distribution. Experiments show that these methods can have a positive impact on the time required to complete the tasks.

EAAI Journal 2022 Journal Article

Reconstruction and prediction of the layout of indoor environments from two-dimensional metric maps

• Matteo Luperto
• Francesco Amigoni

Metric maps, like occupancy grids, are one of the most common ways to represent indoor environments in autonomous mobile robotics. Although they are effective for navigation and localization, metric maps contain little knowledge about the structure of the buildings they represent. In this paper, we propose a method that identifies the structure of indoor environments from 2D metric maps by retrieving their layout, namely an abstract geometrical representation that models walls as line segments and rooms as polygons. The method works by finding regularities within a building, abstracting from the possibly noisy information of the metric map, and uses such knowledge to reconstruct the layout of the observed part and to predict a possible layout of the partially observed portion of the building. Thus, differently of other methods from the state of the art, our method can be applied both to fully observed environments and, most significantly, to partially observed ones. Experimental results show that our approach performs effectively and robustly on different types of input metric maps and that the predicted layout is increasingly more accurate when the input metric map is increasingly more complete. The layout returned by our method can be exploited in several tasks, such as semantic mapping, place categorization, path planning, human–robot communication, and task allocation.

AAMAS Conference 2021 Conference Paper

Exploration of Indoor Environments through Predicting the Layout of Partially Observed Rooms

• Matteo Luperto
• Luca Fochetta
• Francesco Amigoni

We consider exploration tasks in which an autonomous mobile robot incrementally builds maps of initially unknown indoor environments. In such tasks, the robot makes a sequence of decisions on where to move next that, usually, are based on knowledge about the observed parts of the environment. In this paper, we present an approach that exploits a prediction of the geometric structure of the unknown parts of an environment to improve exploration performance. In particular, we leverage an existing method that reconstructs the layout of an environment starting from a partial grid map and that predicts the shape of partially observed rooms on the basis of geometric features representing the regularities of the indoor environment. Then, we originally employ the predicted layout to estimate the amount of new area the robot would observe from candidate locations in order to inform the selection of the next best location and to early stop the exploration when no further relevant area is expected to be discovered. Experimental activities show that our approach is able to exploit the predicted layout of partially observed rooms in order to speed up the exploration.

AAMAS Conference 2019 Conference Paper

Exploiting Inaccurate A Priori Knowledge in Robot Exploration

• Matteo Luperto
• Danilo Fusi
• N. Alberto Borghese
• Francesco Amigoni

Exploration is a task in which autonomous mobile robots incrementally discover features of interest in initially unknown environments. Most of the current exploration approaches ignore prior knowledge about the environments that have to be explored. However, in some practical cases, such knowledge could be available. In this paper, we present a method that includes a priori knowledge in an exploration strategy that selects the next best locations the robot should reach in partially explored indoor environments by exploiting the (possibly inaccurate) knowledge of their� oor plans.

ICRA Conference 2019 Conference Paper

Predicting the Layout of Partially Observed Rooms from Grid Maps

• Matteo Luperto
• Valerio Arcerito
• Francesco Amigoni

In several applications, autonomous mobile robots benefit from knowing the structure of the indoor environments where they operate. This knowledge can be extracted from the metric maps built (e. g. , using SLAM algorithms) from the data perceived by the robots' sensors. The layout is a way to represent the structure of an indoor environment with geometrical primitives. Most of the current methods for reconstructing the layout from a metric map represent the parts of the environment that have been fully observed. In this paper, we propose an approach that predicts the layout of rooms which are only partially known in a 2D metric grid map. The prediction is made according to the global structure of the environment, as identified from its known parts. Experiments show that our approach is able to effectively predict the layout of several indoor environments that have been observed to different degrees.

AAMAS Conference 2018 Conference Paper

A Journey Among Pairs of Vertices: Computing Robots' Paths for Performing Joint Measurements

• Alessandro Riva
• Jacopo Banfi
• Carlo Fanton
• Nicola Basilico
• Francesco Amigoni

The problem of performing joint measurements recurs in many robotic applications, like constructing communication maps from signal strength samples gathered on the field. In spite of this, a theory supporting efficient algorithms has not been yet developed and ad hoc methods are usually employed. In this paper, we consider an environment represented by a metric graph and prove that the problem of jointly performing measurements from given vertices is NP-hard when either the total traveled distance or the task completion time have to be minimized. Given the difficulty of finding optimal paths in an efficient way, we propose a greedy randomized approach able to cope with both the optimization objectives. In settings for which joint measurements must be taken for all pairs of vertices, we prove that a deterministic greedy algorithm achieves an O(m logn) approximation factor for the traveled distance objective, where m is the number of robots and n the number of vertices, and an O(m2 logn) approximation factor for the completion time. Experiments in simulation show that our algorithms perform well in practice, also when compared to an ad hoc method taken from the literature.

AAMAS Conference 2018 Conference Paper

A Search-Based Approach to Solve Pursuit-Evasion Games with Limited Visibility in Polygonal Environments

• Alberto Quattrini Li
• Raffaele Fioratto
• Francesco Amigoni
• Volkan Isler

A pursuit-evasion game is a non-cooperative game in which a pursuer tries to detect or capture an adversarial evader. We study a pursuit-evasion game which takes place in a known polygonal environment. The goal of the pursuer is to capture the evader by moving onto its location. The players can observe each others’ locations only if they can “see” each other – i. e. , if the line segment connecting their locations lies entirely inside the polygonal environment. The complexity of representing the information available to the players at a given time makes solving pursuit-evasion games with visibility limitations di�cult. We represent the state of the game using an e�cient visibility-based decomposition of the environment paired with a more classical grid-based decomposition. The optimal players’ strategies are computed using a min-max search algorithm improved with speci�c speedup techniques that preserve optimality. We show that our decomposition is complete for a rash evader, which hides from the pursuer and does not move from its hiding location when the pursuer is not visible. Simulations in realistic indoor environments and comparison with a Monte Carlo tree search algorithm validate our approach.

IROS Conference 2018 Conference Paper

Improving Repeatability of Experiments by Automatic Evaluation of SLAM Algorithms

• Francesco Amigoni
• Valerio Castelli
• Matteo Luperto

The development of good experimental methodologies for robotics takes often inspiration from general principles of experimental practice. Repeatability prescribes that experiments should involve several trials in order to guarantee that results are not achieved by chance, but are systematic, and statistically significant trends can be identified. In this paper, we propose an approach to improve the repeatability of experiments performed in robotics. In particular, we focus on the domain of SLAM (Simultaneous Localization And Mapping) and we introduce a system that exploits simulations to generate a large number of test data on which SLAM algorithms are automatically evaluated in order to obtain consistent results, according to the principle of repeatability.

AAAI Conference 2018 Conference Paper

Multiagent Connected Path Planning: PSPACE-Completeness and How to Deal With It

• Davide Tateo
• Jacopo Banfi
• Alessandro Riva
• Francesco Amigoni
• Andrea Bonarini

In the Multiagent Connected Path Planning problem (MCPP), a team of agents moving in a graph-represented environment must plan a set of start-goal joint paths which ensures global connectivity at each time step, under some communication model. The decision version of this problem asking for the existence of a plan that can be executed in at most a given number of steps is claimed to be NP-complete in the literature. The NP membership proof, however, is not detailed. In this paper, we show that, in fact, even deciding whether a feasible plan exists is a PSPACE-complete problem. Furthermore, we present three algorithms adopting different search paradigms, and we empirically show that they may efficiently obtain a feasible plan, if any exists, in different settings.

AAMAS Conference 2017 Conference Paper

A GRASP Metaheuristic for the Coverage of Grid Environments with Limited-Footprint Tools

• Alessandro Riva
• Francesco Amigoni

Coverage of known environments is a task involved in several applications of autonomous mobile robots, like patrolling, search and rescue, and cleaning. The (single robot) coverage problem can be formulated as that of finding the optimal tour that, when followed, allows a robot to cover with its tool (e. g. , a sensor or a brush) all the points of the free space of a given environment. Most of the current methods for coverage discretize the environment in cells, possibly of different shapes. In this paper, we consider a setting in which the environment is represented as a grid of equal square cells and in which a robot has a tool with limited range and angular field of view, able to cover a set of cells from a given pose. We propose an efficient covering method based on a on Greedy Randomized Adaptive Search Procedure (GRASP) metaheuristic approach that iteratively constructs a feasible solution and tries to improve it through local search. Results of experimental activities show that the proposed method produces solutions of better quality than those of a state-of-the-art method, in an efficient way.

IS Journal 2017 Journal Article

Multirobot Exploration of Communication-Restricted Environments: A Survey

• Francesco Amigoni
• Jacopo Banfi
• Nicola Basilico

Exploration of initially unknown environments is an online task in which autonomous mobile robots coordinate themselves to efficiently discover free spaces and obstacles. Several efforts have been devoted to study coordinated multirobot exploration assuming that communication is possible between any two locations. The problem of developing multirobot systems for effective exploration in the presence of communication constraints, despite its remarkable practical relevance, is comparably much less studied. The authors provide a taxonomy of the field of communication-restricted multirobot exploration, survey recent work in this field, and outline some promising research directions.

ICRA Conference 2017 Conference Paper

Multirobot online construction of communication maps

• Jacopo Banfi
• Alberto Quattrini Li
• Nicola Basilico
• Ioannis M. Rekleitis
• Francesco Amigoni

The importance of communication in many multirobot information-gathering tasks requires the availability of reliable communication maps. These provide estimates of the radio signal strength and can be used to predict the presence of communication links between different locations of the environment. In the problem we consider, a team of mobile robots has to build such maps autonomously in a robot-to-robot communication setting. The solution we propose models the signal's distribution with a Gaussian Process and exploits different online sensing strategies to coordinate and guide the robots during their data acquisition. Our methods show interesting operative insights both in simulations and on real TurtleBot 2 platforms.

ICRA Conference 2017 Conference Paper

Semantic classification by reasoning on the whole structure of buildings using statistical relational learning techniques

• Matteo Luperto
• Alessandro Riva
• Francesco Amigoni

Semantic mapping for autonomous mobile robots includes the place classification task that associates semantic labels (like `corridor' or `office') to rooms perceived in indoor environments. The mainstream approaches to place classification are characterized by local reasoning, where only features relative to the neighbourhood of each room are considered. In this paper, we propose a method for global reasoning on the whole structure of buildings, considered as single structured objects. We use a statistical relational learning algorithm, called kLog, and we compare it against a classifier, Extra-Trees, which resembles classical local approaches, in three tasks: classification of rooms, classification of entire floors of buildings, and validation of simulated worlds. Our results show that our global approach performs better than local approaches when the classification task involves reasoning on the regularities of buildings and when available information about rooms is coarse-grained.

ICRA Conference 2016 Conference Paper

Asynchronous multirobot exploration under recurrent connectivity constraints

• Jacopo Banfi
• Alberto Quattrini Li
• Nicola Basilico
• Ioannis M. Rekleitis
• Francesco Amigoni

In multirobot exploration under centralized control, communication plays an important role in constraining the team exploration strategy. Recurrent connectivity is a way to define communication constraints for which robots must connect to a base station only when making new observations. This paper studies effective multirobot exploration strategies under recurrent connectivity by considering a centralized and asynchronous planning framework. We formalize the problem of selecting the optimal set of locations robots should reach, provide an exact formulation to solve it, and devise an approximation algorithm to obtain efficient solutions with a bounded loss of optimality. Experiments in simulation and on real robots evaluate our approach in a number of settings.

AAMAS Conference 2016 Conference Paper

Water Resources Systems Operations via Multiagent Negotiation (Extended Abstract)

• Francesco Amigoni
• Andrea Castelletti
• Paolo Gazzotti
• Matteo Giuliani
• Emanuele Mason

The operations of water resources infrastructures, like dams and diversions, often involve multiple conflicting interests and stakeholders. Agent-based approaches have recently attracted an increasing attention to design optimal operating policies for these systems. In this paper we contribute a general monotonic concession negotiation protocol that allows the stakeholders-agents of a regulated lake to reach agreements on the amount of water to release daily, balancing control of lake floods and water supply to agricultural districts downstream.

IROS Conference 2015 Conference Paper

A generative spectral model for semantic mapping of buildings

• Matteo Luperto
• Leone D'Emilio
• Francesco Amigoni

Consider a mobile robot exploring an initially unknown school building and assume that it has already discovered some classrooms, offices, and bathrooms. What can the robot infer about the presence and the locations of other classrooms and offices in the school building? This paper makes a step toward providing an answer to the above question by proposing a system based on a generative model that is able to represent the topological structures and the semantic labeling schemas of buildings and to predict the structure and the schema for unexplored portions of these environments. We represent the buildings as undirected graphs, whose nodes are rooms and edges are physical connections between them. Given an initial knowledge base of graphs, our approach, relying on a spectral analysis of these graphs, segments each graph for finding significant subgraphs and clusters them according to their similarity. A graph representing a new building or an unvisited part of a building is eventually generated by sampling subgraphs from clusters and connecting them.

IROS Conference 2015 Conference Paper

Minimizing communication latency in multirobot situation-aware patrolling

• Jacopo Banfi
• Nicola Basilico
• Francesco Amigoni

We consider the problem of computing patrolling strategies under communication constraints for a team of autonomous robots employed in repeated surveillance missions on a set of predefined locations. We assume the presence of a communication infrastructure providing only some regions of the environment with a communication link to a mission control center (MCC). We define the problem of computing a joint patrolling strategy that minimizes communication latencies, defined as the delays between inspecting some locations and reporting the outcome to the MCC. We provide and experimentally evaluate a MILP formulation and a heuristic method.

ICRA Conference 2014 Conference Paper

Matching line segment scans with mutual compatibility constraints

• Mladen Mazuran
• Francesco Amigoni

Over the years, proposals have been made to employ line segments to build 2D maps of indoor environments. One of the basic steps of these approaches is the matching between scans (or, more generally, sets) of line segments, which is usually addressed using variants of the Iterative Closest Line (ICL) paradigm. ICL is based on the idea of associating closest line segments belonging to the two scans and of reducing the distance between them. In this paper, we propose two algorithms that go beyond this approach by exploiting the mutual compatibility between associations of line segments. Experimental results show that our algorithms significantly outperform, in terms of matching accuracy, traditional algorithms based on ICL, at the cost of a slightly longer execution time.

ICRA Conference 2012 Conference Paper

A game theoretical approach to finding optimal strategies for pursuit evasion in grid environments

• Francesco Amigoni
• Nicola Basilico

Pursuit evasion problems, in which evading targets must be cleared from an environment, are encountered in surveillance and search and rescue applications. Several works have addressed variants of this problem in order to study strategies for the pursuers. As a common trait, many of these works present results in the general form: given some assumptions on the environment, on the pursuers, and on the evaders, upper and lower bounds are calculated for the time needed for (the probability of, the resources needed for, .. .) clearing the environment. The question “what is the optimal strategy for a given pursuer in a given environment to clear a given evader? ” is left largely open. In this paper, we propose a game theoretical framework that contributes in finding an answer to the above question in a version of the pursuit evasion problem in which the evader enters and exits a grid environment and the pursuer has to intercept it along its path. We adopt a criterion for optimality related to the probability of capture. We experimentally evaluate the proposed approach in simulated settings and we provide some hints to generalize the framework to other versions of the pursuit evasion problem.

AIJ Journal 2012 Journal Article

Patrolling security games: Definition and algorithms for solving large instances with single patroller and single intruder

• Nicola Basilico
• Nicola Gatti
• Francesco Amigoni

Security games are gaining significant interest in artificial intelligence. They are characterized by two players (a defender and an attacker) and by a set of targets the defender tries to protect from the attackerʼs intrusions by committing to a strategy. To reach their goals, players use resources such as patrollers and intruders. Security games are Stackelberg games where the appropriate solution concept is the leader–follower equilibrium. Current algorithms for solving these games are applicable when the underlying game is in normal form (i. e. , each player has a single decision node). In this paper, we define and study security games with an extensive-form infinite-horizon underlying game, where decision nodes are potentially infinite. We introduce a novel scenario where the attacker can undertake actions during the execution of the defenderʼs strategy. We call this new game class patrolling security games (PSGs), since its most prominent application is patrolling environments against intruders. We show that PSGs cannot be reduced to security games studied so far and we highlight their generality in tackling adversarial patrolling on arbitrary graphs. We then design algorithms to solve large instances with single patroller and single intruder.

AAAI Conference 2012 Conference Paper

Searching for Optimal Off-Line Exploration Paths in Grid Environments for a Robot with Limited Visibility

• Alberto Quattrini Li
• Francesco Amigoni
• Nicola Basilico

ICRA Conference 2011 Conference Paper

Defining effective exploration strategies for search and rescue applications with Multi-Criteria Decision Making

• Nicola Basilico
• Francesco Amigoni

Autonomous mobile robots are a promising technology for search and rescue scenarios, where an initially unknown environment has to be explored to locate human victims. Robots can exploit exploration strategies to autonomously move around the environment. Most of the strategies proposed in literature are based on the idea of evaluating a number of candidate locations according to ad hoc utility functions that combine different criteria. In this paper, we show some of the advantages of using a more theoretically-grounded approach, based on Multi-Criteria Decision Making (MCDM), to define exploration strategies for robots employed in search and rescue applications. We implemented our MCDM-based exploration strategies within an existing robot controller and we evaluated their performance in a simulated environment.

AAMAS Conference 2011 Conference Paper

Exploration Strategies Based on Multi-Criteria Decision Making for Search and Rescue Autonomous Robots

• Nicola Basilico
• Francesco Amigoni

Autonomous mobile robots are considered a valuable technology for search and rescue applications, where an initially unknown environment has to be explored to locate human victims. In this scenario, robots exploit exploration strategies to autonomously move around the environment. Most of the strategies proposed in literature are based on the idea of evaluating a number of candidate locations according to ad hoc utility functions that combine different criteria. In this paper, we show some of the advantages of using a more theoretically-grounded approach, based on Multi-Criteria Decision Making (MCDM), to define exploration strategies for robots employed in search and rescue applications. We implemented some MCDM-based exploration strategies within an existing robot controller and we experimentally evaluated their performance in a simulated environment.

ICRA Conference 2010 Conference Paper

Moving game theoretical patrolling strategies from theory to practice: An USARSim simulation

• Francesco Amigoni
• Nicola Basilico
• Nicola Gatti 0001
• Alessandro Saporiti
• Stefano Troiani

Game theoretical approaches have been recently used to develop patrolling strategies for mobile robots. The idea is that the patroller and the intruder play a game, whose outcome depends on the combination of their actions. From the analysis of this game, an optimal strategy for the patrolling robot can be derived. Although game theoretical approaches are promising, their applicability in real settings is still an open problem. In this paper, we experimentally evaluate the practical applicability of the most general game theoretical approach for patrolling strategies, called BGA model. Experiments are conducted by using USARSim, with the goal of studying the behavior of the optimal patrolling strategy returned by the BGA model both in situations that violate its idealized assumptions and in comparison with other patrolling strategies that can be developed with much less computational effort.

ICRA Conference 2009 Conference Paper

Finding the optimal strategies for robotic patrolling with adversaries in topologically-represented environments

• Francesco Amigoni
• Nicola Basilico
• Nicola Gatti 0001

Using autonomous mobile robots to patrol environments for detecting intruders is a topic of increasing relevance for its possible applications. A large part of strategies for mobile patrolling robots proposed so far adopt some kind of random movements. Although these strategies are unpredictable for an intruder, they are not always efficient in getting the patroller a large expected utility. In this paper we propose an approach that considers a model of the adversary in a game theoretic framework to find optimally-efficient patrolling strategies. We show that our approach extends those proposed in literature and we experimentally analyze some of its features.

AAMAS Conference 2009 Conference Paper

Leader-Follower Strategies for Robotic Patrolling in Environments with Arbitrary Topologies

• Nicola Basilico
• Nicola Gatti
• Francesco Amigoni

Game theoretic approaches to patrolling have become a topic of increasing interest in the very last years. They mainly refer to a patrolling mobile robot that preserves an environment from intrusions. These approaches allow for the development of patrolling strategies that consider the possible actions of the intruder in deciding where the robot should move. Usually, it is supposed that the intruder can hide and observe the actions of the patroller before intervening. This leads to the adoption of a leader-follower solution concept. In this paper, mostly theoretical in its nature, we propose an approach to determine optimal leader-follower strategies for a mobile robot patrolling an environment. Differently from previous works in literature, our approach can be applied to environments with arbitrary topologies.

IROS Conference 2008 Conference Paper

Analysis of methods for reducing line segments in maps: Towards a general approach

• Francesco Amigoni
• Simone Gasparini

Segment-based maps are emerging as an efficient way to represent the environments in which mobile robots operate. When compared to grid-based maps, maps composed of line segments usually need less space to be stored. However, very little effort has been devoted to methods that allow to reduce the size of segment-based maps by removing redundant line segments that represent the same object in the environment. This problem is usually addressed with rather ad hoc methods that are embedded in mapping systems. In this paper, we put forward the problem of reducing the size of segment-based maps by presenting a survey of the existing methods and by experimentally evaluating some of them. Our results can be used to set out some guidelines for the development of a general approach to reducing redundant line segments in maps.

ICRA Conference 2008 Conference Paper

Experimental evaluation of some exploration strategies for mobile robots

• Francesco Amigoni

The ability of building maps of environments where they operate is one of the main requirements for autonomous mobile robots. An efficient map building process is based on a good exploration strategy that determines the most convenient observation positions in a partially known environment in order to incrementally map it. Several exploration strategies have been proposed in literature but their comparative evaluations are rare. In this paper, we experimentally compare some exploration strategies in order to contribute to assess their strengths and weaknesses.

JAAMAS Journal 2007 Journal Article

A formal framework for connective stability of highly decentralized cooperative negotiations

• Francesco Amigoni
• Nicola Gatti

Abstract Multiagent cooperative negotiation is a promising technique for modeling and controlling complex systems. Effective and flexible cooperative negotiations are especially useful for open complex systems characterized by high decentralization (which implies a low amount of exchanged information) and by dynamic connection and disconnection of agents. Applications include ad hoc network management, vehicle formation, and physiological model combination. To obtain an effective control action, the stability of the negotiation, namely the guarantee that an agreement will be eventually reached, is of paramount importance. However, the techniques usually employed for assessing the stability of a negotiation can be hardly applied in open scenarios. In this paper, whose nature is mainly theoretical, we make a first attempt towards engineering stable cooperative negotiations proposing a framework for their analysis and design. Specifically, we present a formal protocol for cooperative negotiations between a number of agents and we propose a criterion for negotiation stability based on the concept of connective stability. This is a form of stability that accounts for the effects of structural changes on the composition of a system and that appears very suitable for multiagent cooperative negotiations. To show its possible uses, we apply our framework for connective stability to some negotiations taken from literature.

ICRA Conference 2007 Conference Paper

Good Experimental Methodologies for Robotic Mapping: A Proposal

• Francesco Amigoni
• Simone Gasparini
• Maria L. Gini

A way to significantly advance robotic science is to perform experiments that can be replicated by other researchers and be used to compare different methods. This happens rarely in current robotics research. In this paper we present a methodology for performing experimental activities in the area of robotic mapping. The proposed methodology prescribes a number of issues that should be addressed when experimentally validating a mapping method. We present the application of the proposed methodology to a mapping system we have developed.

ECAI Conference 2006 Conference Paper

A Multiagent System for Scheduling Activities Onboard a Space System

• Francesco Amigoni
• Simone Farè
• Michèle Lavagna
• Guido Sangiovanni

The possible advantages of employing multiple agents to manage activities on a single space system are largely unexplored. This paper presents the experimental validation of a multiagent scheduler for a low Earth orbit satellite.

AAMAS Conference 2005 Conference Paper

A Decentralized Bargaining Protocol on Dependent Continuous Multi-Issue for Approximate Pareto Optimal Outcomes

• Nicola Gatti
• Francesco Amigoni

ICRA Conference 2005 Conference Paper

A Multi-Objective Exploration Strategy for Mobile Robots

• Francesco Amigoni
• Alessandro Gallo

Exploration strategies are used to guide mobile robots in building maps of environments. Usually, exploration strategies work greedily by evaluating a number of candidate observation positions on the basis of a utility function and selecting the best one. The utility functions are defined in an ad hoc manner as the compositionof values measuring different features of a candidate observation position, such as the travelling cost and the estimated information gain. In this paper, we propose a more general way to define an exploration strategy through multi-objective optimization. In our approach, the values of the features are kept separated without combining them in a particular utility function. Experimental results demonstrate the effectiveness of our method.

AAMAS Conference 2004 Conference Paper

A Cooperative Negotiation Protocol for Physiological Model Combination

• Nicola Gatti
• Francesco Amigoni

ICRA Conference 2004 Conference Paper

Map Building without Odometry Information

• Francesco Amigoni
• Simone Gasparini
• Maria L. Gini

The map building methods usually employed by mobile robots are based on the assumption that an estimate of the position of the robot can be obtained from odometry readings. In this paper we propose three methods that build a geometrical global map by integrating partial maps without using any odometry information. We focus on the problem of integrating a sequence of partial maps that specifies the order in which the partial maps must be integrated. Experimental results show the effectiveness of our approach in different types of environments.

AIIM Journal 2003 Journal Article

Anthropic agency: a multiagent system for physiological processes

• Francesco Amigoni
• Marco Dini
• Nicola Gatti
• Marco Somalvico

Multiagent systems are powerful and flexible tools for modelling and regulating complex phenomena. In fact, a way to manage the complexity of a phenomenon is to decompose it in such a way that each agent embeds the control model for a portion of the phenomenon. In this perspective, the cooperative interaction among the agents results in the controller for the whole phenomenon. Since the portions in which the phenomenon is decomposed may overlap, the actions the single agents undertake to regulate these portions may conflict; hence a balanced negotiation is required. A class of complex phenomena that present several difficulties in their satisfactory modelling and controlling is the class of physiological processes. The purpose of this paper is to introduce a general multiagent architecture, called anthropic agency, for the modelling and the regulation of complex physiological phenomena.