Effective task allocation is an essential component to the coordination of heterogeneous robots. This paper proposes a hybrid task allocation algorithm that improves upon given initial solutions, for example from the popular decentralized market-based allocation algorithm, via a derivative-free optimization strategy called Speeding-Up and Slowing-Down (SUSD). Based on the initial solutions, SUSD performs a search to find an improved task assignment. Unique to our strategy is the ability to apply a gradient-like search to solve a classical integer-programming problem. The proposed strategy outperforms other state-of-the-art algorithms in terms of total task utility and can achieve near optimal solutions in simulation. Experimental results using the Robotarium are also provided.

This paper introduces a game-theoretical approach to the multi-robot task allocation problem, where each robot is considered as self-interested and cannot share its personal utility functions. We consider the case where each robot can execute multiple tasks and each task requires only one robot. For real-world applications with mobile robots, we design a utility function that includes both assignment conflict penalties and path-dependent execution cost. For a robot to maximize its own utility, it needs to select a subset of conflict-free tasks that minimizes its total travel distance. Our approaches utilize a consensus communication scheme to share robots' task selection and the Speeding-Up and Slowing-Down (SUSD) strategy to search in a combinatorial action (task selection) space for a subset of tasks that can achieve a higher utility at each iteration. The SUSD strategy can perform a gradient-like search without calculating the derivatives, which allows robots to improve upon their current task selections. Simulation results show that robots using the proposed algorithms can successfully find Nash equilibria for effective coordination.

We propose a memory-constrained partition-based method to extract symbolic representations of the belief state and its dynamics in order to solve planning problems in a partially observable Markov decision process (POMDP). Our K-means partitioning strategy uses a fixed number of symbols to represent the partitions of the belief space and ensures the parameterization of the belief dynamics does not grow exponentially as the system dimension increases. By casting our problem as a partitioning of the POMDP, we can then solve planning problems using traditional symbolic planning solvers (such as HTN or A* solvers). Our work is motivated by an autonomous underwater vehicle navigation problem where the vehicle is affected by uncertain flow conditions and receives severely limited position observations. Simulation experiments are provided to validate the performance of the proposed algorithms.

This paper proposes a distributed field mapping algorithm that drives a team of robots to explore and learn an unknown scalar field. The algorithm is based on a bio-inspired approach known as Speeding-Up and Slowing-Down (SUSD) for distributed source seeking problems. Our algorithm leverages a Gaussian Process model to predict field values as robots explore. By comparing Gaussian Process predictions with measurements of the field, agents search along the gradient of the model error while simultaneously improving the Gaussian Process model. We provide a proof of convergence to the gradient direction and demonstrate our approach in simulation and experiments using 2D wheeled robots and 2D flying autonomous miniature blimps.

Modern unmanned aerial vehicles (UAVs) rely on constant periodic sensor measurements to detect and avoid obstacles. However, constant checking and replanning are time and energy consuming and are often not necessary especially in situations in which the UAV can safely fly in uncluttered environments without entering unsafe states. Thus, in this paper, we propose a self-triggered framework that leverages reachability analysis to schedule the next time to check sensor measurements and perform replanning while guaranteeing safety under noise and disturbance effects. Further, we relax sensor checking and motion replanning operations by leveraging a risk-based analysis that determines the likelihood to reach undesired states over a certain time horizon. We also propose an online speed adaptation policy based on the planned trajectory curvature to minimize drift from the desired path due to the system dynamics. Finally, we validate the proposed approach with simulations and experiments for a quadrotor UAV motion planning case study in a cluttered environment.