For robots tasked with surveying the temporal dynamics of a changing environment, a choice must be made to observe novel regions of the environment or to re-survey previously visited regions, which may have changed. We present a novel multi-robot informative path planner (IPP) that combines an environmental and task kernel to direct mobile robots to gather samples from regions that would result in the greatest expected improvement in map accuracy. Our planner utilizes a multi-output Gaussian process to unify priors about the spatiotemporal environment along with priors about observational correlations between sensing vehicles. Additionally, we extend our analysis into an adaptive planning scenario and examine the performance under different planning configurations. We find that planning performance is largely driven by the choice of environmental priors, and that unrepresentative priors can be improved through adaptive planning.

This paper explores decision-making processes in robotic systems tasked with reconstructing scalar fields through sensing in uncertain environments. Each robot must handle noisy perception and operate within specific environmental and physical constraints. The complexity increases in multiagent scenarios, where robots must not only plan their actions but also anticipate the movements and strategies of other agents. Effective coordination is crucial to prevent collisions and minimize redundant tasks. To address this challenge, we propose an online, distributed multi-robot sampling algorithm that combines Monte Carlo Tree Search (MCTS) with Gaussian regression. In this approach, each robot iteratively selects its next sampling point while exchanging limited information with other robots and predicting their future actions. Predictions about other robots future actions are computed with a MCTS that is recomputed at each iteration to incorporate all information collected up to that point. We evaluate the performance of our method across diverse environments and team sizes, comparing it to algorithmic alternatives.

Robotics and artificial intelligence hold significant potential for advancing precision agriculture. While robotic systems have been successfully deployed for various tasks, adapting them to perform diverse missions remains challenging, particularly because end users often lack technical expertise. In this paper, we present an end-to-end system that leverages large language models (LLMs), specifically ChatGPT, to enable users to assign complex data collection tasks to autonomous robots using natural language instructions. To enhance reusability, mission plans are encoded using an existing IEEE task specification standard, and are executed on robots via ROS2 nodes that bridge high-level mission descriptions with existing ROS libraries. Through extensive experiments, we highlight the strengths and limitations of LLMs in this context, particularly regarding spatial reasoning and solving complex routing challenges, and show how our proposed implementation-overcomes them.

We present a new Monte Carlo Tree Search (MCTS) algorithm to solve the stochastic orienteering problem with chance constraints, i.e., a version of the problem where travel costs are random, and one is assigned a bound on the tolerable probability of exceeding the budget. The algorithm we present is online and anytime, i.e., it alternates planning and execution, and the quality of the solution it produces increases as the allowed computational time increases. Differently from most former MCTS algorithms, for each action available in a state the algorithm maintains estimates of both its value and the probability that its execution will eventually result in a violation of the chance constraint. Then, at action selection time, our proposed solution prunes away trajectories that are estimated to violate the failure probability. Extensive simulation results show that this approach can quickly produce high-quality solutions and is competitive with the optimal but time-consuming solution. Note to Practitioners—In many practical scenarios one is faced with multiobjective sequential decision making problems that can be solved through constrained optimization. If some of the parameters are known with uncertainty, the event “violating one of the constraints” becomes a random variable whose probability should be bound. As an application of this general problem formulation, in this paper we consider stochastic orienteering, a problem that finds applications when a robot is tasked with performing multiple tasks of varying utility while being subject to a bound on the traveled distance. Many problems in logistics, precision agriculture, and environmental monitoring, just to name a few, can be cast as instances of this optimization problem.

Graph-patrolling problems in the adversarial domain typically embed models and assumptions about how hostile events, from which an environment must be protected, are generated at a specific time and location. Relying upon such attacker models prevents algorithms from synthesizing strategies that can generalize in different settings, providing good performance under different and uncertain scenarios. In this paper, we propose a first method to deal with adversarial patrolling using a data driven approach. We cast the problem in an RL setting where the reward function is based on the ability to neutralize attacks that can follow an unknown strategy and that, hence, can be viewed as a black box component. We apply a policy gradient framework for optimizing action probabilities under such a reward model showing how effective patrolling strategies can be obtained from repeated attack-defense interactions between a patrolling agent and an attacker. Our results show that the data driven patroller can effectively provide protection against multiple, diverse attacker behaviors.

Graph patrolling algorithms provide effective strategies for coordinating mobile robots in the context of autonomously surveilling valuable assets. Optimizing patrolling strategies often aims to minimize the time between subsequent visits to a vertex, a measure known in the literature as idleness. In the domain of multi-robot patrolling, two approaches have received the most attention so far. The first involves coordinating all robots to follow a shared patrolling strategy covering the entire graph, while the second approach partitions the environment into disjoint areas that are then assigned to individual robots. Starting from these existing solutions, this paper introduces a new method that bridges these two complementary approaches. Our technique splits the vertices of the graph into a partition that includes a shared portion of the environment patrolled collectively by all robots, along with disjoint areas allocated exclusively to individual robots. This problem is formulated in terms of minimizing the maximum weighted idleness of the graph and is shown to be NP-hard. We then describe an exact solution for the problem and propose various heuristics to efficiently compute solutions for large problem instances. We evaluate and compare the proposed techniques in simulation and demonstrate that, in most cases, our methods produce better patrolling strategies when compared to classic solutions. Moreover, for small problem instances where the exact solution can be found, we show that our proposed heuristic has a competitive performance ratio.

The ROS 2 Navigation Stack (Nav2) has emerged as a widely used software component providing the underlying basis to develop a variety of high-level functionalities. However, when used in outdoor environments such as orchards and vineyards, its functionality is notably limited by the presence of obstacles and/or situations not commonly found in indoor settings. One such example is given by tall grass and weeds that can be safely traversed by a robot, but that can be perceived as obstacles by LiDAR sensors, and then force the robot to take longer paths to avoid them, or abort navigation altogether. To overcome these limitations, domain specific extensions must be developed and integrated into the software pipeline. This paper presents a new, lightweight approach to address this challenge and improve outdoor robot navigation. Leveraging the multi-scale nature of the costmaps supporting Nav2, we developed a system that using a depth camera performs pixel level classification on the images, and in real time injects corrections into the local cost map, thus enabling the robot to traverse areas that would otherwise be avoided by the Nav2. Our approach has been implemented and validated on a Clearpath Husky and we demonstrate that with this extension the robot is able to perform navigation tasks that would be otherwise not practical with the standard components.

In multi-robot informative path planning the problem is to find a route for each robot in a team to visit a set of locations that can provide the most useful data to reconstruct an unknown scalar field. In the budgeted version, each robot is subject to a travel budget limiting the distance it can travel. Our interest in this problem is motivated by applications in precision agriculture, where robots are used to collect measurements to estimate domain-relevant scalar parameters such as soil moisture or nitrates concentrations. In this paper, we propose an online, distributed multi-robot sampling algorithm based on Monte Carlo Tree Search (MCTS) where each robot iteratively selects the next sampling location through communication with other robots and considering its remaining budget.We evaluate our proposed method for varying team sizes and in different environments, and we compare our solution with four different baseline methods. Our experiments show that our solution outperforms the baselines when the budget is tight by collecting measurements leading to smaller reconstruction errors.

We present a novel algorithm to solve the stochastic orienteering problem with chance constraints that combines Monte Carlo Tree Search (MCTS) with a best arm identification (BAI) algorithm. This method extends our recently proposed solution that builds a search planning tree considering both an objective function to maximize, as well as a chance constraint on the failure probability, i.e., the probability of violating the assigned budget constraint. By combining these two approaches, we obtain a new planner that tunes the amount of tree search at run time. Extensive simulation results on our benchmark problems show that the new approach is significantly faster than the previous one, while incurring in just marginal decrements in terms of performance.

The proliferation of unmanned vehicles offers many opportunities for solving environmental sampling tasks with applications in resource monitoring and precision agriculture. Informative path planning (IPP) includes a family of methods which offer improvements over traditional surveying techniques for suggesting locations for observation collection. In this work, we present a novel solution to the IPP problem by using a coregionalized Gaussian processes to estimate a dynamic scalar field that varies in space and time. Our method improves previous approaches by using a composite kernel accounting for spatiotemporal correlations and at the same time, can be readily incorporated in existing IPP algorithms. Through extensive simulations, we show that our novel modeling approach leads to more accurate estimations when compared with formerly proposed methods that do not account for the temporal dimension.

In this paper we consider the information path-planning problem for a single robot in a stochastic environment with static obstacles subject to a preassigned constraint on the distance it can travel. Given a set of candidate sampling locations, the objective is to determine a path for the robot that allows to visit as many sampling locations as possible to accurately reconstruct an unknown underlying scalar field while not exceeding the assigned travel budget. Starting from the assumption that the phenomenon being measured can be modeled by a Gaussian Process, our algorithm balances exploration and exploitation to determine a sequence of locations ensuring that a preassigned final site is reached before the budget is consumed. Using mutual information as a reward criterion, as well as a generative model to predict consumed energy, the algorithm iteratively determines where to sample next, and when to end the mission. Our findings are validated in simulation in various scenarios and lead to a better reconstruction with less failures when compared with other methods.

Robotics is playing an increasingly important role in precision agriculture and agricultural technology because it allows to tackle some important problems at scale at a time when the agricultural workforce is declining. Robots can collect data that can better inform farmers on the best course of actions for their crops. Robots can also perform tasks that are too labor intensive for workers. Despite increased availability, however, these technologies will not become as so pervasive that each problem instance will be taken care of by robots and it is therefore important to carefully select which ones should be addressed and which ones can be deferred. Starting from these premises, in this overview paper we discuss a series of scheduling problems we developed that is pervasive in these applications.

Polyculture farming, where multiple crop species are grown simultaneously, has potential to reduce pesticide and water usage while improving the utilization of soil nutrients. However, it is much harder to automate polyculture than monoculture. To facilitate research, we present AlphaGardenSim, a fast, first order, open-access polyculture farming simulator with single plant growth and irrigation models tuned using real world measurements. AlphaGardenSim can be used for policy learning as it simulates inter-plant dynamics, including light and water competition between plants in close proximity and approximates growth in a real greenhouse garden at 25,$000\times $the speed of natural growth. This paper extends earlier work with a new action space that includes planting, which dynamically finds new seed locations that increases resources utilization, and an adaptive sampling technique to reduce the number of actions taken at each timestep without affecting performance. We also evaluate other automation policies using a novel metric that combines plant diversity and canopy coverage. Code and supplementary material can be found athttps://github.com/BerkeleyAutomation/AlphaGarden.Note to Practitioners—Monoculture farming is often characterized by heavy agrichemical inputs, such as chemical fertilizers and pesticides, and increased vulnerability to disease and pestilence. This paper is motivated by the lack of long-term sustainability of industrial agriculture, and its implications for human food security. Although polyculture is a sustainable alternative to monoculture farming, it requires more human labor and is more challenging to automate. In this paper we propose a fast, first order simulator that simulates the growth of plants in a polyculture setting. Simulation experiments suggest that the simulator can be used to learn a planting, watering and pruning plan a robot can follow to produce maximal yield from a diverse set of plants with limited irrigation, however it has not yet been tested on a physical garden. In future research we will develop a fully automated controller that will operate planting, irrigation and pruning tools in a physical garden over multiple plant growth cycles.

In this article, we study the orienteering aisle-graph single-access problem (OASP), a variant of the orienteering problem for a robot moving in a so-called single-access aisle graph, i.e., a graph consisting of a set of rows that can be accessed from one side only. Aisle graphs model, among others, vineyards or warehouses. Each aisle-graph vertex is associated with a reward that a robot obtains when it visits the vertex itself. As the energy of the robot is limited, only a subset of vertices can be visited with a fully charged battery. The objective is to maximize the total reward collected by the robot with a battery charge. We first propose an optimal algorithm that solves the OASP in O (m 2n 2) time for aisle graphs with a single access consisting of m rows, each with n vertices. With the goal of designing faster solutions, we propose four greedy suboptimal algorithms that run in at most O(mn\(m + n)) time. For two of them, we guarantee an approximation ratio of 1 2(1-1 e), where e is the base of the natural logarithm, on the total reward by exploiting the well-known submodularity property. Experimentally, we show that these algorithms collect more than 80% of the optimal reward.

Polyculture farming is a sustainable farming technique based on synergistic interactions between differing plant types that make them more resistant to diseases and pests and better able to retain water. Reduced uniformity can reduce use of pesticides, fertilizer, and water, but is more labor intensive and more challenging to automate. We describe a scaled physical testbed (1.5m×3.0m) that uses a high resolution camera and soil sensors to monitor polyculture plants to facilitate tuning of plant growth, companion effects, and irrigation parameters for a first-order garden simulator. We use this simulator to develop a novel seed placement algorithm that increases coverage and diversity, and a learned pruning policy. In simulation experiments, the seed placement algorithm yields 60% more coverage and 10% more diversity than random seed placement and the learned pruning policy runs 1000X faster than a procedural lookahead policy to achieve high leaf coverage and plant diversity on adversarial gardens that include plant species with diverse growth rates. These models and policies provide the groundwork for a fully-automated system under development. Code, datasets and supplementary material can be found at https://github.com/BerkeleyAutomation/AlphaGarden/.

We study a stochastic version of the classic orienteering problem where the time to traverse an edge is a continuous random variable. For a given temporal deadline B, our solution produces a policy, i.e., a function that, based on the current position along a solution path and the elapsed time, decides whether to continue along the path or take a shortcut to avoid missing the deadline. The solution is based on a formulation using constrained Markov decision processes to ensure that the deadline is met with a preassigned confidence level. To expedite the computation, a Monte Carlo simulation on an open loop policy is run to determine how to adaptively discretize the temporal dimension and therefore reduce the number of states and the number of optimization variables in the associated linear program. Our results show that the adaptive algorithm matches the performance of the non-adaptive one while taking significantly less time.

We consider the Stochastic Orienteering Problem with random traversal time for edges. In this scenario the length of the path is a random variable and we consider a formulation with chance constraints, i.e., a bound on the probability that the length of the path exceeds the allotted budget. Our proposed solution casts the problem as an instance of a suitably defined Constrained Markov Decision Process and uses a Lagrangian formulation to solve it. In particular, exploiting some structural properties of the associated decision process we can solve the Markov Decision Process using a Lagrangian approach and efficiently determine the optimal Lagrange multiplier. Our method is experimentally evaluated and demonstrated to be significantly faster than previous solutions using a linear programming approach to solve the Stochastic Orienteering Problem with chance constraints.

We study a patrolling problem where multiple agents are tasked with protecting an environment where one or more adversaries are trying to compromise targets of varying value. The objective of the patrollers is to move between targets to quickly spot when an attack is taking place and then diffuse it. Differently from most related literature, we do not assume that attackers have full knowledge of the strategies followed by the patrollers, but rather build a model at run time through repeated observations of how often they visit certain targets. We study three different solutions to this problem. The first two partition the environment using either a fast heuristic or an exact method that is significantly more time consuming. The third method, instead does not partition the environment, but rather lets every patroller roam over the entire environment. After having identified strengths and weaknesses of each method, we contrast their performances against attackers using different algorithms to decide whether to attack or not.

In this paper, we consider the Constant-cost Orienteering Problem (COP) where a robot, constrained by a limited travel budget, aims at selecting a path with the largest reward in an aisle-graph. The aisle-graph consists of a set of loosely connected rows where the robot can change lane only at either end, but not in the middle. Even when considering this special type of graphs, the orienteering problem is known to be intractable. We optimally solve in polynomial time two special cases, COP-FR where the robot can only traverse full rows, and COP-SC where the robot can access the rows only from one side. To solve the general COP, we then apply our special case algorithms as well as a new heuristic that suitably combines them. Despite its light computational complexity and being confined into a very limited class of paths, the optimal solutions for COP-FR turn out to be competitive in terms of achieved rewards even for COP. This is shown by means of extended simulations performed on both real and synthetic scenarios. Furthermore, our new heuristic for the general case outperforms state-of-art algorithms, especially for input with highly unbalanced rewards.

In this paper we consider the stochastic cost orienteering problem, i.e., a version of the classic orienteering problem where the cost associated with each edge is a random variable with known distribution. Such a model is relevant when travel costs are variable, e.g., when a robot moves in uncertain terrain conditions. We model this problem using a composite state space tracking both how much progress the robot has made towards the goal and how much time it has left. On top of this state space, we compute a time-aware policy that allows the robot to dynamically adjust its path and avoid missing the temporal deadline. This policy is determined using a Constrained Markov Decision Process that allows tuning the accepted failure probability upfront. This approach suffers from a significant growth in the composite state space, and to mitigate this problem we introduce an aggregation technique where nearby vertices are compounded together, effectively reducing the original routing problem to an instance with a smaller state space. We then analyze this approach over large scale problem instances associated with robotic irrigation on a commercial grade vineyard.

We consider the problem of multirobot routing in vineyards, a task motivated by our ongoing project aiming at creating a corobotic system to implement precision irrigation on large-scale commercial vineyards. The problem is related to a combinatorial optimization problem on graphs called “team orienteering.” Team orienteering is known to be NP-hard, thus motivating the development of heuristic solutions that can scale to large problem instances. We propose three different parameter-free approaches informed by the domain we consider and compare them against a general purpose heuristic developed previously. In numerous benchmarks derived from data gathered in a commercial vineyard, we demonstrate that our solutions outperform the general purpose heuristic and are scalable, thus allowing us to solve instances with tens of thousands of vertices in the graphs. Note to Practitioners-Routing problems with budget and motion constraints are pervasive to many applications. In particular, the structural constraints considered in this problem are found not only in agricultural environments but also in warehouse logistics and other domains where goods are arranged along regular linear structures. This article proposes and analyzes algorithms that can be applied when multiple agents must be coordinated in these environments. In particular, by utilizing domain-specific knowledge, the solutions proposed in this article outperform general purpose approaches that poorly scale with the size of the environment. The algorithms we present also ensure that no collisions occur between robots-an aspect normally neglected in algorithms previously proposed to solve the team orienteering problem.

Large-scale micro-aerial vehicle (MAV) swarms provide promising solutions for situational awareness in applications such as environmental monitoring, urban surveillance, search and rescue, and so on. However, these scenarios do not provide localization infrastructure and limit cost and size of on-board capabilities of individual nodes, which makes it challenging for nodes to autonomously navigate to suitable preassigned locations. In this article, we present H-DrunkWalk , a collaborative and adaptive technique for heterogeneous MAV swarm navigation in environments not formerly preconditioned for operation. Working with heterogeneous MAV swarm, the H-DrunkWalk achieves high accuracy through collaboration but still maintains a low cost of the entire swarm. The heterogeneous MAV swarm consists of two types of nodes: (1) basic MAVs with limited sensing, communication, computing capabilities and (2) advanced MAVs with premium sensing, communication, computing capabilities. The key focus behind this networked MAV swarm research is to (1) rely on collaboration to overcome limitations of individual nodes and efficiently achieve system-wide sensing objectives and (2) fully take advantage of advanced MAVs to help basic MAVs improve their performance. The evaluations based on real MAV testbed experiments and large-scale physical-feature-based simulations show that compared to the traditional non-collaborative and non-adaptive method (dead reckoning with map bias), our system achieves up to 6× reductions in location estimation errors, and as much as 3× improvements in navigation success rate under the given time and accuracy constraints. In addition, by comprehensively considering the environment, heterogeneous structure, and quality of location estimation, our H-DrunkWalk brings 2× performance improvement (on average) as that of a hardware upgrade.

The use of autonomous robots for surveillance is one of the most interesting applications of graph-patrolling algorithms. In recent years, considerable effort has been devoted to tackling the problem of efficiently computing effective patrolling strategies. One of the mainstream approaches is adversarial patrolling, where a model of a strategic attacker is explicitly taken into account. A common assumption made by these techniques is to consider a worst-case attacker, characterized by ubiquitous and perfect observation capabilities. Motivated by the domain of robotic applications, we instead consider a more realistic and limited attacker model capable of gathering noisy observations in a locally limited range of the environment. We assume that the modeled attacker follows a behavior induced by its observations. Thus, we devise a randomized patrolling strategy based on Markov chains that makes observations reveal very little information, while still maintaining a reasonable level of protection in the environment. Our experimental results obtained in simulation confirm time-variance as a practical approach for our objective.

Indoor plants in homes and commercial buildings such as malls, offices, airports, and hotels, can benefit from precision irrigation to maintain healthy growth and reduce water consumption. As active valves are too costly, and ongoing precise manual adjustment of drip emitters is impractical, we explore how the Toyota HSR mobile manipulator robot can autonomously adjust low-cost passive emitters. To provide sufficient accuracy for gripper alignment, we designed a lightweight, modular Emitter Localization Device (ELD) with cameras and LEDs that can be non-invasively mounted on the arm. This paper presents details of the design, algorithms, and experiments with adjusting emitters using a two-phase procedure: (1) aligning the robot base using the build-in hand camera, and (2) aligning the gripper axis with the emitter axis using the ELD. We report success rates and sensitivity analysis to tune computer vision parameters and joint motor gains. Experiments suggest that emitters can be adjusted with 95 % success rate in approximately 20 seconds.

In this paper we propose a new approach to evaluate grasps that accounts for both the kinematic structure of the robot and the noise at its joints. Our starting observation is that with a redundant robot the same grasp can be implemented with different arm configurations, and these may display significant differences in terms of robustness to disturbances. Consequently, the grasp quality metric is seen as a random variable depending on the arm configuration. Starting from a first order approximation for the error, we introduce the high probability force closure region as a tool to evaluate the local robustness of an arm configuration, and we then introduce a new metric Qarmto rank different configurations according to the robustness to noise. By combining this method in an offline/online framework, we demonstrate through large scale simulations that this approach successfully captures aspects that were neglected in former literature regarding grasp evaluation, and can successfully be integrated into future grasp planners.

When robots navigate through vineyards to perform irrigation adjustments, an optimization problem emerges whereby robots are tasked with performing adjustments having the highest cumulative outcome within a given temporal budget due to limited battery charge. To this end, the robot needs to reach a set of spatially distributed sites, and the specific structure of the vineyard imposes various constraints on possible motions. In this paper we first demonstrate that this type of orienteering problem remains NP-hard even for the restricted class of graphs associated with precision irrigation. Then, we devise and analyze two greedy heuristics informed by the problem we consider. Finally, these algorithms are evaluated on settings associated with a commercial vineyard and we show that our methods favorably compare to solutions proposed in the past.

In this paper, we consider the problem of maintaining and restoring connectivity among a set of agents (humans or robots) by incrementally redeploying a team of mobile robots acting as communication relays. This problem is relevant in numerous scenarios where humans and robots are jointly deployed for tasks like urban search and rescue, surveillance, and the like. In this case, as the humans move in the environment, connectivity may be broken, and consequently, robots need to reposition themselves to restore it. We study the computational complexity of the problem, also in terms of approximation hardness, and present an Integer Linear Programming formulation to compute optimal solutions. We then analyze the performance of the proposed resolution approach against a heuristic algorithm taken from the literature, and we demonstrate how our method favorably compares in terms of solution quality and scalability.

In this paper, we address the problem of detecting intruders in complex bidimensional environments with a team of robots arranged in line formations called sweep lines. Sweep lines are used to coordinate the motion of multiple robots and guarantee the detection of any number of arbitrarily fast intruders, even when each robot has a limited sensor footprint. We present a formalization of the problem, coined Line-Clear, which requires the computation of sweep schedules to coordinate the motion of multiple sweep lines using the fewest robots possible. We provide a proof of NP-hardness of the general Line-Clear problem based on results from graph searching. An algorithm to compute sweep schedules for simply connected environments, which additionally guarantees that the cleared area is connected and not recontaminated, is then presented. We analyze its complexity formally and in simulation experiments and present solutions for a number of subproblems required for an implementation of the algorithm. The analysis provides a formal criterion for when the algorithm runs in polynomial time and the experiments indicate that this criterion may be satisfied for most environments in practice.

We consider the problem of grasping concave objects, i.e., objects whose surface includes regions with negative curvature. When a multifingered hand is used to restrain these objects, these areas can be advantageously used to determine grasps capable of more robustly resisting to external disturbance wrenches. We propose a new grasp quality metric specifically suited for this case, and we use it to inform a grasp planner searching the space of possible grasps. Our findings are validated both in simulation and on a real robot system executing a bin picking task. Experimental validation shows that our method is more effective than those not explicitly considering negative curvature.

In this paper we present an algorithm to compute risk averse policies in Markov Decision Processes (MDP) when the total cost criterion is used together with the average value at risk (AVaR) metric. Risk averse policies are needed when large deviations from the expected behavior may have detrimental effects, and conventional MDP algorithms usually ignore this aspect. We provide conditions for the structure of the underlying MDP ensuring that approximations for the exact problem can be derived and solved efficiently. Our findings are novel inasmuch as average value at risk has not previously been considered in association with the total cost criterion. Our method is demonstrated in a rapid deployment scenario, whereby a robot is tasked with the objective of reaching a target location within a temporal deadline where increased speed is associated with increased probability of failure. We demonstrate that the proposed algorithm not only produces a risk averse policy reducing the probability of exceeding the expected temporal deadline, but also provides the statistical distribution of costs, thus offering a valuable analysis tool.

We present an algorithm to solve a sequential stochastic decision making problem whereby a robot is subject to multiple objective functions and is asked to complete a number of subgoals specified using a subset of linear temporal logic. Each subgoal is associated with a desired satisfaction probability that will be met in expectation by the policy produced by the algorithm. Our method relies on the theory of constrained Markov Decision Processes and on methods coming from the realm of formal verification. The key idea is the definition of a product operation that can recursively incorporate more and more subgoals into the underlying planner. Ultimately, a policy is computed solving a linear program and we outline conditions for the existence and correctness of the solution. Our findings are validated in various simulation scenarios.

Constrained Markov Decision Processes offer a principled way to tackle sequential decision problems with multiple objectives. Although they could be very valuable in numerous robotic applications, to date their use has been quite limited. One of the reasons is that their solution requires to solve constrained linear programs with a large number of variables and this is computationally demanding, especially when considering dynamic environments. In this paper we propose a hierarchical approach to solve large CMDPs. States are clustered into macro states and relevant parameters like transition probabilities and costs are extracted with a Monte Carlo approach. Macro states are created with the objective of grouping together states with similar costs while preserving feasibility. We illustrate the value of our findings in a path planning scenario where the robot moves through an environment characterized by different risk levels. Our approach largely outperforms the non-hierarchical method and we also show how it prevails over methods based on fixed partitioning strategies.

We present Partial Quick Hull (PQH), an algorithm to efficiently compute one of the most commonly used grasp quality metrics. The metric relies on the computation of the convex hull of a set of points in a six dimensional space. Built on top of widely used QuickHull algorithm, PQH exploits the relationship between the convex hull and the grasp quality metric to avoid computing the whole convex hull. PQH determines at run time when the computation can be ended because the grasp quality metric can be already determined from a partially computed convex hull - hence the name of the algorithm. This improvement greatly accelerates grasp quality evaluation for force closure grasps. When the grasp is not force closure, the partial computation does not apply and PQH then behaves exactly like QuickHull. A large set of experimental tests show how PQH largely outperforms QuickHull and better scales with the size of the input.

In this paper we present an algorithm to determine the location of contact points to obtain force closure grasps on tree dimensional objects. The shape of the object is assumed to be given by a triangle mesh - a format widely used in CAD software. Our algorithm can handle an arbitrary number of contact points and does nor require any prior information about their initial locations. Through an iterative process, contact point locations are updated aiming at improving a commonly used grasp quality metric. The process is global in the sense that during the process the whole surface of the object can be explored, and contact point locations can cross sharp edges that usually represent a problem for optimization algorithms relying on smooth surface representations. Extensive simulation results illustrate the performance of the proposed method, outlining strengths and directions for further research.

We consider the problem of providing surveillance to a grid area using multiple heterogeneous UAVs, named sentinels and searchers, with complementary sensing and actuation capabilities. We consider probabilistic attacks and we analyze the expected performance with respect to the team deployment. We then introduce the problem of finding minmax deployments that result in the most desirable worst case performance caused by an attack. We present an algorithm to compute deployments while trading off solution's quality and computational effort and we qualitatively and quantitatively analyze it.

Micro-aerial vehicle (MAV) swarms are a new class of mobile sensor networks with many applications, including search and rescue, urban surveillance, radiation monitoring, etc. These sensing applications require autonomously navigating a high number of low-cost, low-complexity MAV sensor nodes in hazardous environments. The lack of preexisting localization infrastructure and the limited sensing, computing, and communication abilities of individual nodes makes it challenging for nodes to autonomously navigate to suitable preassigned locations. In this paper, we present a collaborative and adaptive algorithm for resource-constrained MAV nodes to quickly and efficiently navigate to preassigned locations. Using radio fingerprints between flying and landed MAVs acting as radio beacons, the algorithm detects intersections in trajectories of mobile nodes. The algorithm combines noisy dead-reckoning measurements from multiple MAVs at detected intersections to improve the accuracy of the MAVs' location estimations. In addition, the algorithm plans intersecting trajectories of MAV nodes to aid the location estimation and provide desired performance in terms of timeliness and accuracy of navigation. We evaluate the performance of our algorithm through a real testbed implementation and large-scale physical feature based simulations. Our results show that, compared to existing autonomous navigation strategies, our algorithm achieves up to 6X reduction in location estimation errors, and as much as 3X improvement in navigation success rate under the given time and accuracy constraints.

We study the problem of deploying a high number of low-cost, low-complexity robots inside a known environment with the objective that at least one robotic platform reaches each of N preassigned goal locations. Our study is inspired by SensorFly, a micro-aerial vehicle successfully used for mobile sensor network applications. SensorFly nodes feature limited on-board sensors, so one has to rely on simple navigation strategies and increase performance through redundance in the team. We introduce a simple, fully scalable deployment algorithm exploiting the limited capabilities offered by the SensorFly platform, and we explore its performance by feeding the simulation system with parameters extracted from the real SensorFly platform.

In this paper we consider the problem of multirobot deployment under temporal deadlines. The objective is to compute strategies trading off safety for speed to maximize the probability of reaching a given set of target locations within a pre-assigned temporal deadline. We formulate this problem using the theory of Constrained Markov Decision Processes and we show that thanks to this framework it is possible to determine deploying strategies maximizing the probability of success while satisfying the deadline. Moreover, the formulation allows to exactly compute the failure probability of complex deployment tasks. Simulation results illustrate how the proposed method works in different scenarios and show how informed decisions can be made regarding the size of the robot team.

In this paper we study the multi-robot deployment problem under hard temporal constraints. After proposing a model for this task, we consider the simplest deployment algorithm and we analyze the relationship between three fundamental parameters, the temporal deadline, the probability of success, and the number of robots. Because an exact analysis of even the simplest algorithm is computationally intractable, we derive an approximate bound leading to performance curves useful to answer design questions (how many robots are needed to get a certain performance guarantee?) or analysis questions (what is the probability of success given a certain deadline and number of robots?) Simulations show that the bounds are sharp and provide a useful tool to predict team deployment performance and tradeoffs.

Marching along the DARPA SyNAPSE roadmap, IBM unveils a trilogy of innovations towards the TrueNorth cognitive computing system inspired by the brain's function and efficiency. The non-von Neumann nature of the TrueNorth architecture necessitates a novel approach to efficient system design. To this end, we have developed a set of abstractions, algorithms, and applications that are natively efficient for TrueNorth. First, we developed repeatedly-used abstractions that span neural codes (such as binary, rate, population, and time-to-spike), long-range connectivity, and short-range connectivity. Second, we implemented ten algorithms that include convolution networks, spectral content estimators, liquid state machines, restricted Boltzmann machines, hidden Markov models, looming detection, temporal pattern matching, and various classifiers. Third, we demonstrate seven applications that include speaker recognition, music composer recognition, digit recognition, sequence prediction, collision avoidance, optical flow, and eye detection. Our results showcase the parallelism, versatility, rich connectivity, spatio-temporality, and multi-modality of the TrueNorth architecture as well as compositionality of the corelet programming paradigm and the flexibility of the underlying neuron model.

We propose a map merging algorithm that is capable of merging together heterogeneous maps independently built by different robots. Heterogeneous map merging is a crucially important problem for scenarios where multiple heterogeneous robots collaborate to provide situational awareness in urban search and rescue, patrolling, and explorations tasks, just to name a few. To remedy the lack of uniform representation between heterogeneous map models, we rely on the ubiquitous presence of WiFi signals in today's environments. Our solution consists of three steps. First, the overlap between the heterogeneous maps being merged is determined. Second, metric correspondences between overlapping parts are established. Third, the merging is improved by exploiting the structural properties inherent to graph-based maps. Our proposed system is validated using various occupancy grid and appearance-based maps built in real-world conditions, the results of which confirm its strengths. To the best of our knowledge, this is the first solution to the heterogeneous map merging problem.

While unimanual regrasping has been studied extensively, either by regrasping in-hand or by placing the object on a surface, bimanual regrasping has seen little attention. The recent popularity of simple end-effectors and dual-manipulator platforms makes bimanual regrasping an important behavior for service robots to possess. We solve the challenge of bimanual regrasping by casting it as an optimization problem, where the objective is to minimize execution time. The optimization problem is supplemented by image processing and a unimanual grasping algorithm based on machine learning that jointly identify two good grasping points on the object and the proper orientations for each end-effector. The optimization algorithm exploits this data by finding the proper regrasp location and orientation to minimize execution time. Influenced by human bimanual manipulation, the algorithm only requires a single stereo image as input. The efficacy of the method we propose is demonstrated on a dual manipulator torso equipped with Barrett WAM arms and Barrett Hands.

Unmanned Aerial Vehicles (UAVs) can be an effective technology for security applications involving patrolling and search missions. Defining online patrolling strategies for UAVs presents challenges related both to classical patrolling, as periodic monitoring of the environment, and to search, as accurate localization and identification of the mission-related activities. In this paper, we deal with this problem considering probabilistic intrusions and a variable resolution sensing model that naturally applies to the domain of UAVs. We present three online single-robot patrolling strategies exploiting a variable resolution paradigm to represent the environment that has recently shown promising results for search problems. The approach uses a hierarchical representation based on probabilistic quadtrees that allows UAVs to tradeoff sensing accuracy with sensing area. The model is extended by adding stochastic arrivals of intruders in space and time. Obtained results validate this approach for online patrolling against approaches based on uniform grids.

Appearance based maps are emerging as an important class of spatial representations for mobile robots. In this paper we tackle the problem of merging together two or more appearance based maps independently built by robots operating in the same environment. Noticing the lack of well accepted metrics to measure the performance of map merging algorithms, we propose to use algebraic connectivity as a metric to assess the advantage gained by merging multiple maps. Next, based on this criterion, we propose an anytime algorithm aiming to quickly identify the more advantageous parts to merge. The system we proposed has been fully implemented and tested in indoor scenarios and shows that our algorithm achieves a convenient tradeoff between accuracy and speed.

We consider the problem of team-based robot mapping and localization using wireless signals broadcast from access points embedded in today's urban environments. We map and localize in an unknown environment, where the access points' locations are unspecified and for which training data is a priori unavailable. Our approach is based on an heterogeneous method combining robots with different sensor payloads. The algorithmic design assumes the ability of producing a map in real-time from a sensor-full robot that can quickly be shared by sensor-deprived robot team members. More specifically, we cast WiFi localization as classification and regression problems that we subsequently solve using machine learning techniques. In order to produce a robust system, we take advantage of the spatial and temporal information inherent in robot motion by running Monte Carlo Localization on top of our regression algorithm, greatly improving its effectiveness. A significant amount of experiments are performed and presented to prove the accuracy, effectiveness, and practicality of the algorithm.

We consider the problem of cooperatively covering a group of static targets while simultaneously minimizing exposure from a different set of static locations. Starting from the work of Bullo et al. [8] who formalized the problem of cooperative sensor coverage as a multicenter optimization problem, we show that also this problem can be formulated and solved using related concepts. However, we evidence that the resulting function to be optimized loses some desirable properties and requires a more sophisticated controller. After having identified the peculiar aspects of this new function to be optimized and having studied its critical points, we provide a controller and show that it will drive the system to a stable local optimizer. The control strategy is distributed in the sense of Voronoi, and it implements a distributed version of the gradient projection method known in the optimization literature. Numerical simulations illustrate how the controller works, and we conclude sketching some theoretical properties.

We propose a novel framework to search for a static target using a multiscale representation. The algorithm we present is appropriate when the target detection sensor trades off accuracy versus covered area, e.g., when a UAV can fly and sense at different elevations. A structure based on quadtrees is used to propagate a posterior about the target location using a variable resolution representation that is dynamically refined in regions associated with higher probability of target presence. Probabilities are updated using a Bayesian approach accounting for erroneous sensor readings in the form of false positives and missed detections. The model we propose is coupled with a search and decision algorithm that determines where to sense next and with which accuracy. The search algorithm is based on an objective function accounting for both probability of detection and motion costs, thus aiming to minimize traveled distances while trying to localize the target. The paper is concluded with simulation results showing our approach outperforms commonly used methods based on uniform resolution grids.

Research on robotic manipulation has primarily focused on grasping rigid objects using a single manipulator. It is however evident that in order to be truly pervasive, service robots will need to handle deformable objects, possibly with two arms. In this paper we tackle the problem of using cooperative manipulators to perform towel folding tasks. Differently from other approaches, our method executes what we call a momentum fold - a swinging motion that exploits the dynamics of the object being manipulated. We propose a new learning algorithm that combines imitation and reinforcement learning. Human demonstrations are used to reduce the search space of the reinforcement learning algorithm, which then quickly converges to its final solution. The strengths of the algorithm come from its efficient processing, fast learning capabilities, absence of a deformable object model, and applicability to other problems exhibiting temporally incoherent parameter spaces. A wide range of experiments were performed on a robotic platform, demonstrating the algorithm's capability and practicality.

We consider the problem of searching for an unknown number of static targets inside an assigned area. The search problem is tackled using Probabilisitic Quadtrees (PQ), a data structure we recently introduced. Probabilistic quadtrees allow for a variable resolution representation and naturally induce a search problem where the searcher needs to choose not only where to sense, but also the sensing resolution. Through a Bayesian approach accommodating faulty sensors returning both false positives and missed detections, a posterior distribution about the location of the targets is propagated during the search effort. In this paper we extend our previous findings by considering the problem of searching for an unknown number of targets. Moreover, we substitute our formerly used heuristic with an approach based on information gain and expected costs. Finally, we provide some convergence results showing that in the worst case our model provides the same results as uniform grids, thus guaranteeing that the representation we propose gracefully degrades towards a known model. Extensive simulation results substantiate the properties of the method we propose, and we also show that our variable resolution method outperforms traditional methods based on uniform resolution grids.

A learning method capable of empowering a robot to successfully grasp a novel object through vision has recently been demonstrated, and generated much interest in the robotics community. In this paper we carefully analyze this new approach and apply dimensionality reduction techniques to decrease the number of features that need to be computed in order to classify whether a given pixel in an image is associated with a good or bad grasping point. Exploiting the ideas behind principal component analysis, we formulate two hypotheses about possible ways to eliminate certain features from training and classification. We then experimentally verify that the feature reduction significantly improves speed while retaining classification accuracy. Overall, the combination of the two hypotheses leads to a speedup factor of almost ten. The hypotheses are validated on third party synthetic data and also demonstrated on a seven degrees-of-freedom manipulator.

We propose a distributed algorithm enabling a large team of robots to detect all intruders within a large planar environment. Each robot can only detect intruders and communicate with other robots within a limited range. No map of the environment is given, and none is built during the process. Robots are only capable of following walls and other robots that are nearby. The algorithm puts together elementary behaviors giving robots the means to coordinate their movement in order to cover lines between opposite walls with their sensors and discover nearby new walls. A line has leading robots at its endpoints that follow walls and hence move the line of robots forward. Multiple such lines move through the entire assigned area in order to detect all intruders. The movement of multiple lines is coordinated by using a graph representation of the environment that describes possible line movements and their associated costs in terms of robots. This coordination requires only local communication between the leaders of different robot lines when they meet. Finally, we demonstrate how the algorithm can be implemented using elementary wall following and obstacle discovery behaviors.

In this paper we consider the problem of folding deformable objects like cloth or towels. Embracing a simple object model, we present a new algorithm capable of generating collision-free folding motions for two cooperating manipulators. The algorithm encompasses the essential properties of manipulator-independence, parameterized fold quality, and speed. Numerous experiments executed on a real and simulated dual-manipulator robotic torso demonstrate the effectiveness of the presented method.

We present a moving horizon approach for estimating the state of a nonlinear dynamic system that may be subject to inequality constraints. The method takes advantage of a recent smoothing algorithm proposed in the literature based on interior point techniques. The approach exploits the same decomposition used for unconstrained Kalman-Bucy smoothers. Hence, the number of operations required by the algorithm scales linearly with the length of the horizon, making it suitable for online applications. We apply this method to the robot localization problem, showing that it is able to produce much more accurate results than the iterated Kalman filter with little additional computational effort.

We present graph-clear: a novel pursuit-evasion problem on graphs which models the detection of intruders in complex indoor environments by robot teams. The environment is represented by a graph, and a robot team can execute sweep and block actions on vertices and edges, respectively. A sweep action detects intruders in a vertex and represents the capability of the robot team to detect intruders in the region associated to the vertex. Similarly, a block action prevents intruders from crossing an edge and represents the capability to detect intruders as they move between regions. Both actions may require multiple robots to be executed. A strategy is a sequence of block and sweep actions to detect all intruders. When instances of graph-clear are being solved, the goal is to determine optimal strategies, i.e., strategies that use the least number of robots. We prove that for the general case of graphs, the problem of computation of optimal strategies is NP-hard. Next, for the special case of trees, we provide a polynomial-time algorithm. The algorithm ensures that throughout the execution of the strategy, all cleared vertices form a connected subtree, and we show that it produces optimal strategies.

This paper presents HSM3D, an algorithm for global rigid 6DOF alignment of 3D point clouds. The algorithm works by projecting the two input sets into the Radon/Hough domain, whose properties allow to decompose the 6DOF search into a series of fast one-dimensional cross-correlations. No planes or other particular features must be present in the input data, and the algorithm is provably complete in the case of noise-free input. The algorithm has been experimentally validated on publicly available data sets.

This paper introduces a probabilistic model for multirobot surveillance applications with limited range and possibly faulty sensors. Sensors are described with a footprint and a false negative probability, i.e. the probability of failing to report a target within their sensing range. The model implements a probabilistic extension to our formerly developed deterministic approach for modeling surveillance tasks in large environments with large robot teams known as Graph-Clear. This extension leads to a new algorithm that allows to answer new design and performance questions, namely 1) how many robots are needed to obtain a certain confidence that the environment is free from intruders, and 2) given a certain number of robots, how should they coordinate their actions to minimize their failure rate.

We recently introduced HSM3D, an algorithm to solve the six dimensional scan-matching problem without relying on features in the input, and whose solution does not depend on initial guesses. Building upon these new findings, in this manuscript we present a more detailed experimental study of the algorithm we proposed. In particular, we show how to improve the algorithm's performance also when matching point clouds produced by stereo cameras, given that this kind of input invalidates some of the assumptions we formerly identified in order to accelerate HSM3D's performance. We also show that by incorporating color information into the the algorithm it is possible to reduce the number of sporadic outliers in the solution set, thus providing a more reliable algorithm.

We present a system that enables multiple heterogenous mobile robots to build and share an appearance based map appropriate for indoor navigation using exclusively monocular vision. Robots incrementally create online an appearance based model based on SIFT descriptors. The spatial model is enriched with additional information so that the map can be used for navigation also by robots different from those that built it. Once the map is available, navigation is performed using an approach based on epipolar geometry. The control mechanism builds upon the unicycle kinematic model, and assumes robots are equipped with a servoed camera. The validity of the proposed approach is substantiated both in simulation and on an heterogeneous multirobot system.

In this paper we present a method to extract surveillance graphs from occupancy grid maps. Surveillance graphs are part of the graph-clear framework and model the problem of detecting targets using multiple robots with limited range sensors. Robots can only execute basic actions called sweep and block on vertices and edges, respectively. Sweep detects targets in vertices and block prevents them from crossing edges. The extracted graphs accurately model the complexity of the planar environment to be searched, and are constructed as duals of the Voronoi diagram. We give a geometric embedding for blocking and sweeping actions of the graph into the environment by directly associating them to sweep lines that robots cover with their sensors. This paper solves two open problems, namely the generation of surveillance graphs and the implementation of actions on a robot team. Sweep lines can then be directly translated into control inputs to the robot team. The new method is superior to previous heuristics for the extraction of graphs not only through its direct geometric relationship to the environment, but also due to its increased performance in direct experimental comparisons. Additionally, it provides a basis for possible theoretical results regarding the optimal coordination of multiple robots to detect targets in an arbitrary planar environment.

The main contribution of this paper is an improved algorithm for the GRAPH-CLEAR problem, a novel NP-complete graph theoretic problem we recently introduced as a tool to model multi-robot surveillance tasks. The proposed algorithm combines two previously developed solving techniques and produces strategies that require less robots to be executed. We provide a theoretical framework useful to identify the conditions for the existence of an optimal solution under special circumstances, and a set of mathematical tools characterizing the problem being studied. Finally we also identify a set of open questions deserving more investigations.

We present a recently developed algorithm for merging multiple occupancy grid maps computed by multiple robots independently exploring a shared indoor environment. The algorithm exploits the well known Hough transform in a novel way in order to produce a set of ranked roto-translations aimed to overlap the partial maps provided as input. In this paper, after having briefly summarized such method, we investigate the impact on the performance of different variations of the Hough transform. In particular, we are interested in determining the repercussions in terms of accuracy and computational time when only a subset of points is used to compute the transformation. Results are analyzed while merging maps produced by two robots exploring an indoor environment, and also using public available data sets. It turns out that the proposed method is robust and positively influenced by the use of more refined approaches to compute the Hough transform.

This paper presents an experimental validation of an online estimation algorithm we recently investigated theoretically. One of the peculiar characteristics of the approach we propose is the ability to perform an online estimation of the variance parameters that regulate the dynamics of the nonlinear dynamical model used. The approach exploits and extends classical iterated Kalman filtering equations by propagating an approximation of the marginal posterior of the unknown variances over time. The method has been previously used to model and solve a localization task for multiple robots equipped only with a sensor returning mutual distances. In this paper we present a first experimental validation of the algorithm that complements and confirms our initial promising theoretical findings. Our current implementation relies on a sensor returning distance estimates based on a simple image processing algorithm. Such sensor is inherently and intentionally noisy, and in this study we show that our technique is capable of appropriately estimating the variance describing the noise affecting this sensor. We conclude proving experimentally that the procedure we present ensures a performance comparable to similar algorithms that require significantly more a priori information.

GRAPH-CLEAR is a recently introduced theoretical framework to model surveillance tasks accomplished by multiple robots patrolling complex indoor environments. In this paper we provide a first step to close the loop between its graph-based theoretical formulation and practical scenarios. We show how it is possible to algorithmically extract suitable so-called surveillance graphs from occupancy grid maps. We also identify local graph modification operators, called contractions, that alter the graph being extracted so that the original surveillance problem can be solved using less robots. The algorithm we present is based on the generalized Voronoi diagram, a structure that can be simply computed using watershed like algorithms. Our algorithm is evaluated by processing maps produced by mobile robots exploring indoor environments. It turns out that the proposed algorithm is fast, robust to noise, and opportunistically modifies the graph so that less expensive strategies can be computed.

This paper presents USARSim, an open source high fidelity robot simulator that can be used both for research and education. USARSim offers many characteristics that differentiate it from most existing simulators. Most notably, it constitutes the simulation engine used to run the virtual robots competition within the Robocup initiative. We describe its general architecture, describe examples of utilization, and provide a comprehensive overview for those interested in robot simulations for education, research and competitions.

The paper presents a genetic algorithm to find and optimize solutions for nonholonomic motion planning problems. Mainly focusing on mobile robots, the algorithm uses present randomized algorithms to come up with suboptimal paths and iteratively optimizes them according to a fitness function which includes domain specific knowledge. The major advantages of this method include being an any-time algorithm, and improving the quality of the solution throughout the evolutionary process. An extensive experimental analysis comparing our results with state of the art algorithms outline the effectiveness of the proposed methodology.

Different coherence dimensions can be considered to improve the performances of an algorithm for computing collision translations of pairs of convex polyhedra. The algorithm's peculiar approach, based on convex minimization, is well suited to work without initialization and also endowed with an inherently embedded mechanism to exploit spatial coherence in a broader sense than other related approaches usually do. After a brief outline of the algorithm, we summarize the outcomes of several numerical experiments meant to explore extensively the incremental behavior of the algorithm while controlling the coherence parameters. In order to assess the efficacy and the potential of the approach, the performances are also discussed in the light of the results on H-Walk, an algorithm specifically designed to adapt to variable coherence.

In this paper we present a novel graph theoretic problem, called GRAPH-CLEAR, useful to model surveillance tasks where multiple robots are used to detect all possible intruders in a given indoor environment. We provide a formal definition of the problem and we investigate its basic theoretical properties, showing that the problem is NP-complete. We then present an algorithm to compute a strategy for the restriction of the problem to trees and present a method how to use this solution in applications. The method is then tested in simple simulations. GRAPH-CLEAR is useful to describe multirobot pursuit evasion games when robots have limited sensing capabilities, i.e. multiple agents are needed to perform basic patrolling operations.

This paper addresses a largely ignored perspective in multiple robot observation of multiple targets, i.e. that of the evaders. We present a robust distributed approach to target motion control that utilizes cooperation to minimize the average observation time of the evaders. Targets actively communicate with each other to gain a much richer view of the environment than their immediate sensors provide, and use such information to generate better motion decisions from the group viewpoint. Targets relay information coming from other targets to ensure maximal data spread, and cooperate to escape the pursuers in certain favorable situations. Extensive testing has demonstrated the superiority of the approach over other simpler strategies. Furthermore, robustness with respect to key environmental conditions has been evaluated, and the results suggest the algorithm is a good candidate for real-world applications.

The multirobot localization problem is solved in this paper using an innovative approach related to Tikhonov regularization. We release the requirement that robots are equipped with sensors to estimate their own motion, as well as the requirement that covariance matrices describing system and measure noises are perfectly known. Robots are assumed to have a single sensor returning noisy measurements of mutual distances while they move along unknown paths. The proposed algorithm estimates online both the robots’ poses as well as the unknown covariance parameters. In addition to the classical iterations of the well known iterated Kalman filter, we include iterations that propagate an approximation of the posterior marginal densities of the unknown variances. Simulationl results provide evidence that the algorithm is capable of accurately estimating the variances online while at the same time keeping the localization error bounded.

The subject of this paper is an asymptotically fast and incremental algorithm for computing collision translations of convex polyhedra, where the problem at hand is reduced to determining collision translations of pairs of planar sections and minimizing a bivariate convex function. There are two main reasons, in our view, why the algorithm is worth consideration. On the one hand, the addressed proximity measure, namely collision translation, is not as widely studied as distance. On the other, its peculiar computation strategy may be interesting in itself, being well suited to work without initialization and also endowed with an inherently embedded mechanism to exploit spatial coherence. After outlining the main ideas of this novel approach and providing an estimation of the computational costs, we summarize a broad set of numerical experiments meant to explore extensively the behavior of the algorithm, both without and with initialization. Finally, in order to assess the efficacy and the potential of the approach under analysis, the attained performances are contrasted with those of other popular algorithms designed to compute distances between polyhedra. A thorough comparison of the reported query times and, more significantly, of the corresponding trends shows that the behavior of the collision translation algorithm is quite interesting, especially when used without initialization or under variable coherence, which should encourage further work on this approach.

This paper presents a comparative analysis relative to the experimental performances of an asymptotically fast and incremental algorithm, recently developed to compute collision translations for pairs of convex polyhedra. The algorithm may be worth considering because it solves a proximity problem which is less widely addressed than distance, as well as because of its peculiar computation strategy, well suited to work without initialization, but also endowed with an inherently embedded mechanism to exploit spatial coherence. Numerical data characterizing the behavior of the algorithm with respect to the complexity of the polyhedra have already been discussed elsewhere, thus here the main focus is on contrasting its performances with those of two popular algorithms designed to compute distances between polyhedra. Although the considered "yardsticks" answer different proximity queries, and although one of the techniques is meant to deal with general polyhedra, the results presented in this paper should help to assess the efficacy and potential of the approach under analysis. All the three algorithms, indeed, share the same kind of application context; moreover, on the basis of the asymptotic bounds discussed in the literature, distances and collision translations require similar computational efforts. A thorough comparison of the reported query times and, more significantly, of the corresponding trends seems to show that the behavior of the novel algorithm is quite interesting, especially when used without initialization, what should encourage further work on its peculiar approach

This paper presents a behavior-based solution to the problem of observing multiple mobile targets by multiple mobile robots. Robots sense targets using sensors and in addition exchange information about them with other robots. Workload is shared between different robots by requesting help when targets are escaping and supporting robots requesting such help. We provide a detailed description of the proposed solution, as well as significant simulation tests to outline its performance. The described approach outperforms formerly proposed solutions

Mapping can potentially be speeded up in a significant way by using multiple robots exploring different parts of the environment. But the core question of multirobot mapping is how to integrate the data of the different robots into a single global map. A significant amount of research exists in the area of multirobot mapping that deals with techniques to estimate the relative robots poses at the start or during the mapping process. With map merging, the robots in contrast individually build local maps without any knowledge about their relative positions. The goal is then to identify regions of overlap at which the local maps can be joined together. A concrete approach to this idea is presented in form of a special similarity metric and a stochastic search algorithm. Given two maps m and m', the search algorithm transforms m' by rotations and translations to find a maximum overlap between m and m'. In doing so, the heuristic similarity metric guides the search algorithm toward optimal solutions. Results from experiments with up to six robots are presented based on simulated as well as real-world map data

We propose a novel single-shot motion-planning algorithm based on adaptive random walks. The proposed algorithm turns out to be simple to implement, and the solution it produces can be easily and efficiently optimized. Furthermore, the algorithm can incorporate adaptive components, so the developer is not required to specify all the parameters of the random distributions involved, and the algorithm itself can adapt to the environment it is moving in. Proofs of the theoretical soundness of the algorithm are provided, as well as implementation details. Numerical comparisons with well-known algorithms illustrate its effectiveness.

We propose a novel motion planning algorithm based on adaptive random walks. The proposed algorithm turns out to be easy to implement and the solution it produces can be easily and efficiently optimized. Furthermore the algorithm can incorporate adaptive components, so that the developer is not required to specify all the parameters of the random distributions involved, and the algorithm itself can adapt to the environment it is moving in. Proofs of the theoretical soundness of the algorithm are provided as well as implementation details. Numerical comparisons with well known algorithms illustrate its effectiveness.

The cooperative leader following task for multi-robot teams is introduced and discussed. We describe the design and implementation of a distributed technique to coordinate team level and robot level behaviors for this task, as well as a multi-threaded framework for the implementation of a multi-robot system with heterogeneous sensing capabilities. This approach enables robots to remain in formation as they deal with other obstacles that may appear within the formation. We describe how single robot behaviors are realized and scheduled. We show some of the results of the team implementations. The proposed approach has been run and validated on a team of robots performing both in indoor and outdoor environments.