Publications

2024

J56. Reducing the Minimal Fleet Size by Delaying Individual Tasks
Maximilian Kronmueller, Andres Fielbaum, Javier Alonso-Mora. In IEEE Transactions on Intelligent Transportation Systems, 2024.

pdf web
This work formally defines the problem of fleet sizing with delays (FSD), where the option of delaying individual tasks within fleet sizing is considered. We prove that the FSD problem is NP-hard and solve a formulation of the FSD problem as a mixed integer linear problem (MILP). We then analyze the proposed method in detail in an abstract case and validate it in a case study of taxi rides in Manhattan. We show that fleet sizes can be decreased significantly and that the trade-off space of the number of required vehicles to execution time and added delay can be enlarged.

J55. Statistically Distinct Plans for Multi-Objective Task Assignment
Nils Wilde, Javier Alonso-Mora. In IEEE Transaction on Robotics(T-RO), 2024.

pdf
We study the problem of finding statistically distinct plans for stochastic task assignment problems such as online multi-robot pickup and delivery (MRPD) when facing multiple competing objectives. In many real-world settings robot fleets do not only need to fulfil delivery requests, but also have to consider auxiliary objectives such as energy efficiency or avoiding human-centered work spaces. We pose MRPD as a multi-objective optimization problem where the goal is to find MRPD policies that yield different trade-offs between given objectives. There are two main challenges: 1) MRPD is computationally hard, which limits the number of trade-offs that can reasonably be computed, and 2) due to the random task arrivals, one needs to consider statistical variance of the objective values in addition to the average. We present an adaptive sampling algorithm that finds a set of policies which i) are approximately optimal, ii) approximate the set of all optimal solutions, and iii) are statistically distinguishable. We prove completeness and adapt a state-of-the-art MRPD solver to the multi-objective setting for three example objectives. In a series of simulation experiments we demonstrate the advantages of the proposed method compared to baseline approaches and show its robustness in a sensitivity analysis. The approach is general and could be adapted to other multi-objective task assignment and planning problems under uncertainty.

J54. Scalarizing Multi-Objective Robot Planning Problems Using Weighted Maximization
Nils Wilde, Stephen L. Smith, Javier Alonso-Mora. In IEEE Robotics and Automation Letters (RA-L), 2024.

pdf
When designing a motion planner for autonomous robots there are usually multiple objectives to be considered. However, a cost function that yields the desired trade-off between objectives is not easily obtainable. A common technique across many applications is to use a weighted sum of relevant objective functions and then carefully adapt the weights. However, this approach may not find all relevant trade-offs even in simple planning problems. Thus, we study an alternative method based on a weighted maximum of objectives. Such a cost function is more expressive than the weighted sum, and we show how it can be deployed in both continuous- and discrete-space motion planning problems. We propose a novel path planning algorithm for the proposed cost function and establish its correctness, and present heuristic adaptations that yield a practical runtime. In extensive simulation experiments, we demonstrate that the proposed cost function and algorithm are able to find a wider range of trade-offs between objectives (i.e., Pareto-optimal solutions) for various planning problems, showcasing its advantages in practice.

J53. Contingency Games for Multi-Agent Interaction
Lasse Peters, Andrea Bajcsy, Chih-Yuan Chiu, David Fridovich-Keil, Forrest Laine, Laura Ferranti, Javier Alonso-Mora. In Robotics and Automation Letters (RA-L), 2024.

pdf web video
Contingency planning, wherein an agent generates a set of possible plans conditioned on the outcome of an uncertain event, is an increasingly popular way for robots to act under uncertainty. In this work we take a game-theoretic perspective on contingency planning, tailored to multi-agent scenarios in which a robot’s actions impact the decisions of other agents and vice versa. The resulting contingency game allows the robot to efficiently interact with other agents by generating strategic motion plans conditioned on multiple possible intents for other actors in the scene. Contingency games are parameterized via a scalar variable which represents a future time when intent uncertainty will be resolved. By estimating this parameter online, we construct a game-theoretic motion planner that adapts to changing beliefs while anticipating future certainty. We show that existing variants of game-theoretic planning under uncertainty are readily obtained as special cases of contingency games. Through a series of simulated autonomous driving scenarios, we demonstrate that contingency games close the gap between certainty-equivalent games that commit to a single hypothesis and non-contingent multi-hypothesis games that do not account for future uncertainty reduction.
paper image

O1. Auto-Encoding Bayesian Inverse Games
Xinjie Liu, Lasse Peters, Javier Alonso-Mora, Ufuk Topcu, David Fridovich-Keil. In arxiv preprint arxiv:2402.08902, 2024.

pdf web
When multiple agents interact in a common environment, each agent's actions impact others' future decisions, and noncooperative dynamic games naturally capture this coupling. In interactive motion planning, however, agents typically do not have access to a complete model of the game, e.g., due to unknown objectives of other players. Therefore, we consider the inverse game problem, in which some properties of the game are unknown a priori and must be inferred from observations. Existing maximum likelihood estimation (MLE) approaches to solve inverse games provide only point estimates of unknown parameters without quantifying uncertainty, and perform poorly when many parameter values explain the observed behavior. To address these limitations, we take a Bayesian perspective and construct posterior distributions of game parameters. To render inference tractable, we employ a variational autoencoder (VAE) with an embedded differentiable game solver. This structured VAE can be trained from an unlabeled dataset of observed interactions, naturally handles continuous, multi-modal distributions, and supports efficient sampling from the inferred posteriors without computing game solutions at runtime. Extensive evaluations in simulated driving scenarios demonstrate that the proposed approach successfully learns the prior and posterior game parameter distributions, provides more accurate objective estimates than MLE baselines, and facilitates safer and more efficient game-theoretic motion planning.

2023

J52. Continuous Occupancy Mapping in Dynamic Environments Using Particles
G. Chen, W. Dong, P. Peng, J. Alonso-Mora, X. Zhu. In IEEE Transactions on Robotics (TRO), 2023.

pdf
Abstract: Particle-based dynamic occupancy maps were proposed in recent years to model the obstacles in dynamic environments. Current particle-based maps describe the occupancy status in discrete grid form and suffer from the grid size problem, wherein a large grid size is unfavorable for motion planning, while a small grid size lowers efficiency and causes gaps and inconsistencies. To tackle this problem, this paper generalizes the particle-based map into continuous space and builds an efficient 3D egocentric local map. A dual-structure subspace division paradigm, composed of a voxel subspace division and a novel pyramid-like subspace division, is proposed to propagate particles and update the map efficiently with the consideration of occlusions. The occupancy status of an arbitrary point in the map space can then be estimated with the particles' weights. To further enhance the performance of simultaneously modeling static and dynamic obstacles and minimize noise, an initial velocity estimation approach and a mixture model are utilized. Experimental results show that our map can effectively and efficiently model both dynamic obstacles and static obstacles. Compared to the state-of-the-art grid-form particle-based map, our map enables continuous occupancy estimation and substantially improves the performance in different resolutions.

J51. Learning scalable and efficient communication policies for multi-robot collision avoidance
Álvaro Serra-Gómez, Hai Zhu, Bruno Brito, Wendelin Böhmer, Javier Alonso-Mora. In Autonomous Robots 47, 1275-1297, 2023.

web pdf
Decentralized multi-robot systems typically perform coordinated motion planning by constantly broadcasting their intentions to avoid collisions. However, the risk of collision between robots varies as they move and communication may not always be needed. This paper presents an efficient communication method that addresses the problem of “when” and “with whom” to communicate in multi-robot collision avoidance scenarios. In this approach, each robot learns to reason about other robots’ states and considers the risk of future collisions before asking for the trajectory plans of other robots. We introduce a new neural architecture for the learned communication policy which allows our method to be scalable. We evaluate and verify the proposed communication strategy in simulation with up to twelve quadrotors, and present results on the zero-shot generalization/robustness capabilities of the policy in different scenarios. We demonstrate that our policy (learned in a simulated environment) can be successfully transferred to real robots.

J50. Online flash delivery from multiple depots
M. Kronmuller, A. Fielbaum, J. Alonso-Mora. In Transportation Letters, 2023.

web pdf
Abstract: We study routing for on-demand last-mile logistics with two crucial novel features: i) Multiple depots, optimizing where to pick-up every order, ii) Allowing vehicles to perform depot returns prior to being empty, thus adapting their routes to include new orders online. Both features result in shorter distances and more agile planning.We propose a scalable dynamic method to deliver orders as fast as possible. Following a rolling horizon approach, each time step the following is executed. First, define potential pick-up locations and identify which groups of orders can be transported together, with which vehicle and following which route. Then, decide which of these potential groups of orders will be executed and by which vehicle by solving an integer linear program. We simulate one day of service in Amsterdam that considers 10,000 requests, compare results to several strategies and test different scenarios. Results underpin the advantages of the proposed method.

J49. Optimizing Task Waiting Times in Dynamic Vehicle Routing
A. Botros, B. Gilhuly, N. Wilde, A. Sadeghi, J. Alonso-Mora, S. L Smith. In IEEE Robotics and Automation Letters (RA-L), 2023.

pdf
Abstract: We study the problem of deploying a fleet of mobile robots to service tasks that arrive stochastically over time and at random locations in an environment. This is known as the Dynamic Vehicle Routing Problem (DVRP) and requires robots to allocate incoming tasks among themselves and find an optimal sequence for each robot. State-of-the-art approaches only consider average wait times and focus on high-load scenarios where the arrival rate of tasks approaches the limit of what can be handled by the robots while keeping the queue of unserviced tasks bounded, i.e., stable. To ensure stability, these approaches repeatedly compute minimum distance tours over a set of newly arrived tasks. This letter is aimed at addressing the missing policies for moderate-load scenarios, where quality of service can be improved by prioritizing long-waiting tasks. We introduce a novel DVRP policy based on a cost function that takes the p-norm over accumulated wait times and show it guarantees stability even in high-load scenarios. We demonstrate that the proposed policy outperforms the state-of-the-art in both mean and 95th percentile wait times in moderate-load scenarios through simulation experiments in the Euclidean plane as well as using real-world data for city scale service requests.

J48. Online and offline learning of player objectives from partial observations in dynamic games
L. Peters, V Rubies-Royo, C. J. Tomlin, L. Ferranti, J. Alonso-Mora, C. Stachniss, D. Fridovich-Keil. In The International Journal of Robotics Research (IJRR), 2023.

pdf web
Abstract: Robots deployed to the real world must be able to interact with other agents in their environment. Dynamic game theory provides a powerful mathematical framework for modeling scenarios in which agents have individual objectives and interactions evolve over time. However, a key limitation of such techniques is that they require a priori knowledge of all players’ objectives. In this work, we address this issue by proposing a novel method for learning players’ objectives in continuous dynamic games from noise-corrupted, partial state observations. Our approach learns objectives by coupling the estimation of unknown cost parameters of each player with inference of unobserved states and inputs through Nash equilibrium constraints. By coupling past state estimates with future state predictions, our approach is amenable to simultaneous online learning and prediction in receding horizon fashion. We demonstrate our method in several simulated traffic scenarios in which we recover players’ preferences, for, e.g. desired travel speed and collision-avoidance behavior. Results show that our method reliably estimates game-theoretic models from noise-corrupted data that closely matches ground-truth objectives, consistently outperforming state-of-the-art approaches.

J47. Economies and diseconomies of scale in on-demand ridepooling systems
A. Fielbaum, A. Tirachini, J. Alonso-Mora. In Economics of Transportation, 2023.

pdf
Abstract: We analyse the sources of economies and diseconomies of scale in On-Demand Ridepooling (ODRP), disen- tangling three effects: when demand grows, average costs are reduced due to i) a larger fleet that diminishes waiting and walking times (Mohring Effect), and ii) matching users with more similar routes (Better-matching Effect). A counter-balance force (Extra-detour Effect), occurs when iii) the number of passengers per vehicle in- creases and users face longer detours. At low demand levels, there is little sharing and the Mohring effect pre- vails; as demand grows, more passengers per vehicle push for the Extra-detour Effect to dominate; eventually, vehicles run at capacity, and the Better-matching Effect prevails. The last two effects are specific to ODRP as the routes are not fixed but adapted online. Our simulations show that considering both users’ and operators’ costs, scale economies prevail, and that ODRP with human-driven vehicles and walks allowed has total costs similar to door-to-door systems with driverless vehicles.

J46. Active Classification of Moving Targets with Learned Control Policies
A Serra-Gomez, E Montijano, W Boehmer, J. Alonso-Mora. In IEEE Robotics and Automation Letters (RA-L), 2023.

pdf
Abstract: WIn this paper, we consider the problem where a drone has to collect semantic information to classify multiple moving targets. In particular, we address the challenge of computing control inputs that move the drone to informative viewpoints, position and orientation, when the information is extracted using a “black-box” classifier, e.g., a deep learning neural network. These algorithms typically lack of analytical relationships between the viewpoints and their associated out- puts, preventing their use in information-gathering schemes. To fill this gap, we propose a novel attention-based architecture, trained via Reinforcement Learning (RL), that outputs the next viewpoint for the drone favoring the acquisition of evidence from as many unclassified targets as possible while reasoning about their movement, orientation, and occlusions. Then, we use a low-level MPC controller to move the drone to the desired viewpoint taking into account its actual dynamics. We show that our approach not only outperforms a variety of baselines but also generalizes to scenarios unseen during training. Additionally, we show that the network scales to large numbers of targets and generalizes well to different movement dynamics of the targets.

J45. Ride-pooling adoption, efficiency and level of service under alternative demand, behavioural and pricing settings
A. de Ruijter, O. Cats, J. Alonso-Mora, S. Hoogendoorn. In Transportation Planning and Technology, 2023.

pdf
Abstract: Previous studies into the potential benefits of ride pooling failed to account for the trade-off that users likely make when considering a shared ride. We address this shortcoming by formulating user net benefit stemming from pooling as a compensatory function where the additional travel time and on-board discomfort need to be compensated by the price discount for a traveller to choose a pooled ride over a private ride. The proposed formulation is embedded in a method for matching travel requests and vehicles. We conduct a series of experiments investigating how the potential of ride-pooling services depends on demand characteristics, user preferences and the pricing policy adopted by the service provider. Our results suggest that the total vehicle mileage savings found by previous studies is only attainable when users are very willing to share their ride (i.e. attach low premium to private rides) and are offered a 50% discount for doing so.

J44. Learning to Play Trajectory Games Against Opponents with Unknown Objectives
X. Liu, L. Peters, J. Alonso-Mora. In IEEE Robotics and Automation Letters (RA-L), 2023.

web pdf video
Abstract: Many autonomous agents, such as intelligent ve- hicles, are inherently required to interact with one another. Game theory provides a natural mathematical tool for robot motion planning in such interactive settings. However, tractable algorithms for such problems usually rely on a strong assumption, namely that the objectives of all players in the scene are known. To make such tools applicable for ego-centric planning with only local information, we propose an adaptive model-predictive game solver, which jointly infers other players’ objectives online and computes a corresponding generalized Nash equilibrium (GNE) strategy. The adaptivity of our approach is enabled by a differentiable trajectory game solver whose gradient signal is used for maximum likelihood estimation (MLE) of opponents’ objectives. This differentiability of our pipeline facilitates direct integration with other differentiable elements, such as neural networks (NNs). Furthermore, in contrast to existing solvers for cost inference in games, our method handles not only partial state observations but also general inequality constraints. In two simulated traffic scenarios, we find superior performance of our approach over both existing game-theoretic methods and non- game-theoretic model-predictive control (MPC) approaches. We also demonstrate our approach’s real-time planning capabilities and robustness in two-player hardware experiments.

J43. Dynamic Optimization Fabrics for Motion Generation
M. Spahn, M. Wisse, J. Alonso-Mora. In IIEEE Transactions on Robotics (T-RO), 2023.

pdf code
Abstract: Optimization fabrics are a geometric approach to real-time local motion generation, where motions are designed by the composition of several differential equations that exhibit a desired motion behavior. We generalize this framework to dynamic scenarios and nonholonomic robots and prove that fundamental properties can be conserved. We show that convergence to desired trajectories and avoidance of moving obstacles can be guaranteed using simple construction rules of the components. In addition, we present the first quantitative comparisons between optimization fabrics and model predictive control and show that optimization fabrics can generate similar trajectories with better scalability, and thus, much higher replanning frequency (up to 500 Hz with a 7 de- grees of freedom robotic arm). Finally, we present empirical results on several robots, including a nonholonomic mobile manipulator with 10 degrees of freedom and avoidance of a moving human, supporting the theoretical findings.

J42. RAST: Risk-Aware Spatio-Temporal Safety Corridors for MAV Navigation in Dynamic Uncertain Environments
G. Chen, S. Wu, M. Shi, W. Dong, H. Zhu, J. Alonso-Mora. In IEEE Robotics and Automation Letters (RA-L), 2023.

pdf code
Abstract: Autonomous navigation of Micro Aerial Vehicles (MAVs) in dynamic and unknown environments is a complex and challenging task. Current works rely on assumptions to solve the problem. The MAV’s pose is precisely known, the dynamic obstacles can be explicitly segmented from static ones, their number is known and fixed, or they can be modeled with given shapes. In this paper, we present a method for MAV navigation in dynamic uncertain environments without making any of these assumptions. The method employs a particle-based dynamic map to represent the local environment and predicts it to the near future. Collision risk is defined based on the predicted maps and a series of risk-aware spatio-temporal (RAST) safety corridors are constructed, which are finally used to optimize a dynamically- feasible collision-free trajectory for the MAV. We compared our method with several state-of-the-art works in 12000 simulation tests in Gazebo with the physical engine enabled. The results show that our method has the highest success rate at different uncertainty levels. Finally, we validated the proposed method in real experiments.

C68. Interaction-Aware Sampling-Based MPC with Learned Local Goal Predictions
W. Jansma, E. Trevisan, Á. Serra-Gómez, J. Alonso-Mora. In Proc. IEEE International Symposium on Multi-Robot and Multi-Agent Systems, 2023.

pdf web Data, Model, Code and video
Abstract: Motion planning for autonomous robots in tight, interaction-rich, and mixed human-robot environments is challenging. State-of-the-art methods typically separate prediction and planning, predicting other agents' trajectories first and then planning the ego agent's motion in the remaining free space. However, agents' lack of awareness of their influence on others can lead to the freezing robot problem. We build upon Interaction-Aware Model Predictive Path Integral (IA-MPPI) control and combine it with learning-based trajectory predictions, thereby relaxing its reliance on communicated short-term goals for other agents. We apply this framework to Autonomous Surface Vessels (ASVs) navigating urban canals. By generating an artificial dataset in real sections of Amsterdam's canals, adapting and training a prediction model for our domain, and proposing heuristics to extract local goals, we enable effective cooperation in planning. Our approach improves autonomous robot navigation in complex, crowded environments, with potential implications for multi-agent systems and human-robot interaction.
paper image

C67. Designing Heterogeneous Robot Fleets for Task Allocation and Sequencing
N. Wilde, J. Alonso-Mora. In Proc. IEEE International Symposium on Multi-Robot and Multi-Agent Systems (MRS), 2023.

pdf
Abstract: We study the problem of selecting a fleet of robots to service spatially distributed tasks with diverse requirements within time-windows. The problem of allocating tasks to a fleet of potentially heterogeneous robots and finding an optimal sequence for each robot is known as multi-robot task assignment (MRTA). Most state-of-the-art methods focus on the problem when the fleet of robots is fixed. In contrast, we consider that we are given a set of available robot types and requested tasks, and need to assemble a fleet that optimally services the tasks while the cost of the fleet remains under a budget limit. We characterize the complexity of the problem and provide a Mixed-Integer Linear Program (MILP) formulation. Due to poor scalability of the MILP, we propose a heuristic solution based on a Large Neighbourhood Search (LNS). In simulations, we demonstrate that the proposed method requires substantially lower budgets than a greedy algorithm to service all tasks.

C66. Multi-Robot Local Motion Planning Using Dynamic Optimization Fabrics
S. Bakker, L. Knoedler, M. Spahn, W. Böhmer, J. Alonso-Mora. In Proc. IEEE International Symposium on Multi-Robot and Multi-Agent Systems, 2023.

pdf code video
Abstract: In this paper, we address the problem of real-time motion planning for multiple robotic manipulators that operate in close proximity. We build upon the concept of dynamic fabrics and extend them to multi-robot systems, referred to as Multi-Robot Dynamic Fabrics (MRDF). This geometric method enables a very high planning frequency for high-dimensional systems at the expense of being reactive and prone to deadlocks. To detect and resolve deadlocks, we propose Rollout Fabrics where MRDF are forward simulated in a decentralized manner. We validate the methods in simulated close-proximity pick-and-place scenarios with multiple manipulators, showing high success rates and real-time performance.

C65. Reinforcement Learning from Simulation to Real World Autonomous Driving using Digital Twin
K. L. Voogd, J. P. Allamaa, J. Alonso-Mora, T. Son. In IFAC World Congress, 2023.

pdf
Abstract: Reinforcement learning (RL) is a promising solution for autonomous vehicles to deal with complex and uncertain traffic environments. The RL training process is however expensive, unsafe, and time-consuming. Algorithms are often developed first in simulation and then transferred to the real-world, leading to a common sim2real challenge where performance decreases when the domain changes. In this paper, we propose a transfer learning process to minimize the gap by exploiting digital twin technology, relying on a systematic and simultaneous combination of virtual and real world data coming from vehicle dynamics and traffic scenarios. The model and testing environment is evolved from model, hardware to vehicle in the loop and proving ground testing stages, similar to standard development cycle in the automotive industry. In particular, we also integrate other transfer learning techniques such as domain randomization and adaptation in each stage. The simulation and real data are gradually incorporated to accelerate and make the transfer learning process more robust. The proposed RL methodology is applied to develop a path-following steering controller for an autonomous electric vehicle. After learning and deploying the real-time RL control policy on the vehicle, we obtained satisfactory and safe control performance already from the first deployment, demonstrating the advantages of the proposed digital twin based learning process.

C64. A Framework for Fast Prototyping of Photo-realistic Environments with Multiple Pedestrians
S. Casao, A. Otero, A. Serra-Gomez, AC. Murillo, J. Alonso-Mora, E. Montijano. In , in IEEE Int. Conf. on Robotics and Automation (ICRA), 2023.

pdf
Abstract: Robotic applications involving people often re- quire advanced perception systems to better understand com- plex real-world scenarios. To address this challenge, photo- realistic and physics simulators are gaining popularity as a means of generating accurate data labeling and designing scenarios for evaluating generalization capabilities, e.g., lighting changes, camera movements or different weather conditions. We develop a photo-realistic framework built on Unreal Engine and AirSim to generate easily scenarios with pedestrians and mobile robots. The framework is capable to generate random and customized trajectories for each person and provides up to 50 ready-to-use people models along with an API for their metadata retrieval. We demonstrate the usefulness of the proposed framework with a use case of multi-target tracking, a popular problem in real pedestrian scenarios. The notable feature variability in the obtained perception data is presented and evaluated.

C63. Wi-Closure: Reliable and Efficient Search of Inter-Robot Loop Closures Using Wireless Sensing
W. Wang, A. Kemmeren, D. Son, J. Alonso-Mora, S. Gil. In IEEE Int. Conf. on Robotics and Automation (ICRA), 2023.

pdf
Abstract: In this paper we propose a novel algorithm, Wi- Closure, to improve the computational efficiency and robustness of loop closure detection in multi-robot SLAM. Our approach decreases the computational overhead of classical approaches by pruning the search space of potential loop closures, prior to evaluation by a typical multi-robot SLAM pipeline. Wi-Closure achieves this by identifying candidates that are spatially close to each other measured via sensing over the wireless commu- nication signal between robots, even when they are operating in non-line-of-sight or in remote areas of the environment from one another. We demonstrate the validity of our approach in simulation and in hardware experiments. Our results show that using Wi-closure greatly reduces computation time, by 54.1% in simulation and 76.8% in hardware experiments, compared with a multi-robot SLAM baseline. Importantly, this is achieved without sacrificing accuracy. Using Wi-closure reduces absolute trajectory estimation error by 98.0% in simulation and 89.2% in hardware experiments. This improvement is partly due to Wi-Closure’s ability to avoid catastrophic optimization failure that typically occurs with classical approaches in challenging repetitive environments.

C62. Autotuning Symbolic Optimization Fabrics for Trajectory Generation
M. Spahn, J. Alonso-Mora. In IEEE Int. Conf. on Robotics and Automation (ICRA), 2023.

pdf code
Abstract: In this paper, we present an automated parameter optimization method for trajectory generation. We formulate parameter optimization as a constrained optimization problem that can be effectively solved using Bayesian optimization. While the approach is generic to any trajectory generation method, we showcase it using optimization fabrics. Optimiza- tion fabrics are a geometric trajectory generation method based on non-Riemannian geometry. By symbolically pre-solving the structure of the tree of fabrics, we obtain a parameterized trajectory generator, called symbolic fabrics. We show that autotuned symbolic fabrics reach expert-level performance in a few trials. Additionally, we show that tuning transfers across different robots, motion planning problems and between sim- ulation and real world. Finally, we qualitatively showcase that the framework could be used for coupled mobile manipulation.

C61. Probabilistic Risk Assessment for Chance-Constrained Collision Avoidance in Uncertain Dynamic Environments
K. Mustafa, O. de Groot, X. Wang, J. Kober, J. Alonso-Mora. In , in IEEE Int. Conf. on Robotics and Automation (ICRA), 2023.

pdf
Abstract: Balancing safety and efficiency when planning in crowded scenarios with uncertain dynamics is challenging where it is imperative to accomplish the robot’s mission without incurring any safety violations. Typically, chance constraints are incorporated into the planning problem to provide probabilistic safety guarantees by imposing an upper bound on the collision probability of the planned trajectory. Yet, this results in overly conservative behavior on the grounds that the gap between the obtained risk and the specified upper limit is not explicitly restricted. To address this issue, we propose a real-time capable approach to quantify the risk associated with planned trajec- tories obtained from multiple probabilistic planners, running in parallel, with different upper bounds of the acceptable risk level. Based on the evaluated risk, the least conservative plan is selected provided that its associated risk is below a specified threshold. In such a way, the proposed approach provides probabilistic safety guarantees by attaining a closer bound to the specified risk, while being applicable to generic uncertainties of moving obstacles. We demonstrate the efficiency of our proposed approach, by improving the performance of a state- of-the-art probabilistic planner, in simulations and experiments using a mobile robot in an environment shared with humans.

C60. Globally Guided Trajectory Planning in Dynamic Environments
O. de Groot, L. Ferranti, D. Gavrila, J. Alonso-Mora. In IEEE Int. Conf. on Robotics and Automation (ICRA), 2023.

pdf video
Abstract: Navigating mobile robots through environments shared with humans is challenging. From the perspective of the robot, humans are dynamic obstacles that must be avoided. These obstacles make the collision-free space nonconvex, which leads to two distinct passing behaviors per obstacle (passing left or right). For local planners, such as receding-horizon trajectory optimization, each behavior presents a local optimum in which the planner can get stuck. This may result in slow or unsafe motion even when a better plan exists. In this work, we identify trajectories for multiple locally optimal driving behaviors, by considering their topology. This identification is made consistent over successive iterations by propagating the topology information. The most suitable high-level trajectory guides a local optimization-based planner, resulting in fast and safe motion plans. We validate the proposed planner on a mobile robot in simulation and real-world experiments.

C59. Multi-Agent Path Integral Control for Interaction-Aware Motion Planning in Urban Canals
L. Streichenberg, E. Trevisan, J. J. Chung, R. Siegwart, J. Alonso-Mora. In , in IEEE Int. Conf. on Robotics and Automation (ICRA), 2023.

pdf
Abstract: Autonomous vehicles that operate in urban envi- ronments shall comply with existing rules and reason about the interactions with other decision-making agents. In this paper, we introduce a decentralized and communication-free interaction-aware motion planner and apply it to Autonomous Surface Vessels (ASVs) in urban canals. We build upon a sampling-based method, namely Model Predictive Path Integral control (MPPI), and employ it to, in each time instance, compute both a collision-free trajectory for the vehicle and a prediction of other agents’ trajectories, thus modeling inter- actions. To improve the method’s efficiency in multi-agent sce- narios, we introduce a two-stage sample evaluation strategy and define an appropriate cost function to achieve rule compliance. We evaluate this decentralized approach in simulations with multiple vessels in real scenarios extracted from Amsterdam’s canals, showing superior performance than a state-of-the- art trajectory optimization framework and robustness when encountering different types of agents.

W9. Sampling-Based MPC Using a GPU-parallelizable Physics Simulator as Dynamic Model: an Open Source Implementation with IsaacGym
C. Pezzato, C. Salmi, E. Trevisan, J. Alonso-Mora, C. Hernández Corbato. In Embracing Contacts Workshop at IEEE Int. Conf. on Robotics and Automation (ICRA), 2023.

pdf Code Web
Abstract: We present a method for solving finite horizon optimal control problems using a generic physics simulator as the dynamical model. In particular, we present an open-source implementation of a model predictive path integral controller (MPPI), that uses the GPU-parallelizable IsaacGym simulator as the dynamical model to compute the forward dynamics of the system. This allows one to effortlessly solve complex contact-rich tasks such as for example, non-prehensile manipulation of a variety of objects, or picking with a mobile manipulator. Since there is no explicit dynamic modeling required from a user, the repository is easily extendable to different objects and robots, as we show in the experiments section. This makes this method a powerful and accessible tool to solve a large variety of contact-rich tasks.

W8. TrajFlow: Learning the Distribution over Trajectories
A. Meszaros, J. Alonso-Mora, J. Kober. In 5th Workshop on Long-term Human Motion Prediction at IEEE Int. Conf. on Robotics and Automation (ICRA), 2023.

pdf
Abstract: Predicting the future behaviour of people re- mains an open challenge for the development of risk-aware autonomous vehicles. An important aspect of this challenge is effectively capturing the uncertainty inherent to human behaviour. This paper studies an approach for multi-modal probabilistic motion forecasting of an agent with improved accuracy in the predicted sample likelihoods. Our approach achieves state-of-the-art results on the inD dataset when evalu- ated with the standard metrics employed for motion forecasting. Furthermore, our approach also achieves state-of-the-art results when evaluated with respect to the likelihoods it assigns to its generated trajectories. Evaluations on artificial datasets indicate that the distributions learned by our model closely correspond to the true distributions observed in data and are not as prone to being over-confident in a single outcome in the face of uncertainty.

2022

J41. Visually-Guided Motion Planning for Autonomous Driving from Interactive Demonstrations
R. Perez-Dattari, B. Brito, O. de Groot, J. Kober, J. Alonso-Mora. In IFAC Engineering Applications of Artificial Intelligence Journal, 2022.

web pdf code video
Abstract: The successful integration of autonomous robots in real-world environments strongly depends on their ability to reason from context and take socially acceptable actions. Current autonomous navigation systems mainly rely on geometric information and hard-coded rules to induce safe and socially compliant behaviors. Yet, in unstructured urban scenarios these approaches can become costly and suboptimal. In this paper, we introduce a motion planning framework consisting of two components: a data-driven policy that uses visual inputs and human feedback to generate socially compliant driving behaviors (encoded by high-level decision variables), and a local trajectory optimization method that executes these behaviors (ensuring safety). In particular, we employ Interactive Imitation Learning to jointly train the policy with the local planner, a Model Predictive Controller (MPC), which results in safe and human-like driving behaviors. Our approach is validated in realistic simulated urban scenarios. Qualitative results show the similarity of the learned behaviors with human driving. Furthermore, navigation performance is substantially improved in terms of safety, i.e., number of collisions, as compared to prior trajectory optimization frameworks, and in terms of data-efficiency as compared to prior learning-based frameworks, broadening the operational domain of MPC to more realistic autonomous driving scenarios.

J40. Distributed Nonlinear Trajectory Optimization for Multi-Robot Motion Planning
L. Ferranti, L. Lyons, R. R. Negenborn, T. Keviczky, J. Alonso-Mora. In IEEE Transactions on Control Systems Technology (T-CST), 2022.

web pdf video
Abstract: This work presents a method for multi-robot coordination based on a novel distributed nonlinear model predictive control (NMPC) formulation for trajectory optimization and its modified version to mitigate the effects of packet losses and delays in the communication among the robots. Our algorithms consider that each robot is equipped with an onboard computation unit to solve a local control problem and communicate with neighboring autonomous robots via a wireless network. The difference between the two proposed methods is in the way the robots exchange information to coordinate. The information exchange can occur in a following: 1) synchronous or 2) asynchronous fashion. By relying on the theory of the nonconvex alternating direction method of multipliers (ADMM), we show that the proposed solutions converge to a (local) solution of the centralized problem. For both algorithms, the communication exchange preserves the safety of the robots; that is, collisions with neighboring autonomous robots are prevented. The proposed approaches can be applied to various multi-robot scenarios and robot models. In this work, we assess our methods, both in simulation and with experiments, for the coordination of a team of autonomous vehicles in the following: 1) an unsupervised intersection crossing and 2) the platooning scenarios.

J39. Group-based Distributed Auction Algorithms for Multi-Robot Task Assignment
X. Bai, A. Fielbaum, M. Kronmuller, L. Knoedler, J. Alonso-Mora. In IEEE Transactions on Automation Science and Engineering (T-ASE), 2022.

web pdf
Abstract: This paper studies the multi-robot task assignment problem in which a fleet of dispersed robots needs to efficiently transport a set of dynamically appearing packages from their initial locations to corresponding destinations within prescribed time-windows. Each robot can carry multiple packages simultaneously within its capacity. Given a sufficiently large robot fleet, the objective is to minimize the robots' total travel time to transport the packages within their respective time-window constraints. The problem is shown to be NP-hard, and we design two group-based distributed auction algorithms to solve this task assignment problem. Guided by the auction algorithms, robots first distributively calculate feasible package groups that they can serve, and then communicate to find an assignment of package groups. We quantify the potential of the algorithms with respect to the number of employed robots and the capacity of the robots by considering the robots' total travel time to transport all packages. Simulation results show that the designed algorithms are competitive compared with an exact centralized Integer Linear Program representation solved with the commercial solver Gurobi, and superior to popular greedy algorithms and a heuristic distributed task allocation method.

J38. Learning Interaction-Aware Guidance for Trajectory Optimization in Dense Traffic Scenarios
B. Brito, A. Agarwal, J. Alonso-Mora. In IEEE Transactions on Intelligent Transportation Systems (T-ITS), 2022.

web pdf video
Abstract: Autonomous navigation in dense traffic scenarios remains challenging for autonomous vehicles (AVs) because the intentions of other drivers are not directly observable and AVs have to deal with a wide range of driving behaviors. To maneuver through dense traffic, AVs must be able to reason how their actions affect others (interaction model) and exploit this reasoning to navigate through dense traffic safely. This paper presents a novel framework for interaction-aware motion planning in dense traffic scenarios. We explore the connection between human driving behavior and their velocity changes when interacting. Hence, we propose to learn, via deep Reinforcement Learning (RL), an interaction-aware policy providing global guidance about the cooperativeness of other vehicles to an optimization-based planner ensuring safety and kinematic feasibility through constraint satisfaction. The learned policy can reason and guide the local optimization-based planner with interactive behavior to pro-actively merge in dense traffic while remaining safe in case the other vehicles do not yield. We present qualitative and quantitative results in highly interactive simulation environments (highway merging and unprotected left turns) against two baseline approaches, a learning-based and an optimization-based method. The presented results demonstrate that our method significantly reduces the number of collisions and increases the success rate with respect to both learning-based and optimization-based baselines.

J37. Probabilistic risk metric for highway driving leveraging multi-modal trajectory prediction
X. Wang, J. Alonso-Mora, M. Wang. In , IEEE Transactions on Intelligent Transportation Systems (T-ITS), 2022.

web pdf
Abstract: Road traffic safety has attracted increasing research attention, in particular in the current transition from human-driven vehicles to autonomous vehicles. Surrogate measures of safety are widely used to assess traffic safety but they typically ignore motion uncertainties and are inflexible in dealing with two-dimensional motion. Meanwhile, learning-based lane-change and trajectory prediction models have shown potential to provide accurate prediction results. We therefore propose a prediction-based driving risk metric for two-dimensional motion on multi-lane highways, expressed by the maximum risk value over different time instants within a prediction horizon. At each time instant, the risk of the vehicle is estimated as the sum of weighted risks over each mode in a finite set of lane-change maneuver possibilities. Under each maneuver mode, the risk is calculated as the product of three factors: lane-change maneuver mode probability, collision probability and expected crash severity. The three factors are estimated leveraging two-stage multi-modal trajectory predictions for surrounding vehicles: first a lane-change intention prediction module is invoked to provide lane-change maneuver mode possibilities, and then the mode possibilities are used as partial input for a multi-modal trajectory prediction module. Working with the empirical trajectory dataset highD and simulated highway scenarios, the proposed two-stage model achieves superior performance compared to a state-of-the-art prediction model. The proposed risk metric is computationally efficient for real-time applications, and effective to identify potential crashes earlier thanks to the employed prediction model.

J36. A business class for autonomous mobility-on-demand: Modeling service quality contracts in dynamic ridesharing systems
B. A. Beirigo, R. R. Negenborn, J. Alonso-Mora, F. Schulte. In , Transportation Research Part C: Emerging Technologies, 2022.

web pdf
Abstract: With the popularization of transportation network companies (TNCs) (e.g., Uber, Lyft) and the rise of autonomous vehicles (AVs), even major car manufacturers are increasingly considering themselves as autonomous mobility-on-demand (AMoD) providers rather than individual vehicle sellers. However, matching the convenience of owning a vehicle requires providing consistent service quality, taking into account individual expectations. Typically, different classes of users have different service quality (SQ) expectations in terms of responsiveness, reliability, and privacy. Nonetheless, AMoD systems presented in the literature do not enable active control of service quality in the short term, especially in light of unusual demand patterns, sometimes allowing extensive delays and user rejections. This study proposes a method to control the daily operations of an AMoD system that uses the SQ expectations of heterogeneous user classes to dynamically distribute service quality among riders. Additionally, we consider an elastic vehicle supply, that is, privately-owned freelance AVs (FAVs) can be hired on short notice to help providers meeting user service-level expectations. We formalize the problem as the dial-a-ride problem with service quality contracts (DARP-SQC) and propose a multi-objective matheuristic to address real-world requests from Manhattan, New York City. Applying the proposed service-level constraints, we improve user satisfaction (in terms of reached service-level expectations) by 53% on average compared to conventional ridesharing systems, even without hiring additional vehicles. By deploying service-quality-oriented on-demand hiring, our hierarchical optimization approach allows providers to adequately cater to each segment of the customer base without necessarily owning large fleets.

J35. Improving Pedestrian Prediction Models with Self-Supervised Continual Learning
L. Knoedler, C. Salmi, H. Zhu, B. Brito, J. Alonso-Mora. In , IEEE Robotics and Automation Letters (RA-L), 2022.

web pdf code video
Abstract: Autonomous mobile robots require accurate human motion predictions to safely and efficiently navigate among pedestrians, whose behavior may adapt to environmental changes. This letter introduces a self-supervised continual learning framework to improve data-driven pedestrian prediction models online across various scenarios continuously. In particular, we exploit online streams of pedestrian data, commonly available from the robot’s detection and tracking pipeline, to refine the prediction model and its performance in unseen scenarios. To avoid the forgetting of previously learned concepts, a problem known as catastrophic forgetting, our framework includes a regularization loss to penalize changes of model parameters that are important for previous scenarios and retrains on a set of previous examples to retain past knowledge. Experimental results on real and simulation data show that our approach can improve prediction performance in unseen scenarios while retaining knowledge from seen scenarios when compared to naively training the prediction model online.

J34. Decentralized Probabilistic Multi-Robot Collision Avoidance Using Buffered Uncertainty-Aware Voronoi Cells
H. Zhu, B. Brito, J. Alonso-Mora. In , Autonomous Robots (AURO), 2022.

web pdf code video
Abstract: In this paper, we present a decentralized and communication-free collision avoidance approach for multi-robot systems that accounts for both robot localization and sensing uncertainties. The approach relies on the computation of an uncertainty-aware safe region for each robot to navigate among other robots and static obstacles in the environment, under the assumption of Gaussian-distributed uncertainty. In particular, at each time step, we construct a chance-constrained buffered uncertainty-aware Voronoi cell (B-UAVC) for each robot given a specified collision probability threshold. Probabilistic collision avoidance is achieved by constraining the motion of each robot to be within its corresponding B-UAVC, i.e. the collision probability between the robots and obstacles remains below the specified threshold. The proposed approach is decentralized, communication-free, scalable with the number of robots and robust to robots’ localization and sensing uncertainties. We applied the approach to single-integrator, double-integrator, differential-drive robots, and robots with general nonlinear dynamics. Extensive simulations and experiments with a team of ground vehicles, quadrotors, and heterogeneous robot teams are performed to analyze and validate the proposed approach.

C58. Do we use the Right Measure? Challenges in Evaluating Reward Learning Algorithms
N. Wilde, J. Alonso-Mora. In Conference on Robot Learning (CoRL), 2022.

pdf
Abstract: Reward learning is a highly active area of research in human-robot interaction (HRI), allowing a broad range of users to specify complex robot be- haviour. Experiments with simulated user input play a major role in the devel- opment and evaluation of reward learning algorithms due to the availability of a ground truth. In this paper, we review measures for evaluating reward learning algorithms used in HRI, most of which fall into two classes. In a theoretical worst case analysis and several examples, we show that both classes of measures can fail to effectively indicate how good the learned robot behaviour is. Thus, our work contributes to the characterization of sim-to-real gaps of reward learning in HRI.

C57. Routing of Heterogeneous Fleets for Flash Deliveries via Vehicle Group Assignment
M. Kronmueller, A. Fielbaum, J. Alonso-Mora. In Proc. 2022 IEEE - Int. Conf. on Intelligent Transportation (ITSC), 2022.

web pdf
Abstract: This paper presents a novel approach to route heterogeneous fleets for flash delivery operations. Flash deliveries offer to serve customers’ wishes in minutes. We investigate a scenario that allows to pick up orders at multiple depots with a heterogeneous vehicle fleet leveraging different modes of transportation. We propose the Heterogeneous Vehicle Group Assignment (HVGA) method, which, given a problem state, identifies potential pick-up locations, calculates potential trips for all modes of transportation and last chooses from the set of potential trips. Experiments to analyze the proposed method are executed using a fleet featuring two modes of transportation, trucks and drones. We compare to a state-of-the-art method. Results show that HVGA is able to serve more orders while requiring less total traveled distance. Further, the effects of the fleet size and fleet composition between drones and trucks are examined by simulating three hours of a flash delivery operation in the city center of Amsterdam.

C56. Error-Bounded Approximation of Pareto Fronts in Robot Planning Problems
A. Botros, A. Sadeghi, N. Wilde, J. Alonso-Mora, S. L. Smith. In 15th Workshop on the Algorithmic Foundations of Robotics (WAFR), 2022.

web pdf
Abstract: Many problems in robotics seek to simultaneously optimize several competing objectives under constraints. A conventional approach to solving such multi-objective optimization problems is to create a single cost function comprised of the weighted sum of the individual objectives. Solutions to this scalarized optimization problem are Pareto optimal solutions to the original multi-objective problem. However, finding an accurate representation of a Pareto front remains an important challenge. Using uniformly spaced weight vectors is often inefficient and does not provide error bounds. Thus, we address the problem of computing a finite set of weight vectors such that for any other weight vector, there exists an element in the set whose error compared to optimal is minimized. To this end, we prove fundamental properties of the optimal cost as a function of the weight vector, including its continuity and concavity. Using these, we propose an algorithm that greedily adds the weight vector least-represented by the current set, and provide bounds on the error. Finally, we illustrate that the proposed approach significantly outperforms uniformly distributed weights for different robot planning problems with varying numbers of objective functions.

C55. Prediction-Based Reachability Analysis for Collision Risk Assessment on Highways
X. Wang, Z. Li, J. Alonso-Mora, M. Wang. In IEEE Intelligent Vehicles Symposium (IV), 2022.

web pdf
Abstract: Real-time safety systems are crucial components of intelligent vehicles. This paper introduces a prediction-based collision risk assessment approach on highways. Given a point mass vehicle dynamics system, a stochastic forward reachable set considering two-dimensional motion with vehicle state probability distributions is firstly established. We then develop an acceleration prediction model, which provides multi-modal probabilistic acceleration distributions to propagate vehicle states. The collision probability is calculated by summing up the probabilities of the states where two vehicles spatially overlap. Simulation results show that the prediction model has superior performance in terms of vehicle motion position errors, and the proposed collision detection approach is agile and effective to identify the collision in cut-in crash events.

C54. Regulations Aware Motion Planning for Autonomous Surface Vessels in Urban Canals
J. de Vries, E. Trevisan, J. van der Toorn, T. Das, B. Brito, J. Alonso-Mora. In Proc. IEEE Int. Conf. on Robotics and Automation (ICRA), 2022.

web pdf video
Abstract: In unstructured urban canals, regulation-aware interactions with other vessels are essential for collision avoidance and social compliance. In this paper, we propose a regulations aware motion planning framework for Autonomous Surface Vessels (ASVs) that accounts for dynamic and static obstacles. Our method builds upon local model predictive contouring control (LMPCC) to generate motion plans satisfying kino-dynamic and collision constraints in real-time while including regulation awareness. To incorporate regulations in the planning stage, we propose a cost function encouraging compliance with rules describing interactions with other vessels similar to COLlision avoidance REGulations at sea (COLREGs). These regulations are essential to make an ASV behave in a predictable and socially compliant manner with regard to other vessels. We compare the framework against baseline methods and show more effective regulation-compliance avoidance of moving obstacles with our motion planner. Additionally, we present experimental results in an outdoor environment.

C53. Where to Look Next: Learning Viewpoint Recommendations for Informative Trajectory Planning
M. Lodel, B. Brito, A. Serra-Gomez, L. Ferranti, R. Babuska, J. Alonso-Mora. In Proc. IEEE Int. Conf. on Robotics and Automation (ICRA), 2022.

web pdf video
Abstract: Search missions require motion planning and navigation methods for information gathering that continuously replan based on new observations of the robot's surroundings. Current methods for information gathering, such as Monte Carlo Tree Search, are capable of reasoning over long horizons, but they are computationally expensive. An alternative for fast online execution is to train, offline, an information gathering policy, which indirectly reasons about the information value of new observations. However, these policies lack safety guarantees and do not account for the robot dynamics. To overcome these limitations we train an information-aware policy via deep reinforcement learning, that guides a receding-horizon trajectory optimization planner. In particular, the policy continuously recommends a reference viewpoint to the local planner, such that the resulting dynamically feasible and collision-free trajectories lead to observations that maximize the information gain and reduce the uncertainty about the environment. In simulation tests in previously unseen environments, our method consistently outperforms greedy next-best-view policies and achieves competitive performance compared to Monte Carlo Tree Search, in terms of information gains and coverage time, with a reduction in execution time by three orders of magnitude.

C52. Learning Mixed Strategies in Trajectory Games
L. Peters, D. Fridovich-Keil, L. Ferranti, C. J. Alonso-Mora, F. Laine. In , Proc. of Robotics: Science and Systems (RSS), 2022.

web pdf video
Abstract: In multi-agent settings, game theory is a natural framework for describing the strategic interactions of agents whose objectives depend upon one another’s behavior. Trajectory games capture these complex effects by design. In competitive settings, this makes them a more faithful interaction model than traditional “predict then plan” approaches. However, current game-theoretic planning methods have important limitations. In this work, we propose two main contributions. First, we introduce an offline training phase which reduces the online computational burden of solving trajectory games. Second, we formulate a lifted game which allows players to optimize multiple candidate trajectories in unison and thereby construct more competitive “mixed” strategies. We validate our approach on a number of experiments using the pursuit-evasion game “tag.”

C51. Reachability-based confidence-aware probabilistic collision detection in highway driving
X. Wang, Z. Li, J. Alonso-Mora, M. Wang. In 4th Symposium on Management of Future motorway and urban Traffic Systems (MFTS), Dresden, Germany, 2022.

pdf slides
Links: [pdf], [slides],

C50. Online Multi-Robot Task Assignment with Stochastic Blockages
N. Wilde, J. Alonso-Mora. In IEEE Conference on Decision and Control (CDC), 2022.

pdf
Abstract: In this paper we study the multi-robot task assignment problem with tasks that appear online and need to be serviced within a fixed time window in an uncertain environment. For example, when deployed in dynamic, human centered environments, the team of robots may not have perfect information about the environment. Parts of the environment may temporarily become blocked and blockages may only be observed on location. While numerous variants of the Canadian Traveler Problem describe the path planning aspect of this problem, few work has been done on multi-robot task allocation (MRTA) under this type of uncertainty. In this paper, we introduce and theoretically analyze the problem of MRTA with recoverable online blockages. Based on a stochastic blockage model, we compute offline tours using the expected travel costs for the online routing problem. The cost of the offline tours is used in a greedy task assignment algorithm. In simulation experiments we highlight the performance benefits of the proposed method under various settings.

W7. Learning a Guidance Policy from Humans for Social Navigation
L. Knoedler, B. Brito, M. Everett, J.P. How, J. Alonso-Mora. In Social Robot Navigation: Advances and Evaluation at IEEE International Conference on Robotics and Automation (ICRA), 2022.

web pdf
Abstract: Autonomous mobile robots navigating among humans must not only consider safety and efficiency but also move acceptably in the current social context. A hybrid deep reinforcement learning - model predictive control (DRL-MPC) approach can account for the complex interactions among humans while maintaining the collision avoidance guarantees and feasibility constraints inherent in the MPC formulation. However, encoding socially acceptable behavior through a reward or cost function, along with other objectives such as reaching the goal quickly, is challenging. Therefore, this work proposes a new training strategy that combines supervised and reinforcement learning to exploit human demonstration. Furthermore, it presents first results from real-world experiments.

2021

J33. How to split the costs and charge the travellers sharing a ride? Aligning system's optimum with users' equilibrium
A. Fielbaum, R. Kucharski, O. Cats, J. Alonso-Mora. In , European Journal of Operational Research, 2021.

web pdf
Abstract: Emerging on-demand sharing alternatives, in which one resource is utilised simultaneously by a circumstantial group of users, entail several challenges regarding how to coordinate such users. A very relevant case refers to how to form groups in a mobility system that offers shared rides, and how to split the costs within the travellers of a group. These are non-trivial tasks, as two objectives conflict: 1) minimising the total costs of the system, and 2) finding an equilibrium where each user is content with her assignment. Aligning both objectives is challenging, as users are not aware of the externalities induced to the rest. In this paper, we propose protocols to share the costs within a ride so that optimal solutions can also constitute equilibria. To do this, we model the situation as a non-cooperative game, which can be seen as a game-version of the well-known set cover problem. We show that the traditional notions of equilibrium in game theory (Nash and Strong) are not useful here, and prove that determining whether a Strong Equilibrium exists is an NP-Complete problem, by reducing it to the k-Exact-Cover problem. Hence, we propose three alternative equilibrium notions (stronger than Nash and weaker than Strong), depending on how users can coordinate. For each of these equilibrium notions, we propose a (possibly overcharging) cost-sharing protocol that yields the optimal solutions equilibria. Simulations for Amsterdam reveal that our protocols can achieve stable solutions that are close to the optimum, and that having a central coordinator can have a large impact.

J32. Anticipatory routing methods for an on-demand ridepooling mobility system
A. Fielbaum, M. Kronmueller, J. Alonso-Mora. In , Transportation, 2021.

web pdf
Abstract: On-demand mobility systems in which passengers use the same vehicle simultaneously are a promising transport mode, yet difficult to control. One of the most relevant challenges relates to the spatial imbalances of the demand, which induce a mismatch between the position of the vehicles and the origins of the emerging requests. Most ridepooling models face this problem through rebalancing methods only, i.e., moving idle vehicles towards areas with high rejections rate, which is done independently from routing and vehicle-to-orders assignments, so that vehicles serving passengers (a large portion of the total fleet) remain unaffected. This paper introduces two types of techniques for anticipatory routing that affect how vehicles are assigned to users and how to route vehicles to serve such users, so that the whole operation of the system is modified to reach more efficient states for future requests. Both techniques do not require any assumption or exogenous knowledge about the future demand, as they depend only on current and recent requests. Firstly, we introduce rewards that reduce the cost of an assignment between a vehicle and a group of passengers if the vehicle gets routed towards a high-demand zone. Secondly, we include a small set of artificial requests, whose request times are in the near future and whose origins are sampled from a probability distribution that mimics observed generation rates. These artificial requests are to be assigned together with the real requests. We propose, formally discuss and experimentally evaluate several formulations for both approaches. We test these techniques in combination with a state-of-the-art trip-vehicle assignment method, using a set of real rides from Manhattan. Introducing rewards can diminish the rejection rate to about nine-tenths of its original value. On the other hand, including future requests can reduce users’ traveling times by about one-fifth, but increasing rejections. Both methods increase the vehicles-hour-traveled by about 10%. Spatial analysis reveals that vehicles are indeed moved towards the most demanded areas, such that the reduction in rejections rate is achieved mostly there.

J31. On-demand ridesharing with optimized pick-up and drop-off walking locations
A. Fielbaum, X. Bai, J. Alonso-Mora. In , Transportation Research Part C: Emerging Technologies, 2021.

web pdf
Abstract: On-demand systems in which passengers with similar routes can share a vehicle are expected to become a relevant part of future mobility, thanks to their flexibility and their potential impact on reducing congestion. Nevertheless, due to the long detours required by a door-to-door scheme, they induce extra costs to the users in terms of delay. In this paper, we face the design of such a system in which users might be requested online to walk towards/from nearby pick-up/drop-off points if this improves overall efficiency. We show theoretically that the general problem becomes more complex (as it contains two sub-problems that extend set-cover), analyze the trade-offs that emerge, and provide a general formulation and specific heuristics that are able to solve it over large instances. We test this formulation over a real dataset of Manhattan taxi trips (9970 requests during one hour), finding that (a) average walks of about one minute can reduce the number of rejections in more than 80% and Vehicles-Hour-Traveled in more than 10%, (b) users who depart or arrive at the most demanded areas are more likely to be required to walk, and (c) the performance improvement of the service is larger when the system receives more trip requests.

J30. Integrated Task Assignment and Path Planning for Capacitated Multi-Agent Pickup and Delivery
Z. Chen, J. Alonso-Mora, X. Bai, D. D. Harabor, P. J. Stuckey. In , IEEE Robotics and Automation Letters (RA-L), 2021.

web pdf code
Abstract: Multi-agent Pickup and Delivery (MAPD) is a challenging industrial problem where a team of robots is tasked with transporting a set of tasks, each from an initial location and each to a specified target location. Appearing in the context of automated warehouse logistics and automated mail sortation, MAPD requires first deciding which robot is assigned what task (i.e., Task Assignment or TA) followed by a subsequent coordination problem where each robot must be assigned collision-free paths so as to successfully complete its assignment (i.e., Multi-Agent Path Finding or MAPF). Leading methods in this area solve MAPD sequentially: first assigning tasks, then assigning paths. In this work we propose a new coupled method where task assignment choices are informed by actual delivery costs instead of by lower-bound estimates. The main ingredients of our approach are a marginal-cost assignment heuristic and a meta-heuristic improvement strategy based on Large Neighbourhood Search. As a further contribution, we also consider a variant of the MAPD problem where each robot can carry multiple tasks instead of just one. Numerical simulations show that our approach yields efficient and timely solutions and we report significant improvement compared with other recent methods from the literature.

J29. Where to go next: Learning a Subgoal Recommendation Policy for Navigation in Dynamic Environments
B. Brito, M. Everett, J. P. How, J. Alonso-Mora. In , IEEE Robotics and Automation Letters (RA-L), 2021.

web pdf video
Abstract: Robotic navigation in environments shared with other robots or humans remains challenging because the intentions of the surrounding agents are not directly observable and the environment conditions are continuously changing. Local trajectory optimization methods, such as model predictive control (MPC), can deal with those changes but require global guidance, which is not trivial to obtain in crowded scenarios. This letter proposes to learn, via deep Reinforcement Learning (RL), an interaction-aware policy that provides long-term guidance to the local planner. In particular, in simulations with cooperative and non-cooperative agents, we train a deep network to recommend a subgoal for the MPC planner. The recommended subgoal is expected to help the robot in making progress towards its goal and accounts for the expected interaction with other agents. Based on the recommended subgoal, the MPC planner then optimizes the inputs for the robot satisfying its kinodynamic and collision avoidance constraints. Our approach is shown to substantially improve the navigation performance in terms of number of collisions as compared to prior MPC frameworks, and in terms of both travel time and number of collisions compared to deep RL methods in cooperative, competitive and mixed multiagent scenarios.

J28. Learning Interaction-Aware Trajectory Predictions for Decentralized Multi-Robot Motion Planning in Dynamic Environments
H. Zhu, F. Claramunt, B. Brito, J. Alonso-Mora. In , IEEE Robotics and Automation Letters (RA-L), 2021.

web pdf video
Abstract: This letter presents a data-driven decentralized trajectory optimization approach for multi-robot motion planning in dynamic environments. When navigating in a shared space, each robot needs accurate motion predictions of neighboring robots to achieve predictive collision avoidance. These motion predictions can be obtained among robots by sharing their future planned trajectories with each other via communication. However, such communication may not be available nor reliable in practice. In this letter, we introduce a novel trajectory prediction model based on recurrent neural networks (RNN) that can learn multi-robot motion behaviors from demonstrated trajectories generated using a centralized sequential planner. The learned model can run efficiently online for each robot and provide interaction-aware trajectory predictions of its neighbors based on observations of their history states. We then incorporate the trajectory prediction model into a decentralized model predictive control (MPC) framework for multi-robot collision avoidance. Simulation results show that our decentralized approach can achieve a comparable level of performance to a centralized planner while being communication-free and scalable to a large number of robots. We also validate our approach with a team of quadrotors in real-world experiments.

J27. Scenario-Based Trajectory Optimization in Uncertain Dynamic Environments
O. de Groot, B. Brito, L. Ferranti, D. Gavrila, J. Alonso-Mora. In , IEEE Robotics and Automation Letters (RA-L), 2021.

web pdf video
Abstract: We present an optimization-based method to plan the motion of an autonomous robot under the uncertainties associated with dynamic obstacles, such as humans. Our method bounds the marginal risk of collisions at each point in time by incorporating chance constraints into the planning problem. This problem is not suitable for online optimization outright for arbitrary probability distributions. Hence, we sample from these chance constraints using an uncertainty model, to generate "scenarios", which translate the probabilistic constraints into deterministic ones. In practice, each scenario represents the collision constraint for a dynamic obstacle at the location of the sample. The number of theoretically required scenarios can be very large. Nevertheless, by exploiting the geometry of the workspace, we show how to prune most scenarios before optimization and we demonstrate how the reduced scenarios can still provide probabilistic guarantees on the safety of the motion plan. Since our approach is scenario based, we are able to handle arbitrary uncertainty distributions. We apply our method in a Model Predictive Contouring Control framework and demonstrate its benefits in simulations and experiments with a moving robot platform navigating among pedestrians, running in real-time.

C49. On-demand Grocery Delivery From Multiple Local Stores With Autonomous Robots
M. Kronmueller, A. Fielbaum, J. Alonso-Mora. In Proc. 3rd IEEE International Symposium on Multi-Robot and Multi-Agent Systems (MRS'21), 2021.

web pdf video
Abstract: The advances in the area of autonomous delivery robots combined with customers' desire for fast delivery, bare potential for same-day delivery operations, specifically with small time windows between ordering and delivery. Most same-day deliveries are operated using a single depot and with vehicles' routes planned and fixed when leaving the depot. In this paper, we relax these two assumptions and focus on on-demand grocery delivery using a fleet of autonomous vehicles or robots. The problem features the opportunity to pick up goods at multiple local stores or depots, for example, supermarkets within the city, and allows robots to perform depot returns prior to being empty, if beneficial. This allows for more agile planning and on average shorter distance to the next depot. We propose a novel dynamic method for the same-day delivery problem, where we aim to deliver orders as fast as possible, minimally within the same day. In each time step (every few seconds or minutes) the following is executed: For each order potential pick-up locations are identified and feasible trips, i.e., sequences to pick up goods and deliver orders, are calculated. To assign trips to robots an integer-linear program is solved. We simulate one day of service in a city under different conditions with up to 30 autonomous robots, 30 depots and 10,500 orders. Results underpin the advantages of the proposed method and show its versatility with respect to different situations.

C48. Multi-robot Task Assignment for Aerial Tracking with Viewpoint Constraints
A. Ray, A. Pierson, H. Zhu, J. Alonso-Mora, D. Rus. In Proc. IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS), 2021.

web pdf
Abstract: We address the problem of assigning a team of drones to autonomously capture a set desired shots of a dynamic target in the presence of obstacles. We present a two-stage planning pipeline that generates offline an assignment of drone to shots and locally optimizes online the viewpoint. Given desired shot parameters, the high-level planner uses a visibility heuristic to predict good times for capturing each shot and uses an Integer Linear Program to compute drone assignments. An online Model Predictive Control algorithm uses the assignments as reference to capture the shots. The algorithm is validated in hardware with a pair of drones and a remote controlled car.

C47. Towards a geographically even level of service in on-demand ridepooling
P. Schuller, A. Fielbaum, J. Alonso-Mora. In Proc. 2021 IEEE - Int. Conf. on Intelligent Transportation (ITSC), 2021.

web pdf
Abstract: On-demand ridepooling systems usually need to decide which requests to serve, when the number of vehicles is not enough to transport them all with waiting times that are acceptable by the users. When doing so, they tend to provide uneven service rates, concentrating rejections in some zones within the operation area. In this paper, we propose two techniques that modify the objective function governing the assignment of users to vehicles, to prioritize requests originated at zones that present a relatively large rejection rate. The goal is to diminish the Gini Index of the rejections' rate, which is a well established way to measure inequality in economics. We test these techniques over an artificial small network and a real-life case in Manhattan, and we show that they are able to reduce the Gini Index of the rejection rates. Moreover, the overall rejection rate can be simultaneously reduced, thanks to utilizing the vehicles more efficiently.

C46. Online Informative Path Planning for Active Information Gathering of a 3D Surface
H. Zhu, J. J. Chung, N. R. J. Lawrance, R. Siegwart, J. Alonso-Mora. In Proc. IEEE Int. Conf. on Robotics and Automation (ICRA), 2021.

web pdf code
Abstract: This paper presents an online informative path planning approach for active information gathering on three-dimensional surfaces using aerial robots. Most existing works on surface inspection focus on planning a path offline that can provide full coverage of the surface, which inherently assumes the surface information is uniformly distributed hence ignoring potential spatial correlations of the information field. In this paper, we utilize manifold Gaussian processes (mGPs) with geodesic kernel functions for mapping surface information fields and plan informative paths online in a receding horizon manner. Our approach actively plans information-gathering paths based on recent observations that respect dynamic constraints of the vehicle and a total flight time budget. We provide planning results for simulated temperature modeling for simple and complex 3D surface geometries (a cylinder and an aircraft model). We demonstrate that our informative planning method outperforms traditional approaches such as 3D coverage planning and random exploration, both in reconstruction error and information-theoretic metrics. We also show that by taking spatial correlations of the information field into planning using mGPs, the information gathering efficiency is significantly improved.

C45. Coupled mobile manipulation via trajectory optimization with free space decomposition
M. Spahn, B. Brito, J. Alonso-Mora. In Proc. IEEE Int. Conf. on Robotics and Automation (ICRA), 2021.

web pdf video
Abstract: This paper presents a real-time method for whole-body trajectory optimization of mobile manipulators in simplified dynamic and unstructured environments. Current trajectory optimization methods typically use decoupling of the mobile base and the robotic arm, which reduces flexibility in motion, does not scale to unstructured environments, and does not consider the future evolution of the environment, which is crucial to avoid dynamic obstacles. Given a goal configuration, such as waypoints generated by a global path planner, we formulate a receding horizon trajectory optimization minimizing the distance-to-target while avoiding collisions with static and dynamic obstacles. The presented method unifies the control of a robotic arm and a non-holonomic base to allow coupled trajectory planning. For collision avoidance, we propose to compute three convex regions englobing the robot's major body parts (i.e., base, shoulder-link and wrist-link) and thus reducing and limiting the number of inequality constraints, regardless of the number of obstacles in the environment. Moreover, our approach incorporates predicted trajectory information to smoothly, and in advance, avoid dynamic obstacles. The presented results show that trajectory optimization for the coupled system can reduce the total execution time by 48% and that applying the convex region generation for individual links allows keeping the computational costs low, even for complex scenarios, enabling onboard implementation.

C44. Curvature Aware Motion Planning with Closed-Loop Rapidly-exploring Random Trees
B. van den Berg, B. Brito, M. Alirezaei, J. Alonso-Mora. In IEEE Intelligent Vehicles Symposium (IV), 2021.

web pdf video
Abstract: The road's geometry strongly influences the path planner's performance, critical for autonomous navigation in high-speed dynamic scenarios (e.g., highways). Hence, this paper introduces the Curvature-aware Rapidly-exploring Random Trees (CA-CL-RRT), whose planning performance is invariant to the road's geometry. We propose a transformation strategy that allows us to plan on a virtual straightened road and then convert the planned motion to the curved road. It is shown that the proposed approach substantially improves path planning performance on curved roads as compared to prior RRT-based path planners. Moreover, the proposed CA-CL-RRT is combined with a Local Model Predictive Contour Controller (LMPCC) for path tracking while ensuring collision avoidance through constraint satisfaction. We present quantitative and qualitative performance results in two navigation scenarios: dynamic collision avoidance and structured highway driving. The results demonstrate that our proposed navigation framework improves the path quality on curved highway roads and collision avoidance with dynamic obstacles.

2020

J26. Social Trajectory Planning for Urban Autonomous Surface Vessels
S. Park, M. Cap, J. Alonso-Mora, C. Ratti, D. Rus. In , IEEE Transactions on Robotics (T-RO), 2020.

web pdf
Abstract: In this article, we propose a trajectory planning algorithm that enables autonomous surface vessels to perform socially compliant navigation in a city's canal. The key idea behind the proposed algorithm is to adopt an optimal control formulation in which the deviation of movements of the autonomous vessel from nominal movements of human-operated vessels is penalized. Consequently, given a pair of origin and destination points, it finds vessel trajectories that resemble those of human-operated vessels. To formulate this, we adopt kernel density estimation (KDE) to build a nominal movement model of human-operated vessels from a prerecorded trajectory dataset, and use a Kullback-Leibler control cost to measure the deviation of the autonomous vessel's movements from the model. We establish an analogy between our trajectory planning approach and the maximum entropy inverse reinforcement learning (MaxEntIRL) approach to explain how our approach can learn the navigation behavior of human-operated vessels. On the other hand, we distinguish our approach from the MaxEntIRL approach in that it does not require well-defined bases, often referred to as features, to construct its cost function as required in many of inverse reinforcement learning approaches in the trajectory planning context. Through experiments using a dataset of vessel trajectories collected from the automatic identification system, we demonstrate that the trajectories generated by our approach resemble those of human-operated vessels and that using them for canal navigation is beneficial in reducing head-on encounters between vessels and improving navigation safety.

J25. Unreliability in ridesharing systems: Measuring changes in users' times due to new requests
A. Fielbaum, J. Alonso-Mora. In , Transportation Research Part C: Emerging Technologies, 2020.

web pdf
Abstract: On-demand systems in which several users can ride simultaneously the same vehicle have great potential to improve mobility while reducing congestion. Nevertheless, they have a significant drawback: the actual realization of a trip depends on the other users with whom it is shared, as they might impose extra detours that increase the waiting time and the total delay; even the chance of being rejected by the system depends on which travelers are using the system at the same time. In this paper we propose a general description of the sources of unreliability that emerge in ridesharing systems and we introduce several measures. The proposed measures are related to two sources of unreliability induced by how requests and vehicles are being assigned, namely how users’ times change within a single trip and between different realizations of the same trip. We then analyze both sources using a state-of-the-art routing and assignment method, and a New York City test case. Regarding same trip unreliability, in our experiments for different fixed fleet compositions and when reassignment is not restricted, we find that more than one third of the requests that are not immediately rejected face some change, and the magnitude of these changes is relevant: when a user faces an increase in her waiting time, this extra time is comparable to the average waiting time of the whole system, and the same happens with total delay. Algorithmic changes to reduce this uncertainty induce a trade-off with respect to the overall quality of service. For instance, not allowing for reassignments may increase the number of rejected requests. Concerning the unreliability between different trips, we find that the same origin-destination request can be rejected or served depending on the state of the fleet. And when it is served the waiting times and total delay are rarely equal, which remains true for different fleet sizes. Furthermore, the largest variations are faced by trips beginning at high-demand areas.

J24. If you are late, everyone is late: late passenger arrival and ride-pooling systems' performance
R. Kucharski, A. Fielbaum, J. Alonso-Mora, O. Cats. In Transportmetrica A: Transport Science, 2020.

web pdf
Abstract: Sharing rides in on-demand systems allow passengers to reduce their fares and service providers to increase revenue, though at the cost of adding uncertainty to the system. Notably, the uncertainty of ride-pooling systems stems not only from travel times but also from unique features of sharing, such as the dependency on other passengers' arrival time at their pick up points. In this work, we theoretically and experimentally analyse how late arrivals at pick up locations impact shared rides' performance. We find that the total delay is equally distributed among sharing passengers. However, delay composition gradually shifts from on-board delay only for the first passenger to waiting delay at the origin for the last passenger. Sadly, trips with more passengers are more adversely impacted. Strategic behaviour analysis reveals Nash equilibria that might emerge. We analyse the system-wide effects and find that when lateness increases passengers refrain from sharing and eventually opt-out.

J23. Ride-Sharing Efficiency and Level of Service under Alternative Demand, Behavioral and Pricing Settings
A. de Ruijter, O. Cats, J. Alonso-Mora, S. Hoogendoorn. In Transportation Research Board Annual Meeting, 2020.

pdf
Previous studies examining ride-sharing potential assumed that rides can be shared as long as the incurred delay does not exceed a certain threshold. Conversely, we formulate willingness to share as a compensatory cost function at the individual passenger level. The latter considers trade-offs between delays caused by detours, travel discomfort related to sharing a vehicle and a fare discount associated with a shared ride. Next to finding how these behavioral preferences and the offered discount structure affect the efficiency and level of service of ride-sharing services, the effect of directionality in demand is considered. A graph-based approach is applied to perform an efficient assignment of vehicles to requests. We test the model on an experiment representing an urban context. Our findings suggest that service performance is strongly dependent on users’ willingness to share and somewhat less strongly on users’ tolerance to delays. Implementation of a ride-sharing service is most successful when directionality in demand is low, while ride-specific discounts can be effective in maximizing societal benefits.

J22. Online Trajectory Planning and Control of a MAV Payload System in Dynamic Environments
N. D. Potdar, G. C. H. D. de Croon, J. Alonso-Mora. In Springer Autonomous Robots, 2020.

web pdf video
Abstract: Micro Aerial Vehicles (MAVs) can be used for aerial transportation in remote and urban spaces where portability can be exploited to reach previously inaccessible and inhospitable spaces. Current approaches for path planning of MAV swung payload system either compute conservative minimal-swing trajectories or pre-generate agile collision-free trajectories. However, these approaches have failed to address the prospect of online re-planning in uncertain and dynamic environments, which is a prerequisite for real-world deployability. This paper describes an online method for agile and closed-loop local trajectory planning and control that relies on Non-Linear Model Predictive Control and that addresses the mentioned limitations of contemporary approaches. We integrate the controller in a full system framework, and demonstrate the algorithm’s effectiveness in simulation and in experimental studies. Results show the scalability and adaptability of our method to various dynamic setups with repeatable performance over several complex tasks that include flying through a narrow opening and avoiding moving humans.

J21. Trajectory Optimization and Situational Analysis Framework for Autonomous Overtaking with Visibility Maximization
H. Andersen, J. Alonso-Mora, Y.H. Eng, D. Rus, M. Ang. In IEEE Transactions on Intelligent Vehicles (T-IV), 2020.

web pdf video
Abstract: In this article we present a trajectory generation method for autonomous overtaking of unexpected obstacles in a dynamic urban environment. In these settings, blind spots can arise from perception limitations. For example when overtaking unexpected objects on the vehicle's ego lane on a two-way street. In this case, a human driver would first make sure that the opposite lane is free and that there is enough room to successfully execute the maneuver, and then it would cut into the opposite lane in order to execute the maneuver successfully. We consider the practical problem of autonomous overtaking when the coverage of the perception system is impaired due to occlusion. Safe trajectories are generated by solving, in real-time, a non-linear constrained optimization, formulated as a receding horizon planner that maximizes the ego vehicle's visibility. The planner is complemented by a high-level behavior planner, which takes into account the occupancy of other traffic participants, the information from the vehicle's perception system, and the risk associated with the overtaking maneuver, to determine when the overtake maneuver should happen. The approach is validated in simulation and in experiments in real world traffic.

C43. Social-VRNN: One-Shot Multi-modal Trajectory Prediction for Interacting Pedestrians
B. Brito, H. Zhu, W. Pan, J. Alonso-Mora. In Proc. 2020 Conference on Robot Learning (CoRL), 2020.

web pdf video
Abstract: Prediction of human motions is key for safe navigation of autonomous robots among humans. In cluttered environments, several motion hypotheses may exist for a pedestrian, due to its interactions with the environment and other pedestrians. Previous works for estimating multiple motion hypotheses require a large number of samples which limits their applicability in real-time motion planning. In this paper, we present a variational learning approach for interaction-aware and multi-modal trajectory prediction based on deep generative neural networks. Our approach can achieve faster convergence and requires significantly fewer samples comparing to state-of-the-art methods. Experimental results on real and simulation data show that our model can effectively learn to infer different trajectories. We compare our method with three baseline approaches and present performance results demonstrating that our generative model can achieve higher accuracy for trajectory prediction by producing diverse trajectories.

C42. With Whome to Communicate: Learning Efficient Communication for Multi-Robot Collision Avoidance
A. Serra-Gomez, B. Brito, H. Zhu, J. J. Chung, J. Alonso-Mora. In Proc. IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS), 2020.

web pdf video
Abstract: Decentralized multi-robot systems typically perform coordinated motion planning by constantly broadcasting their intentions as a means to cope with the lack of a central system coordinating the efforts of all robots. Especially in complex dynamic environments, the coordination boost allowed by communication is critical to avoid collisions between cooperating robots. However, the risk of collision between a pair of robots fluctuates through their motion and communication is not always needed. Additionally, constant communication makes much of the still valuable information shared in previous time steps redundant. This paper presents an efficient communication method that solves the problem of "when" and with "whom" to communicate in multi-robot collision avoidance scenarios. In this approach, every robot learns to reason about other robots' states and considers the risk of future collisions before asking for the trajectory plans of other robots. We evaluate and verify the proposed communication strategy in simulation with four quadrotors and compare it with three baseline strategies: non-communicating, broadcasting and a distance-based method broadcasting information with quadrotors within a predefined distance.

C41. Anticipatory Vehicle Routing for Same-Day Pick-up and Delivery using Historical Data Clustering
J. van Lochem, M. Kronmueller, P. van 't Hof, J. Alonso-Mora. In Proc. IEEE Int. Conf. on Intelligent Transportation Systems (ITSC), 2020.

web pdf video
Abstract: In this paper we address the problem of same-day pick-up and delivery where a set of tasks are known a priori and a set of tasks are revealed during operation. The vehicle routes are precomputed based on the known and predicted requests and adjusted online as new requests are revealed. We propose a novel anticipatory insertion method which incorporates a set of predicted requests to beneficially adjust the routes of a fleet of vehicles in real-time. Requests are predicted based on historical data, which is clustered in advance. We exploit inherent patterns of the demand, which are captured by historical data and include them in a dynamic vehicle routing solver based on heuristics and adaptive large neighborhood search. The proposed method is evaluated using numerical simulations on a variety of real-world problems with up to 1655 requests per day. Their degree of dynamism ranges from 0.70 to 0.93. These instances represent dynamic multi-depot pickup and delivery problems with time windows. The method has shown to require less driven kilometers than comparable methods.

C40. Robust Vision-based Obstacle Avoidance for Micro Aerial Vehicles in Dynamic Environments
J. Liu, H. Zhu, J. Alonso-Mora. In Proc. IEEE Int. Conf. on Robotics and Automation (ICRA), 2020.

web pdf video
Abstract: In this paper, we present an on-board vision-based approach for avoidance of moving obstacles in dynamic environments. Our approach relies on an efficient obstacle detection and tracking algorithm based on depth image pairs, which provides the estimated position, velocity and size of the obstacles. Robust collision avoidance is achieved by formulating a chance-constrained model predictive controller (CC-MPC) to ensure that the collision probability between the micro aerial vehicle (MAV) and each moving obstacle is below a specified threshold. The method takes into account MAV dynamics, state estimation and obstacle sensing uncertainties. The proposed approach is implemented on a quadrotor equipped with a stereo camera and is tested in a variety of environments, showing effective on-line collision avoidance of moving obstacles.

2019

J20. Social behavior for autonomous vehicles
W. Schwarting, A. Pearson, J. Alonso-Mora, S. Karaman, D. Rus. In , Proceedings of the National Academy of Sciences USA (PNAS), 2019.

web pdf pdf-supplemental video
Abstract: We present a framework that integrates social psychology tools into controller design for autonomous vehicles. Our key insight utilizes Social Value Orientation (SVO), quantifying an agent’s degree of selfishness or altruism, which allows us to better predict driver behavior. We model interactions between human and autonomous agents with game theory and the principle of best response. Our unified algorithm estimates driver SVOs and incorporates their predicted trajectories into the autonomous vehicle’s control while respecting safety constraints. We study common-yet-difficult traffic scenarios: highway merging and unprotected left turns. Incorporating SVO reduces error in predictions by 25%, validated on 92 human driving merges. Furthermore, we find that merging drivers are more competitive than nonmerging drivers.

J19. Model Predictive Contouring Control for Collision Avoidance in Unstructured Dynamic Environments
B. Brito, B. Floor, L. Ferranti, J. Alonso-Mora. In , IEEE Robotics and Automation Letters (RA-L), 2019.

web pdf code video
Abstract: This paper presents a method for local motion planning in unstructured environments with static and moving obstacles, such as humans. Given a reference path and speed, our optimization-based receding-horizon approach computes a local trajectory that minimizes the tracking error while avoiding obstacles. We build on nonlinear model-predictive contouring control (MPCC) and extend it to incorporate a static map by computing, online, a set of convex regions in free space. We model moving obstacles as ellipsoids and provide a correct bound to approximate the collision region, given by the Minkowsky sum of an ellipse and a circle. Our framework is agnostic to the robot model. We present experimental results with a mobile robot navigating in indoor environments populated with humans. Our method is executed fully onboard without the need of external support and can be applied to other robot morphologies such as autonomous cars.

J18. Chance-constrained Collision Avoidance for MAVs in dynamic environments
H. Zhu, J. Alonso-Mora. In , IEEE Robotics and Automation Letters (RA-L), 2019.

web pdf code video
Abstract: Safe autonomous navigation of microair vehicles in cluttered dynamic environments is challenging due to the uncertainties arising from robot localization, sensing, and motion disturbances. This letter presents a probabilistic collision avoidance method for navigation among other robots and moving obstacles, such as humans. The approach explicitly considers the collision probability between each robot and obstacle and formulates a chance constrained nonlinear model predictive control problem (CCNMPC). A tight bound for approximation of collision probability is developed, which makes the CCNMPC formulation tractable and solvable in real time. For multirobot coordination, we describe three approaches, one distributed without communication (constant velocity assumption), one distributed with communication (of previous plans), and one centralized (sequential planning). We evaluate the proposed method in experiments with two quadrotors sharing the space with two humans and verify the multirobot coordination strategy in simulation with up to sixteen quadrotors.

C39. Optimizing Multi-class Fleet Compositions for Shared Mobility-as-a-Service
A. Wallar, W. Schwartig, J. Alonso-Mora, D. Rus. In Proc. IEEE Int. Conf. on Intelligent Transportation Systems (ITSC), 2019.

web pdf
Abstract: Previous studies examining ride-sharing potential assumed that rides can be shared as long as the incurred delay does not exceed a certain threshold. Conversely, we formulate willingness to share as a compensatory cost function at the individual passenger level. The latter considers trade-offs between delays caused by detours, travel discomfort related to sharing a vehicle and a fare discount associated with a shared ride. Next to finding how these behavioral preferences and the offered discount structure affect the efficiency and level of service of ride-sharing services, the effect of directionality in demand is considered. A graph-based approach is applied to perform an efficient assignment of vehicles to requests. We test the model on an experiment representing an urban context. Our findings suggest that service performance is strongly dependent on users’ willingness to share and somewhat less strongly on users’ tolerance to delays. Implementation of a ride-sharing service is most successful when directionality in demand is low, while ride-specific discounts can be effective in maximizing societal benefits.

C38. Optimizing Multi-class Fleet Compositions for Shared Mobility-as-a-Service
A. Wallar, W. Schwartig, J. Alonso-Mora, D. Rus. In Proc. IEEE Int. Conf. on Intelligent Transportation Systems (ITSC), 2019.

web pdf
Abstract: Mobility-as-a-Service (MaaS) systems are transforming the way society moves. The introduction and adoption of pooled ride-sharing has revolutionized urban transit with the potential of reducing vehicle congestion, improving accessibility and flexibility of a city's transportation infrastructure. Recently developed algorithms can compute routes for vehicles in realtime for a city-scale volume of requests, as well as optimize fleet sizes for MaaS systems that allow requests to share vehicles. Nonetheless, they are not capable of reasoning about the composition of a fleet and their varying capacity classes. In this paper, we present a method to not only optimize fleet sizes, but also their multi-class composition for MaaS systems that allow requests to share vehicles. We present an algorithm to determine how many vehicles of each class and capacity are needed, where they should be initialized, and how they should be routed to service all the travel demand for a given period of time. The algorithm maximizes utilization while reducing the total number of vehicles and incorporates constraints on wait- times and travel-delays. Finally, we evaluate the effectiveness of the algorithm for multi-class fleets with pooled ride-sharing using 426,908 historical taxi requests from Manhattan and 187,243 downtown Singapore. We show fleets comprised of vehicles with smaller capacities can reduce the total travel delay by 10% in Manhattan whereas larger capacity fleets in downtown Singapore contribute to a 9% reduction in the total waiting time.

C37. B-UAVC: Buffered Uncertainty-Aware Voronoi Cells for Probabilistic Multi-Robot Collision Avoidance
H. Zhu, J. Alonso-Mora. In Proc. 2nd IEEE International Symposium on Multi-Robot and Multi-Agent Systems (MRS'19), 2019.

web pdf video
Abstract: This paper presents B-UAVC, a distributed collision avoidance method for multi-robot systems that accounts for uncertainties in robot localization. In particular, Buffered Uncertainty-Aware Voronoi Cells (B-UAVC) are employed to compute regions where the robots can safely navigate. By computing a set of chance constraints, which guarantee that the robot remains within its B-UAVC, the method can be applied to non-holonomic robots. A local trajectory for each robot is then computed by introducing these chance constraints in a receding horizon model predictive controller. The method guarantees, under the assumption of normally distributed position uncertainty, that the collision probability between the robots remains below a specified threshold. We evaluate the proposed method with a team of quadrotors in simulations and in real experiments.

C36. SafeVRU: A Research Platform for the Interaction of Self-Driving Vehicles with Vulnerable Road Users
L. Ferranti, B. Brito, E. Pool, Y. Zheng, R. M. Ensing, R. Happee, B. Shyrokau, J. Kooij, J. Alonso-Mora, D. M. Gavrila. In Proc. IEEE Intelligent Vehicles Symposium, 2019.

web pdf video
Abstract: This paper presents our research platform Safe VRU for the interaction of self-driving vehicles with Vulnerable Road Users (VRUs, i.e., pedestrians and cyclists). The paper details the design (implemented with a modular structure within ROS) of the full stack of vehicle localization, environment perception, motion planning, and control, with emphasis on the environment perception and planning modules. The environment perception detects the VRUs using a stereo camera and predicts their paths with Dynamic Bayesian Networks (DBNs), which can account for switching dynamics. The motion planner is based on model predictive contouring control (MPCC) and takes into account vehicle dynamics, control objectives (e.g., desired speed), and perceived environment (i.e., the predicted VRU paths with behavioral uncertainties) over a certain time horizon. We present simulation and real-world results to illustrate the ability of our vehicle to plan and execute collision-free trajectories in the presence of VRUs.

C35. Optimizing Vehicle Distributions and Fleet Sizes for Mobility-on-Demand
A. Wallar, J. Alonso-Mora, D. Rus. In Proc. IEEE Int. Conf. on Robotics and Automation (ICRA), 2019.

web pdf
Abstract: Mobility-on-demand (MoD) systems are revolutionizing urban transit with the introduction of ride-sharing. Such systems have the potential to reduce vehicle congestion and improve accessibility of a city's transportation infrastructure. Recently developed algorithms can compute routes for vehicles in real-time for a city-scale volume of requests while allowing vehicles to carry multiple passengers at the same time. However, these algorithms focus on optimizing the performance for a given fleet of vehicles and do not tell us how many vehicles are needed to service all the requests. In this paper, we present an offline method to optimize the vehicle distributions and fleet sizes on historical demand data for MoD systems that allow passengers to share vehicles. We present an algorithm to determine how many vehicles are needed, where they should be initialized, and how they should be routed to service all the travel demand for a given period of time. Evaluation using 23,529,740 historical taxi requests from one month in Manhattan shows that on average 2864 four passenger vehicles are needed to service all of the taxi demand in a day with an average added travel delay of 2.8 mins.

C34. Distributed Multi-Robot Formation Splitting and Merging in Dynamic Environments
H. Zhu, J. Juhl, L. Ferranti, J. Alonso-Mora. In Proc. IEEE Int. Conf. on Robotics and Automation (ICRA), 2019.

web pdf video
Abstract: This paper presents a distributed method for splitting and merging of multi-robot formations in dynamic environments with static and moving obstacles. Splitting and merging actions rely on distributed consensus and can be performed to avoid obstacles. Our method accounts for the limited communication range and visibility radius of the robots and relies on the communication of obstacle-free convex regions and the computation of an intersection graph. In addition, our method is able to detect and recover from (permanent and temporary) communication and motion faults. Finally, we demonstrate the applicability and scalability of the proposed method in simulations with up to sixteen quadrotors and real-world experiments with a team of four quadrotors.

2018

J17. Flycon: Real-time Environment-independent Multi-view Human Pose Estimation with Aerial Vehicles
T. Naegeli, S. Oberholzer, S. Pluess, J. Alonso-Mora, O. Hilliges. In , ACM Transactions on Graphics (SIGGRAPH Asia), 2018.

web pdf video
Abstract: We propose a real-time method for the infrastructure-free estimation of articulated human motion. The approach leverages a swarm of camera-equipped flying robots and jointly optimizes the swarm's and skeletal states, which include the 3D joint positions and a set of bones. Our method allows to track the motion of human subjects, for example an athlete, over long time horizons and long distances, in challenging settings and at large scale, where fixed infrastructure approaches are not applicable. The proposed algorithm uses active infra-red markers, runs in real-time and accurately estimates robot and human pose parameters online without the need for accurately calibrated or stationary mounted cameras. Our method i) estimates a global coordinate frame for the MAV swarm, ii) jointly optimizes the human pose and relative camera positions, and iii) estimates the length of the human bones. The entire swarm is then controlled via a model predictive controller to maximize visibility of the subject from multiple viewpoints even under fast motion such as jumping or jogging. We demonstrate our method in a number of difficult scenarios including capture of long locomotion sequences at the scale of a triplex gym, in non-planar terrain, while climbing and in outdoor scenarios.

J16. Planning and Decision-Making for Autonomous Vehicles
W. Schwarting, J. Alonso-Mora, D. Rus. In Annual Review of Control, Robotics, and Autonomous Systems, vol. 1, pp. 187-210, 2018.

web pdf
Abstract: In this review, we provide an overview of emerging trends and challenges in the field of intelligent and autonomous, or self-driving, vehicles. Recent advances in the field of perception, planning, and decision-making for autonomous vehicles have led to great improvements in functional capabilities, with several prototypes already driving on our roads and streets. Yet challenges remain regarding guaranteed performance and safety under all driving circumstances. For instance, planning methods that provide safe and system-compliant performance in complex, cluttered environments while modeling the uncertain interaction with other traffic participants are required. Furthermore, new paradigms, such as interactive planning and end-to-end learning, open up questions regarding safety and reliability that need to be addressed. In this survey, we emphasize recent approaches for integrated perception and planning and for behavior-aware planning, many of which rely on machine learning. This raises the question of verification and safety, which we also touch upon. Finally, we discuss the state of the art and remaining challenges for managing fleets of autonomous vehicles.

J15. Cooperative Collision Avoidance for Nonholonomic Robots
J. Alonso-Mora, P. Beardsley, R. Siegwart. In IEEE Transactions on Robotics, vol. 34, no. 2, pp. 404-420, 2018.

web pdf video
Abstract: In this paper, we present a method, namely € CCA, for collision avoidance in dynamic environments among interacting agents, such as other robots or humans. Given a preferred motion by a global planner or driver, the method computes a collision-free local motion for a short time horizon, which respects the actuator constraints and allows for smooth and safe control. The method builds on the concept of reciprocal velocity obstacles and extends it to respect the kinodynamic constraints of the robot and account for a grid-based map representation of the environment. The method is best suited for large multirobot settings, including heterogeneous teams of robots, in which computational complexity is of paramount importance and the robots interact with one another. In particular, we consider a set of motion primitives for the robot and solve an optimization in the space of control velocities with additional constraints. Additionally, we propose a cooperative approach to compute safe velocity partitions in the distributed case. We describe several instances of the method for distributed and centralized operation and formulated both as convex and nonconvex optimizations. We compare the different variants and describe the benefits and tradeoffs both theoretically and in extensive experiments with various robotic platforms: robotic wheelchairs, robotic boats, humanoid robots, small unicycle robots, and simulated cars.

J14. Reactive mission and motion planning with deadlock resolution avoiding dynamic obstacles
J. Alonso-Mora, J. A. DeCastro, V. Raman, D. Rus, H. Kress-Gazit. In Autonomous Robots, Special Issue on Online Decision Making in Multi-Robot Coordination, vol. 42, no. 4, pp. 801–824, 2018.

web pdf video
Abstract: In the near future mobile robots, such as personal robots or mobile manipulators, will share the workspace with other robots and humans. We present a method for mission and motion planning that applies to small teams of robots performing a task in an environment with moving obstacles, such as humans. Given a mission specification written in linear temporal logic, such as patrolling a set of rooms, we synthesize an automaton from which the robots can extract valid strategies. This centralized automaton is executed by the robots in the team at runtime, and in conjunction with a distributed motion planner that guarantees avoidance of moving obstacles. Our contribution is a correct-by-construction synthesis approach to multi-robot mission planning that guarantees collision avoidance with respect to moving obstacles, guarantees satisfaction of the mission specification and resolves encountered deadlocks, where a moving obstacle blocks the robot temporally. Our method provides conditions under which deadlock will be avoided by identifying environment behaviors that, when encountered at runtime, may prevent the robot team from achieving its goals. In particular, (1) it identifies deadlock conditions; (2) it is able to check whether they can be resolved; and (3) the robots implement the deadlock resolution policy locally in a distributed manner. The approach is capable of synthesizing and executing plans even with a high density of dynamic obstacles. In contrast to many existing approaches to mission and motion planning, it is scalable with the number of moving obstacles. We demonstrate the approach in physical experiments with walking humanoids moving in 2D environments and in simulation with aerial vehicles (quadrotors) navigating in 2D and 3D environments.

J13. Distributed Formation Control in Dynamic Environments
J. Alonso-Mora, E. Montijano, T. Naegeli, O. Hilliges, M. Schweger, D. Rus. In , Autonomous Robots, 2018.

web pdf video
Abstract: This paper presents a distributed method for formation control of a homogeneous team of aerial or ground mobile robots navigating in environments with static and dynamic obstacles. Each robot in the team has a finite communication and visibility radius and shares information with its neighbors to coordinate. Our approach leverages both constrained optimization and multi-robot consensus to compute the parameters of the multi-robot formation. This ensures that the robots make progress and avoid collisions with static and moving obstacles. In particular, via distributed consensus, the robots compute (a) the convex hull of the robot positions, (b) the desired direction of movement and (c) a large convex region embedded in the four dimensional position-time free space. The robots then compute, via sequential convex programming, the locally optimal parameters for the formation to remain within the convex neighborhood of the robots. The method allows for reconfiguration. Each robot then navigates towards its assigned position in the target collision-free formation via an individual controller that accounts for its dynamics. This approach is efficient and scalable with the number of robots. We present an extensive evaluation of the communication requirements and verify the method in simulations with up to sixteen quadrotors. Lastly, we present experiments with four real quadrotors flying in formation in an environment with one moving human.

J12. Sample Efficient Learning of Path Following and Obstacle Avoidance Behavior for Quadrotors
S. Stevsic, T. Naegeli, J. Alonso-Mora, O. Hilliges. In IEEE Robotics and Automation Letters, 2018.

web pdf video
Abstract: In this paper we propose an algorithm for the training of neural network control policies for quadrotors. The learned control policy computes control commands directly from sensor inputs and is hence computationally efficient. An imitation learning algorithm produces a policy that reproduces the behavior of a path following control algorithm with collision avoidance. Due to the generalization ability of neural networks, the resulting policy performs local collision avoidance of unseen obstacles while following a global reference path. The algorithm uses a time-free model predictive path-following controller as a supervisor. The controller generates demonstrations by following few example paths. This enables an easy to implement learning algorithm that is robust to errors of the model used in the model predictive controller. The policy is trained on the real quadrotor, which requires collision-free exploration around the example path. An adapted version of the supervisor is used to enable exploration. Thus, the policy can be trained from a relatively small number of examples on the real quadrotor, making the training sample efficient.

C33. The Impact of Ridesharing in Mobility-on-Demand Systems: Simulation Case Study in Prague
D. Fiedler, M. Certicky, J. Alonso-Mora, M. Cap. In Proc. IEEE Int. Conf. on Intelligent Transportation Systems (ITSC), 2018.

web pdf
Abstract: In densely populated-cities, the use of private cars for personal transportation is unsustainable, due to high parking and road capacity requirements. The mobility-on-demand systems have been proposed as an alternative to a private car. Such systems consist of a fleet of vehicles that the user of the system can hail for one-way point-to-point trips. These systems employ large-scale vehicle sharing, i.e., one vehicle can be used by several people during one day and consequently, the fleet size and the parking space requirements can be reduced, but, at the cost of a non-negligible increase in vehicles miles driven in the system. The miles driven in the system can be reduced by ridesharing, where several people traveling in a similar direction are matched and travel in one vehicle. We quantify the potential of ridesharing in a hypothetical mobility-on-demand system designed to serve all trips that are currently realized by private car in the city of Prague. Our results show that by employing a ridesharing strategy that guarantees travel time prolongation of no more than 10 minutes, the average occupancy of a vehicle will increase to 2.7 passengers. Consequently, the number of vehicle miles traveled will decrease to 35% of the amount in the MoD system without ridesharing and to 60% of the amount in the present state.

C32. Vehicle Rebalancing for Mobility-on-Demand Systems with Ride-Sharing
A. Wallar, M. van der Zee, J. Alonso-Mora, D. Rus. In Proc. of the IEEE/RSJ Conf. on Robotics and Intelligent Systems (IROS), 2018.

web pdf
Abstract: Recent developments in Mobility-on-Demand (MoD) systems have demonstrated the potential of road vehicles as an efficient mode of urban transportation Newly developed algorithms can compute vehicle routes in real-time for batches of requests and allow for multiple requests to share vehicles. These algorithms have primarily focused on optimally producing vehicle schedules to pick up and drop off requests. The redistribution of idle vehicles to areas of high demand, known as rebalancing, on the contrary has received little attention in the context of ride-sharing. In this paper, we present a method to rebalance idle vehicles in a ride-sharing enabled MoD fleet. This method consists of an algorithm to optimally partition the fleet operating area into rebalancing regions, an algorithm to determine a real-time demand estimate for every region using incoming requests, and an algorithm to optimize the assignment of idle vehicles to these rebalancing regions using an integer linear program. Evaluation with historical taxi data from Manhattan shows that we can service 99.8% of taxi requests in Manhattan using 3000 vehicles with an average waiting time of 57.4 seconds and an average in-car delay of 13.7 seconds. Moreover, we can achieve a higher service rate using 2000 vehicles than prior work achieved with 3000. Furthermore, with a fleet of 3000 vehicles, we reduce the average travel delay by 86%, the average waiting time by 37%, and the amount of ignored requests by 95% compared to earlier work at the expense of an increased distance travelled by the fleet.

C31. Multi-Objective Analysis of Ridesharing in Automated Mobility-on-Demand
M. Cap, J. Alonso-Mora. In Proc. Robotics: Science and Systems (RSS), 2018.

web pdf
Abstract: Self-driving technology is expected to enable the realization of large-scale mobility-on-demand systems that employ massive ridesharing. The technology is being celebrated as a potential cure for urban congestion and others negative externalities of individual automobile transportation. In this paper, we quantify the potential of ridesharing with a fleet of autonomous vehicles by considering all possible trade-offs between the quality of service and operation cost of the system that can be achieved by sharing rides. We formulate a multi-objective fleet routing problem and present a solution technique that can compute Pareto-optimal fleet operation plans that achieve different trade- offs between the two objectives. Given a set of requests and a set of vehicles, our method can recover a trade-off curve that quantifies the potential of ridesharing with given fleet. We provide a formal optimality proof and demonstrate that the proposed method is scalable and able to compute such trade-off curves for instances with hundreds of vehicles and requests optimally. Such an analytical tool helps with systematic design of shared mobility system, in particular, it can be used to make principled decisions about the required fleet size.

C30. Coordination of Multiple Vessels Via Distributed Nonlinear Model Predictive Control
L. Ferranti, R. R. Negenborn, T. Keviczky, J. Alonso-Mora. In Proc. European Control Conference (ECC), 2018.

web pdf video
Abstract: This work presents a method for multi-robot trajectory planning and coordination based on nonlinear model predictive control (NMPC). In contrast to centralized approaches, we consider the distributed case where each robot has an on-board computation unit to solve a local NMPC problem and can communicate with other robots in its neighborhood. We show that, thanks to tailored interactions (i.e., interactions designed according to a nonconvex alternating direction method of multipliers, or ADMM, scheme), the proposed solution is equivalent to solving the centralized control problem. With some communication exchange, required by the ADMM scheme at given synchronization steps, the safety of the robots is preserved, that is, collisions with neighboring robots are avoided and the robots stay within the bounds of the environment. In this work, we tested the proposed method to coordinate three autonomous vessels at a canal intersection. Nevertheless, the proposed approach is general and can be applied to different applications and robot models.

C29. Joint Multi-Policy Behavior Estimation and Receding-Horizon Trajectory Planning for Automated Urban Driving
B. Zhou, W. Schwarting, D. Rus, J. Alonso-Mora. In Proc. IEEE Int. Conf. on Robotics and Automation (ICRA), 2018.

web pdf video spotlight video exp
Abstract: When driving in urban environments, an autonomous vehicle must account for the interaction with other traffic participants. It must reason about their future behavior, how its actions affect their future behavior, and potentially consider multiple motion hypothesis. In this paper we introduce a method for joint behavior estimation and trajectory planning that models interaction and multi-policy decision-making. The method leverages Partially Observable Markov Decision Processes to estimate the behavior of other traffic participants given the planned trajectory for the ego-vehicle, and Receding-Horizon Control for generating safe trajectories for the ego-vehicle. To achieve safe navigation we introduce chance constraints over multiple motion policies in the receding-horizon planner. These constraints account for uncertainty over the behavior of other traffic participants. The method is capable of running in real-time and we show its performance and good scalability in simulated multi-vehicle intersection scenarios.

2017

J11. Safe Nonlinear Trajectory Generation for Parallel Autonomy With a Dynamic Vehicle Model
W. Schwarting, J. Alonso-Mora, L. Paull, S. Karaman, D. Rus. In IEEE Transactions on Intelligent Transportation Systems, 2017.

web pdf video
Abstract: High-end vehicles are already equipped with safety systems, such as assistive braking and automatic lane following, enhancing vehicle safety. Yet, these current solutions can only help in low-complexity driving situations. In this paper, we introduce a parallel autonomy, or shared control, framework that computes safe trajectories for an automated vehicle, based on human inputs. We minimize the deviation from the human inputs while ensuring safety via a set of collision avoidance constraints. Our method achieves safe motion even in complex driving scenarios, such as those commonly encountered in an urban setting. We introduce a receding horizon planner formulated as nonlinear model predictive control (NMPC), which includes the analytic descriptions of road boundaries and the configuration and future uncertainties of other road participants. The NMPC operates over both steering and acceleration simultaneously. We introduce a nonslip model suitable for handling complex environments with dynamic obstacles, and a nonlinear combined slip vehicle model including normal load transfer capable of handling static environments. We validate the proposed approach in two complex driving scenarios. First, in an urban environment that includes a left-turn across traffic and passing on a busy street. And second, under snow conditions on a race track with sharp turns and under complex dynamic constraints. We evaluate the performance of the method with various human driving styles. We consequently observe that the method successfully avoids collisions and generates motions with minimal intervention for parallel autonomy. We note that the method can also be applied to generate safe motion for fully autonomous vehicles.

J10. Multi-robot Formation Control and Object Transport in Dynamic Environments via Constrained Optimization
J. Alonso-Mora, S. Baker, D. Rus. In The International Journal of Robotics Research, Vol 36, Issue 9, pp. 1000-1021, 2017.

web pdf video
Abstract: We present a constrained optimization method for multi-robot formation control in dynamic environments, where the robots adjust the parameters of the formation, such as size and three-dimensional orientation, to avoid collisions with static and moving obstacles, and to make progress towards their goal. We describe two variants of the algorithm, one for local motion planning and one for global path planning. The local planner first computes a large obstacle-free convex region in a neighborhood of the robots, embedded in position-time space. Then, the parameters of the formation are optimized therein by solving a constrained optimization, via sequential convex programming. The robots navigate towards the optimized formation with individual controllers that account for their dynamics. The idea is extended to global path planning by sampling convex regions in free position space and connecting them if a transition in formation is possible - computed via the constrained optimization. The path of lowest cost to the goal is then found via graph search. The method applies to ground and aerial vehicles navigating in two- and three-dimensional environments among static and dynamic obstacles, allows for reconfiguration, and is efficient and scalable with the number of robots. In particular, we consider two applications, a team of aerial vehicles navigating in formation, and a small team of mobile manipulators that collaboratively carry an object. The approach is verified in experiments with a team of three mobile manipulators and in simulations with a team of up to sixteen Micro Air Vehicles (quadrotors).

J9. Real-time Planning for Automated Multi-View Drone Cinematography
T. Naegeli, L. Meier, A. Domahidi, J. Alonso-Mora, O. Hilliges. In ACM Transactions on Graphics SIGGRAPH, vol. 36, no. 4, Article 132, 2017.

web pdf video
Abstract: We propose a method for automated aerial videography in dynamic and cluttered environments. An online receding horizon optimization formulation facilitates the planning process for novices and experts alike. The algorithm takes high-level plans as input, which we dub virtual rails, alongside interactively defined aesthetic framing objectives and jointly solves for 3D quadcopter motion plans and associated velocities. The method generates control inputs subject to constraints of a non-linear quadrotor model and dynamic constraints imposed by actors moving in an a priori unknown way. The output plans are physically feasible, for the horizon length, and we apply the resulting control inputs directly at each time-step, without requiring a separate trajectory tracking algorithm. The online nature of the method enables incorporation of feedback into the planning and control loop, makes the algorithm robust to disturbances. Furthermore, we extend the method to include coordination between multiple drones to enable dynamic multi-view shots, typical for action sequences and live TV coverage. The algorithm runs in real-time on standard hardware and computes motion plans for several drones in the order of milliseconds. Finally, we evaluate the approach qualitatively with a number of challenging shots, involving multiple drones and actors and qualitatively characterize the computational performance experimentally.

J8. Real-time Motion Planning for Aerial videography with Dynamic Obstacle Avoidance and Viewpoint Optimization
T. Naegeli, J. Alonso-Mora, A. Domahidi, D. Rus, O. Hilliges. In , in IEEE Robotics and Automation Letters, vol. 2, no. 3, pp. 1696-1703, 2017.

web pdf video
Abstract: We propose a method for real-time trajectory generation with applications in aerial videography. Taking framing objectives, such as position of targets in the image plane, as input, our method solves for robot trajectories and gimbal controls automatically and adapts plans in real time due to changes in the environment. We contribute a real-time receding horizon planner that autonomously records scenes with moving targets, while optimizing for visibility under occlusion and ensuring collision-free trajectories. A modular cost function, based on the reprojection error of targets, is proposed that allows for flexibility and artistic freedom and is well behaved under numerical optimization. We formulate the minimization problem under constraints as a finite horizon optimal control problem that fulfills aesthetic objectives, adheres to nonlinear model constraints of the filming robot and collision constraints with static and dynamic obstacles and can be solved in real time. We demonstrate the robustness and efficiency of the method with a number of challenging shots filmed in dynamic environments including those with moving obstacles and shots with multiple targets to be filmed simultaneously.

J7. On-demand High-capacity Ride-sharing via Dynamic Trip-Vehicle Assignment
J. Alonso-Mora, S. Samaranayake, A. Wallar, E. Frazzoli, D. Rus. In Proceedings of the National Academy of Sciences of the USA (PNAS), vol. 114, no. 3, pp. 462-467, 2017.

web pdf pdf-supplemental-method video
Abstract: Ride-sharing services can provide not only a very personalized mobility experience but also ensure efficiency and sustainability via large-scale ride pooling. Large-scale ride-sharing requires mathematical models and algorithms that can match large groups of riders to a fleet of shared vehicles in real time, a task not fully addressed by current solutions. We present a highly scalable anytime optimal algorithm and experimentally validate its performance using New York City taxi data and a shared vehicle fleet with passenger capacities of up to ten. Our results show that 2,000 vehicles (15% of the taxi fleet) of capacity 10 or 3,000 of capacity 4 can serve 98% of the demand within a mean waiting time of 2.8 min and mean trip delay of 3.5 min.

C28. Compositional and Contract-based Verification for Autonomous Driving on Road Networks
L. Liebenwein, W. Schwarting, C.-I. Vasile, J. DeCastro, J. Alonso-Mora, S. Karaman, D. Rus. In , in Proc. of the Int. Symp. on Robotics Research (ISRR), 2017.

web pdf video
Abstract: Recent advances in autonomous driving have raised the problem of safety to the forefront and incentivized research into establishing safety guarantees. In this paper, we propose a safety verification framework as a safety standard for driving controllers with full or shared autonomy based on compositional and contract-based principles. Our framework enables us to synthesize safety guarantees over entire road networks by first building a library of locally verified models, and then composing local models together to verify the entire network. Composition is achieved using assume- guarantee contracts that are synthesized concurrently during verification. Thus, we can reuse local models within and across networks, add additional models to cover local road geometries without re-verifying the entire library, and perform all com- putations in a parallel and distributed way, which enables computational tractability. Furthermore, we employ controller contracts such that any controller satisfying them can be certified safe. We demonstrate the practical effectiveness of our framework by certifying controllers over parts of the Manhattan road network.

C27. Predictive Routing for Autonomous Mobility-on-Demand Systems with Ride-Sharing
J. Alonso-Mora, A. Wallar, D. Rus. In Proc. of the IEEE/RSJ Conf. on Robotics and Intelligent Systems (IROS), 2017.

web pdf video
Abstract: Ride-sharing, or carpooling, systems with autonomous vehicles will provide efficient and reliable urban mobility on demand. In this work we present a method for dynamic vehicle routing that leverages historical data to improve the performance of a network of self-driving taxis. In particular, we describe a constrained optimization method capable of assigning requests to autonomous vehicles in an informed way, to minimize the expected cost of serving both current and future travel requests. We allow several passengers with independent trips to share a vehicle and allow vehicles to pick additional passengers as they progress through their route. Based on historical data, we compute a probability distribution over future demand. Then, samples from the learned probability distribution are incorporated into a decoupled vehicle routing and passenger assignment method to take into account the predicted future demand. This method consists of three steps, namely pruning of feasible trips, assignment of trips to vehicles and rebalancing of idle vehicles. We show the benefits and trade-offs of this predictive approach in an experimental evaluation with over three million rides extracted from a dataset of taxi trips in New York City. Our method produces routes and assignments that, in expectation, reduce the travel and waiting times for passengers, with respect to a purely reactive approach. Besides the mobility on demand application, the method we present is general and could also be applied to other multi-task multi-vehicle assignment and routing problems.

C26. Robust Collision Avoidance for Multiple Micro Aerial Vehicles Using Nonlinear Model Predictive Control
M. Kamel, J. Alonso-Mora, R. Siegwart, J. Nieto. In Proc. of the IEEE/RSJ Conf. on Robotics and Intelligent Systems (IROS), 2017.

web pdf video
Abstract: When several Multirotor Micro Aerial Vehicles (MAVs) share the same airspace, reliable and robust collision avoidance is required. In this paper we address the problem of multi-MAV reactive collision avoidance. We employ a model-based controller to simultaneously track a reference trajectory and avoid collisions. Moreover, to achieve a higher degree of robustness, our method also accounts for the uncertainty of the state estimator and of the position and velocity of the other agents. The proposed approach is decentralized, does not require a collision-free reference trajectory and accounts for the full MAV dynamics. We validated our approach in simulation and experimentally with two MAV.

C25. Trajectory Optimization for Autonomous Overtaking with Visibility Maximization
H. Andersen, W. Schwarting, F. Naser, Y. H. Eng, M. H. Ang Jr, D. Rus, J. Alonso-Mora. In proc. IEEE Intelligent Transportation Systems Conference, 2017.

web pdf video
Abstract: In this paper we present a trajectory generation method for autonomous overtaking of static obstacles in a dynamic urban environment. In these settings, blind spots can arise from perception limitations. For example, the autonomous car may have to move slightly into the opposite lane in order to cleanly see in front of a car ahead. Once it has gathered enough information about the road ahead, then the autonomous car can safely overtake. We generate safe trajectories by solving, in real-time, a non-linear constrained optimization, formulated as a Receding Horizon planner. The planner is guided by a high-level state machine, which determines when the overtake maneuver should begin. Our main contribution is a method that can maximize visibility, prioritizes safety and respects the boundaries of the road while executing the maneuver. We present experimental results in simulation with data collected during real driving.

C24. Foresight: Remote Sensing For Autonomous Vehicles Using a Small Unmanned Aerial Vehicle
A. Wallar, B. Araki, R. Chang, J. Alonso-Mora, D. Rus. In Proc. of the Conf. on Field and Service Robotics (FSR), 2017.

web pdf video
Abstract: A large number of traffic accidents, especially those involving vulnerable road users such as pedestrians and cyclists, are due to blind spots for the driver, for example when a vehicle takes a turn with poor visibility or when a pedestrian crosses from behind a parked vehicle. In these accidents, the consequences for the vulnerable road users are dramatic. Autonomous cars have the potential to drastically reduce traffic accidents thanks to high-performance sensing and reasoning. However, their perception capabilities are still limited to the field of view of their sensors. We propose to extend the perception capabilities of a vehicle, autonomous or human-driven, with a small Unmanned Aerial Vehicle (UAV) capable of taking off from the car, flying around corners to gather additional data from blind spots and landing back on the car after a mission. We present a holistic framework to detect blind spots in the map that is built by the car, plan an informative path for the drone, and detect potential threats occluded to the car. We have tested our approach with an autonomous car equipped with a drone.

C23. A Parallel Autonomy Research Platform
F. Naser, D. Dorhout, S. Proulx, S. D. Pendleton, H. Andersen, W. Schwarting, L. Paull, J. Alonso-Mora, M. H. Ang Jr., S. Karaman, R. Tedrake, J. Leonard, D. Rus. In Proc. of the IEEE Symposium on Intelligent Vehicles (IV), 2017.

web pdf video
Abstract: We present the development of a full-scale “parallel autonomy” research platform including software and hardware. In the parallel autonomy paradigm, the control of the vehicle is shared; the human is still in control of the vehicle, but the autonomy system is always running in the background to prevent accidents. Our holistic approach includes: (1) a drive-by-wire conversion method only based on reverse engineering mounting of relatively inexpensive sensors onto the vehicle implementation of a localization and mapping system, (4) obstacle detection and (5) a shared controller as well as (6) integration with an advanced autonomy simulation system (Drake) for rapid development and testing. The system can operate in three modes: (a) manual driving, (b) full autonomy, where the system is in complete control of the vehicle and (c) parallel autonomy, where the shared controller is implemented. We present results from extensive testing of a full-scale vehicle on closed tracks that demonstrate these capabilities.

C22. Parallel Autonomy in Automated Vehicles: Safe Motion Generation with Minimal Intervention
W. Schwarting, J. Alonso-Mora, L. Paull, S. Karaman, D. Rus. In Proc. of the IEEE Int. Conf. on Robotics and Automation (ICRA), 2017.

web pdf video
Abstract: Current state-of-the-art vehicle safety systems, such as assistive braking or automatic lane following, are still only able to help in relatively simple driving situations. We introduce a Parallel Autonomy shared-control framework that produces safe trajectories based on human inputs even in much more complex driving scenarios, such as those commonly encountered in an urban setting. We minimize the deviation from the human inputs while ensuring safety via a set of collision avoidance constraints. We develop a receding horizon planner formulated as a Non-linear Model Predictive Control (NMPC) including analytic descriptions of road boundaries, and the configurations and future uncertainties of other traffic participants, and directly supplying them to the optimizer without linearization. The NMPC operates over both steering and acceleration simultaneously. Furthermore, the proposed receding horizon planner also applies to fully autonomous vehicles. We validate the proposed approach through simulations in a wide variety of complex driving scenarios such as left-turns across traffic, passing on busy streets, and under dynamic constraints in sharp turns on a race track.

C21. Duckietown: an Open, Inexpensive and Flexible Platform for Autonomy Education and Research
L. Paull, J. Tani, H. Ahn, J. Alonso-Mora, L. Carlone, M. Cap, Y. F. Chen, C. Choi, J. Dusek, Y. Fang, D. Hoehener, S.-Y. Liu, M. Novitzky, I. F. Okuyama, J. Pazis, G. Rosman, V. Varricchio, H.-C. Wang, D. S. Yershov, H. Zhao, M. Benjamin, C. Carr, M. T. Zuber, S. Karaman, E. Frazzoli, D. Del Vecchio, D. Rus, J. P. How, J. J. Leonard, A. Censi. In Proc. of the IEEE Int. Conf. on Robotics and Automation (ICRA), 2017.

web pdf video
Abstract: Duckietown is an open, inexpensive and flexible platform for autonomy education and research. The platform comprises small autonomous vehicles (“Duckiebots”) built from off-the-shelf components, and cities (“Duckietowns”) complete with roads, signage, traffic lights, obstacles, and citizens (duckies) in need of transportation. The Duckietown platform offers a wide range of functionalities at a low cost. Duckiebots sense the world with only one monocular camera and perform all processing onboard with a Raspberry Pi 2, yet are able to: follow lanes while avoiding obstacles, pedestrians (duckies) and other Duckiebots, localize within a global map, navigate a city, and coordinate with other Duckiebots to avoid collisions. Duckietown is a useful tool since educators and researchers can save money and time by not having to develop all of the necessary supporting infrastructure and capabilities. All materials are available as open source, and the hope is that others in the community will adopt the platform for education and research.

2016

J6. Data Materialities Art Gallery: Introduction and Gallery
J. Brucker-Cohen, T. Bech, A. Rowe, G. Bushell, L. Birtles, C. Bennewith, O. Bown, D. Sun, P. Su, N. Roy, V. Jan, D. Morozov, T. Digumarti, J. Alonso-Mora, R. Siegwart, P. Beardsley, M. Jacobsen, D.A. Chanel, R. Constant, B. Grosser. In Leonardo, vol. 49, no. 4, pp. 352-374, MIT Press Journals, 2016.

web video

C20. Distributed Multi-Robot Navigation in Formation among Obstacles: A Geometric and Optimization Approach with Consensus
J. Alonso-Mora, E. Montijano, M. Schwager, D. Rus. In , in Proc. of the IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (ICRA), 2016.

web pdf video
Abstract: This paper presents a distributed method for navigating a team of robots in formation in 2D and 3D environments with static and dynamic obstacles. The robots are assumed to have a reduced communication and visibility radius and share information with their neighbors. Via distributed consensus the robots compute (a) the convex hull of the robot positions and (b) the largest convex region within free space. The robots then compute, via sequential convex programming, the locally optimal parameters for the formation within this convex neighborhood of the robots. Reconfiguration is allowed, when required, by considering a set of target formations. The robots navigate towards the target collision-free formation with individual local planners that account for their dynamics. The approach is efficient and scalable with the number of robots and performs well in simulations with up to sixteen quadrotors.

C19. Pixelbots 2014
T. Digumarti, J. Alonso-Mora, R. Siegwart, P. Beardsley. In Proc. ACM SIGGRAPH 2016 Art Gallery (SIGGRAPH '16), ACM, New York, NY, USA, 366-367, 2016.

web pdf video
Abstract: In today's digital media landscape, we are constantly surrounded by displays, from the LCDs found on the phones in our pockets to the ubiquitous screens that greet us whenever we enter a store, airport, taxicab, doctor's office, or educational institution. This plethora of displays both allures us and contributes to the media's saturation of our lives. The truth remains that we are never far from the next form of information display. Disney Research's Pixelbots takes this truth as an inevitability and brings the display into a kinetic form, breaking the screen out of the confines of a rectangular or oval experience. Billed as "Pixels with Personality," the Pixelbots' enticing presence rests on our ability to project human qualities onto objects that move as we do in physical space.

2015

J5. Collision Avoidance for Aerial Vehicles in Multi-Agent Scenarios
J. Alonso-Mora, T. Naegeli, R. Siegwart, P. Beardsley. In , Autonomous Robots, vol. 39, no. 1, pp. 101–121, 2015.

web pdf video
Abstract: This article describes an investigation of local motion planning, or collision avoidance, for a set of decision-making agents navigating in 3D space. The method is applicable to agents which are heterogeneous in size, dynamics and aggressiveness. It builds on the concept of velocity obstacles (VO), which characterizes the set of trajectories that lead to a collision between interacting agents. Motion continuity constraints are satisfied by using a trajectory tracking controller and constraining the set of available local trajectories in an optimization. Collision-free motion is obtained by selecting a feasible trajectory from the VO’s complement, where reciprocity can also be encoded. Three algorithms for local motion planning are presented—(1) a centralized convex optimization in which a joint quadratic cost function is minimized subject to linear and quadratic constraints, (2) a distributed convex optimization derived from (1), and (3) a centralized non-convex optimization with binary variables in which the global optimum can be found, albeit at higher computational cost. A complete system integration is described and results are presented in experiments with up to four physical quadrotors flying in close proximity, and in experiments with two quadrotors avoiding a human.

C18. Multi-robot navigation in formation via sequential convex programming
J. Alonso-Mora, S. Baker, D. Rus. In Proc. of the IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS), 2015.

web pdf video
Abstract: This paper presents a method for navigating a team of robots in formation in 2D and 3D environments with static and dynamic obstacles. The method is local and computes the optimal parameters for the formation within a neighborhood of the robots, allowing for reconfigurations, when required, by considering a set of target formations. The method consists of first computing the largest collision-free convex polytope in a neighborhood of the robots, followed by a constrained optimization via sequential convex programming where the optimal parameters for the formation are obtained. The robots navigate towards the target collision-free formation with individual local planners that account for their dynamics. The approach is efficient and scalable with the number of robots and performed well in simulations with a large team of quadrators and in experiments with two mobile manipulators carrying a rigid object.

C17. Collision-Free Reactive Mission and Motion Planning for Multi-Robot Systems
J. DeCastro, J. Alonso-Mora, V. Raman, D. Rus, H. Kress-Gezit. In Proc. of the Int. Symposium on Robotics Research (ISRR), 2015.

web pdf video
Abstract: This paper describes a holistic method for automatically synthesizing controllers for a team of robots operating in an environment shared with other agents. The proposed approach builds on recent advances in Reactive Mission Planning using Linear Temporal Logic, and Local Motion Planning using convex optimization. A local planner enforces the dynamic constraints of the robot and guarantees collision avoidance in 2D and 3D workspaces. A reactive mission planner takes a high-level specification that captures complex motion sequencing, and generates a correct-by-construction controller guaranteed to achieve the specified behavior and be reactive to sensor events. If there is no controller that fulfills the specification because of possible deadlock in the local planner, a minimal set of human-readable assumptions is generated as a certificate of the conditions on deadlock where the task is guaranteed. This is truly a synergistic method: the low-level motion planner enables scalability of the high-level plan synthesis with respect to dynamic obstacles, and the high-level mission planner enforces correctness of the low-level motion. We provide formal guarantees for our approach and demonstrate it via physical experiments with ground robots and simulations with a team of quadrotors.

C16. Local motion planning for collaborative manipulation of deformable objects in dynamic environments
J. Alonso-Mora, R. Knepper, R. Siegwart, D. Rus. In Proc. of the IEEE Int. Conf. Robotics and Automation (ICRA), 2015.

web pdf video
Abstract: This paper presents a formalism that exploits deformability during manipulation of soft objects by robot teams. A hybrid centralized/distributed approach restricts centralized planning to high-level global guidance of the object for consensus. Low-level control is thus delegated to the individual manipulator robots, which retain manipulation and collision avoidance guarantees by passing forces to one another through the object. A distributed receding horizon planner provides local control, formulated as a convex optimization problem in velocity space and incorporating constraints for both collision avoidance and shape maintenance. We demonstrate teams of mobile manipulators autonomously carrying various deformable objects.

C15. Gesture based human - robot swarm interaction applied to an interactive display
J. Alonso-Mora, S. Haegeli Lohaus, P. Leemann, R. Siegwart, P. Beardsley. In Proc. of the IEEE Int. Conf. Robotics and Automation (ICRA), 2015.

web pdf video
Abstract: A taxonomy for gesture-based interaction between a human and a group (swarm) of robots is described. Methods are classified into two categories. First, free-form interaction, where the robots are unconstrained in position and motion and the user can use deictic gestures to select subsets of robots and assign target goals and trajectories. Second, shape-constrained interaction, where the robots are in a configuration shape that can be modified by the user. In the later, the user controls a subset of meaningful degrees of freedom defining the overall shape instead of each robot directly. A multi-robot interactive display is described where a depth sensor is used to recognize human gesture, determining the commands sent to a group comprising tens of robots. Experimental results with a preliminary user study show the usability of the system.

W6. Optimal Control and Optimization Methods for Multi-robot Systems
J. Alonso-Mora, K. Savla, D. Rus. In Tutorial on Multi-Robot Systems at Robotics Science and Systems (RSS), 2015.

web pdf

2014

C14. Towards Estimation and Correction of Wind Effects on a Quadrotor UAV
F. Schiano, J. Alonso-Mora, K. Rudin, P. Beardsley, R. Siegwart, B. Siciliano. In Proc. of the Int. Micro Air Vehicle Conference and Competition, 2014.

web pdf video
Abstract: In this paper the problem of estimation and correction of wind effects on a quadrotor UAV, without using wind sensors, is discussed. A large body of research addresses the effects of wind on a quadrotor, however most of them consider it only as a disturbance in their control loop and, for this reason, they solved the problem compensating for the wind with a powerful controller. The main part of this paper is related to the modeling of wind on a quadrotor and to the wind tunnel tests performed at the IFD wind tunnel of ETH Zurich. The approach presented can be used as a starting point for future works. The results obtained in the wind tunnel are really promising for the formulation of a complete aerodynamic model of the quadrotor that has been missing until now.

C13. Customized Sensing for Robot Swarms
D. Jud, J. Alonso-Mora, J. Rehder, R. Siegwart, P. Beardsley. In Proc. of the Int. Symposium on Experimental Robotics, 2014.

pdf web pdf video
Abstract: This paper describes a novel and compact design for an omni-directional stereo camera. A key goal of the work is to investigate the use of rapid prototyping to make the mirrors for the device, by 3D printing the mirror shape and chroming the surface. The target application is in robot swarms, and we discuss how the ability to create a customized omni-camera enables sensing to become an integrated part of system design, avoiding the constraints that arise when using commercial sensors.

C12. Shared Control of Autonomous Vehicles based on Velocity Space Optimization
J. Alonso-Mora, P. Gohl, S. Watson, R. Siegwart, P. Beardsley. In Proc. of the IEEE Int. Conf. on Robotics and Automation (ICRA), 2014.

web pdf
Abstract: This paper presents a method for shared control of a vehicle. The driver commands a preferred velocity which is transformed into a collision-free local motion that respects the actuator constraints and allows for smooth and safe control. Collision-free local motions are achieved with an extension of velocity obstacles that takes into account dynamic constraints and a grid-based map representation. To limit the freedom of the driver, a global guidance trajectory can be included, which specifies the areas where the vehicle is allowed to drive in each time instance. The low computational complexity of the method makes it well suited for multi-agent settings and high update rates and both a centralized and a distributed algorithm are provided that allow for real-time control of tens of vehicles. Extensive experimental results with real robotic wheelchairs at relatively high speeds in tight scenarios are presented.

C11. Viewpoint and Trajectory Optimization for Animation Display with a Large Group of Aerial Vehicles
M. Schoch, J. Alonso-Mora, R. Siegwart, P. Beardsley. In Proc. of the IEEE Int. Conf. on Robotics and Automation (ICRA), 2014.

web pdf video
Abstract: This paper presents a method to optimize the position and trajectory of each aerial vehicle within a large group that displays objects and animations in 3D space. The input is a single object or an animation created by an artist. In a first step, goal positions for the given number of vehicles and representing the object are optimized with respect to a known viewpoint. For displaying an animation, an optimal trajectory satisfying the dynamic constraints of each vehicle is computed using B-splines. Finally, a trajectory following controller is described, which provides the preferred velocity, later optimized to be collision-free with respect to all neighboring vehicles.

C10. Human - Robot Swarm Interaction for entertainment: From animation display to gesture based control
J. Alonso-Mora, R. Siegwart, P. Beardsley. In ACM/IEEE Int. Conf. on Human-Robot Interaction (HRI), 2014. Best video Award 2nd Prize.

web pdf video
Abstract: This work shows experimental results with three systems that take real-time user input to direct a robot swarm formed by tens of small robots. These are: real-time drawing, gesture based interaction with an RGB-D sensor and control via a hand-held tablet computer.

W5. Collaborative Motion Planning for Multi-Agent Systems
J. Alonso-Mora, R. Siegwart, D. Rus. In Workshop The future of multiple-robot research and its multiple identities at the RSJ/IEEE Int. Conf. on Robotics and Intelligent Systems (IROS), 2014.

W4. Multi-robot Control and Interaction with a Hand-held Tablet
R. Grieder, J. Alonso-Mora, C. Bloeglinger, R. Siegwart, P. Beardsley. In Workshop Crossing the Reality Gap: Control, Human Interaction and Cloud Technology for Multi- and Many- Robot Systems at the IEEE Int. Conf. on Robotics and Automation (ICRA), 2014.

web pdf video
Abstract: Real-time interaction with a group of robots is shown with a hand-held tablet, which tracks the robots and computes collision-free trajectories. Efficient algorithms are described and experiments are performed in scenarios with changing illumination. Augmented reality and a multi-player setup are also described.

2013

J4. Reciprocal Collision Avoidance with Motion Continuity Constraints
M. Rufli, J. Alonso-Mora, R. Siegwart. In IEEE Transactions on Robotics, vol. 29, no. 4, pp. 899-912, 2013.

web pdf video
Abstract: This paper addresses decentralized motion planning among a homogeneous set of feedback-controlled, decision-making agents. It introduces the continuous control obstacle ( C n -CO), which describes the set of C n -continuous control sequences (and thus trajectories) that lead to a collision between interacting agents. By selecting a feasible trajectory from C n -CO's complement, a collision-free motion is obtained. The approach represents an extension to the reciprocal velocity obstacle (RVO, ORCA) collision-avoidance methods so that trajectory segments verify C n continuity rather than piecewise linearity. This allows the large class of robots capable of tracking C n -continuous trajectories to employ it for partial motion planning directly-rather than as a mere tool for collision checking. This paper further establishes that both the original velocity obstacle method and several of its recently developed reciprocal extensions (which treat specific robot physiologies only) correspond to particular instances of C n -CO. In addition to the described extension in trajectory continuity, C n -CO thus represents a unification of existing RVO theory. Finally, the presented method is validated in simulation-and a parameter study reveals under which environmental and control conditions C n -CO with admits significantly improved navigation performance compared with inflated approaches based on ORCA.

C9. A message-passing algorithm for multi-agent trajectory planning
J. Bento, N. Derbinsky, J. Alonso-Mora, J. Yedidia. In , In Advances in Neural Information Processing Systems (NIPS), 2013.

web pdf video appendix
Abstract: We describe a novel approach for computing collision-free \emph{global} trajectories for p agents with specified initial and final configurations, based on an improved version of the alternating direction method of multipliers (ADMM). Compared with existing methods, our approach is naturally parallelizable and allows for incorporating different cost functionals with only minor adjustments. We apply our method to classical challenging instances and observe that its computational requirements scale well with p for several cost functionals. We also show that a specialization of our algorithm can be used for {\em local} motion planning by solving the problem of joint optimization in velocity space.

C8. Design and Control of a Spherical Omnidirectional Blimp
M. Burri, L. Gasser, M. K. ch, M. Krebs, S. Laube, A. Ledergerber, D. Meier, R. Michaud, L. Mosimann, L. Muri, C. Ruch, A. Schaffner, N. Vuilliomenet, J. Weichart, K. Rudin, S. Leutenegger, J. Alonso-Mora, R. Siegwart, P. Beardsley. In Proc. of the IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS), 2013.

web pdf video
Abstract: This paper presents Skye, a novel blimp design. Skye is a helium-filled sphere of diameter 2.7m with a strong inelastic outer hull and an impermeable elastic inner hull. Four tetrahedrally-arranged actuation units (AU) are mounted on the hull for locomotion, with each AU having a thruster which can be rotated around a radial axis through the sphere center. This design provides redundant control in the six degrees of freedom of motion, and Skye is able to move omnidirectionally and to rotate around any axis. A multi-camera module is also mounted on the hull for capture of aerial imagery or live video stream according to an ‘eyeball’ concept — the camera module is not itself actuated, but the whole blimp is rotated in order to obtain a desired camera view. Skye is safe for use near people — the double hull minimizes the likelihood of rupture on an unwanted collision; the propellers are covered by grills to prevent accidental contact; and the blimp is near neutral buoyancy so that it makes only a light impact on contact and can be readily nudged away. The system is portable and deployable by a single operator — the electronics, AUs, and camera unit are mounted externally and are detachable from the hull during transport; operator control is via an intuitive touchpad interface. The motivating application is in entertainment robotics. Skye has a varied motion vocabulary such as swooping and bobbing, plus internal LEDs for visual effect. Computer vision enables interaction with an audience. Experimental results show dexterous maneuvers in indoor and outdoor environments, and non-dangerous impacts between the blimp and humans.

C7. Collision Avoidance for Multiple Agents with Joint Utility Maximization
J. Alonso-Mora, M. Rufli, R. Siegwart, P. Beardsley. In Proc. of the IEEE Int. Conf. on Robotics and Automation (ICRA), 2013.

web pdf video
Abstract: In this paper a centralized method for collision avoidance among multiple agents is presented. It builds on the velocity obstacle (VO) concept and its extensions to arbitrary kino-dynamics and is applicable to heterogeneous groups of agents (with respect to size, kino-dynamics and aggressiveness) moving in 2D and 3D spaces. In addition, both static and dynamic obstacles can be considered in the framework. The method maximizes a joint utility function and is formulated as a mixed-integer quadratic program, where online computation can be achieved as a trade-off with solution optimality. In experiments with groups of two to 50 agents the benefits of the joint utility optimization are shown. By construction, it's suboptimal variant is at least as good as comparable decentralized methods, while retaining online capability for small groups of agents. In its optimal variant, the proposed algorithm can provide a benchmark for distributed collision avoidance methods, in particular for those based on the VO concept that take interaction into account.

2012

J3. Image and Animation Display with Multiple Robots
J. Alonso-Mora, A. Breitenmoser, M. Rufli, R. Siegwart, P. Beardsley. In International Journal of Robotics Research, vol. 31, no. 6, pp. 753-773, 2012.

web pdf video
Abstract: In this article we present a novel display that is created using a group of mobile robots. In contrast to traditional displays that are based on a fixed grid of pixels, such as a screen or a projection, this work describes a display in which each pixel is a mobile robot of controllable color. Pixels become mobile entities, and their positioning and motion are used to produce a novel experience. The system input is a single image or an animation created by an artist. The first stage is to generate physical goal configurations and robot colors to optimally represent the input imagery with the available number of robots. The run-time system includes goal assignment, path planning and local reciprocal collision avoidance, to guarantee smooth, fast and oscillation-free motion between images. The algorithms scale to very large robot swarms and extend to a wide range of robot kinematics. Experimental evaluation is done for two different physical swarms of size 14 and 50 differentially driven robots, and for simulations with 1,000 robot pixels.

J2. Limited benefit of Sharing Information in Multi-Agent Iterative Learning Control
A. Schoellig, J. Alonso-Mora, R. D'Andrea. In Asian Journal of Control, vol. 14, no. 3, pp. 613-623, 2012.

web pdf
Abstract: This paper studies iterative learning control (ILC) in a multi-agent framework, wherein a group of agents simultaneously and repeatedly perform the same task. Assuming similarity between the agents, we investigate whether exchanging information between the agents improves an individual's learning performance. That is, does an individual agent benefit from the experience of the other agents? We consider the multi-agent iterative learning problem as a two-step process of: first, estimating the repetitive disturbance of each agent; and second, correcting for it. We present a comparison of an agent's disturbance estimate in the case of (I) independent estimation, where each agent has access only to its own measurement, and (II) joint estimation, where information of all agents is globally accessible. When the agents are identical and noise comes from measurement only, joint estimation yields a noticeable improvement in performance. However, when process noise is encountered or when the agents have an individual disturbance component, the benefit of joint estimation is negligible.

C6. Object and Animation Display with Multiple Aerial Vehicles
J. Alonso-Mora, M. Schoch, A. Breitenmoser, R. Siegwart, P. Beardsley. In Proc. of the IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS), 2012.

web pdf video
Abstract: This paper presents a fully automated method to display objects and animations in 3D with a group of aerial vehicles. The system input is a single object or an animation (sequence of objects) created by an artist. The first stage is to generate physical goal configurations and robot colors to represent the objects with the available number of robots. The run-time system includes algorithms for goal assignment, path planning and local reciprocal collision avoidance that guarantee smooth, fast and oscillation-free motion. The presented algorithms are tested in simulations and verified with real quadrotor helicopters and scale to large robot swarms.

C5. Multi-Robot Formation Control via a Real-Time Drawing Interface
S. Hauri, J. Alonso-Mora, A. Breitenmoser, R. Siegwart, P. Beardsley. In Proc. of the 8th Int. Conf. on Field and Service Robots (FSR), 2012.

web pdf video
Abstract: This paper describes a system that takes real-time user input to direct a robot swarm. The user interface is via drawing, and the user can create a single drawing or an animation to be represented by robots. For example, the drawn input could be a stick figure, with the robots automatically adopting a physical configuration to represent the figure. Or the input could be an animation of a walking stick figure, with the robots moving to represent the dynamic deforming figure. Each robot has a controllable RGB LED so that the swarm can represent color drawings. The computation of robot position, robot motion, and robot color is automatic, including scaling to the available number of robots. The work is in the field of entertainment robotics for play and making robot art, motivated by the fact that a swarm of mobile robots is now affordable as a consumer product. The technical contribution of the paper is three-fold. Firstly the paper presents shaped flocking, a novel algorithm to control multiple robots—this extends existing flocking methods so that robot behavior is driven by both flocking forces and forces arising from a target shape. Secondly the new work is compared with an alternative approach from the existing literature, and the experimental results include a comparative analysis of both algorithms with metrics to compare performance. Thirdly, the paper describes a working real-time system with results for a physical swarm of 60 differential-drive robots.

C4. Reciprocal Collision Avoidance for Multiple Car-like Robots
J. Alonso-Mora, A. Breitenmoser, P. Beardsley, R. Siegwart. In Proc. of the IEEE Int. Conf. on Robotics and Automation (ICRA), 2012.

web pdf video
Abstract: In this paper a method for distributed reciprocal collision avoidance among multiple non-holonomic robots with bike kinematics is presented. The proposed algorithm, bicycle reciprocal collision avoidance (B-ORCA), builds on the concept of optimal reciprocal collision avoidance (ORCA) for holonomic robots but furthermore guarantees collision-free motions under the kinematic constraints of car-like vehicles. The underlying principle of the B-ORCA algorithm applies more generally to other kinematic models, as it combines velocity obstacles with generic tracking control. The theoretical results on collision avoidance are validated by several simulation experiments between multiple car-like robots.

W3. Vision-Based Localization for Multiple Robots with Absolute and Relative Measurements
P. Gohl, J. Alonso-Mora, R. Siegwart, P. Beardsley. In , tech report, 2012.

web pdf video

W2. Human-Robot Shared Control in a Large Robot Swarm
J. Alonso-Mora, A. Breitenmoser, S. Wismer, R. Siegwart, P. Beardsley. In Workshop Many-Robot Systems: Crossing the Reality Gap at the IEEE Int. Conf. on Robotics and Automation (ICRA), 2012.

2011

C3. Multi-Robot System for Artistic Pattern Formation
J. Alonso-Mora, A. Breitenmoser, M. Rufli, R. Siegwart, P. Beardsley. In Proc. of the IEEE Int. Conf. on Robotics and Automation (ICRA), 2011.

web pdf video
Abstract: This paper describes work on multi-robot pattern formation. Arbitrary target patterns are represented with an optimal robot deployment, using a method that is independent of the number of robots. Furthermore, the trajectories are visually appealing in the sense of being smooth, oscillation free, and showing fast convergence. A distributed controller guarantees collision free trajectories while taking into account the kinematics of differentially driven robots. Experimental results are provided for a representative set of patterns, for a swarm of up to ten physical robots, and for fifty virtual robots in simulation.

W1. DisplaySwarm: A robot swarm displaying images
J. Alonso-Mora, A. Breitenmoser, M. Rufli, S. Haag, G. Caprari, R. Siegwart, P. Beardsley. In IEEE/RSJ Int. Conf. on Intelligent Robots and Systems, Symposium: Robot Demonstrations, 2011.

2010

C2. Independent vs. Joint Estimation in Multi-Agent Iterative Learning Control
A. Schoellig, J. Alonso-Mora, R. D'Andrea. In Proc. of the Conf. on Decision and Control (CDC), 2010.

web pdf
Abstract: This paper studies iterative learning control (ILC) in a multi-agent framework, wherein a group of agents simultaneously and repeatedly perform the same task. The agents improve their performance by using the knowledge gained from previous executions. Assuming similarity between the agents, we investigate whether exchanging information between the agents improves an individual's learning performance. That is, does an individual agent benefit from the experience of the other agents? We consider the multi-agent iterative learning problem as a two-step process of: first, estimating the repetitive disturbance of each agent; and second, correcting for it. We present a comparison of an agent's disturbance estimate in the case of (I) independent estimation, where each agent has access only to its own measurement, and (II) joint estimation, where information of all agents is globally accessible. We analytically derive an upper bound of the performance improvement due to joint estimation. Results are obtained for two limiting cases: (i) pure process noise, and (ii) pure measurement noise. The benefits of information sharing are negligible in (i). For (ii), a performance improvement is observed when a high similarity between the agents is guaranteed.

C1. Optimal Reciprocal Collision Avoidance for Multiple Non-Holonomic Robots
J. Alonso-Mora, A. Breitenmoser, M. Rufli, P. Beardsley, R. Siegwart. In Proc. of the Int. Symp. on Distributed Autonomous Robotics Systems (DARS), 2010. Nominated Best Student Paper Award.

web pdf video
Abstract: IIn this paper an optimalmethod for distributed collision avoidance among multiple non-holonomic robots is presented in theory and experiments. Non-holonomic optimal reciprocal collision avoidance (NH-ORCA) builds on the concepts introduced in [2], but further guarantees smooth and collision-free motions under non-holonomic constraints. Optimal control inputs and constraints in velocity space are formally derived for the non-holonomic robots. The theoretical results are validated in several collision avoidance experiments with up to fourteen e-puck robots set on collision course. Even in scenarios with very crowded situations, NH-ORCA showed to be collision-free for all times.

2009

J1. Numerical model for polymer electrolyte membrane fuel cells with experimental application and validation
J. Alonso-Mora, A. Husar, M. Serra, J. Riera. In Asia Pacific Journal of Chemical Engineering, vol. 4, no. 1, pp. 55-67, 2009.

web pdf
Abstract: The aim of this paper is to present a simple 3D computational model of a polymer electrolyte membrane fuel cell (PEMFC) that simulates over time the heat distribution, energy, and mass balance of the reactant gas flows in the fuel cell including pressure drop, humidity, and liquid water. Although this theoretical model can be adapted to any type of PEMFC, for verification of the model and to present different analysis it has been adapted to a single cell test fixture. The model parameters were adjusted through a series of experimental tests and the model was experimentally validated for a well-defined range of operating conditions: H2/air O2 as reactants, flow rates of 0.5–1.5 SLPM, dew points and cell temperatures of 30–80 °C, currents 0–5 A and with/without water condensation. The model is especially suited for the analysis of liquid water condensation in the reactant channels. A key finding is that the critical current at which liquid water is formed is determined at different flows, temperatures, and humidity. Copyright © 2008 Curtin University of Technology and John Wiley & Sons, Ltd.

Patents

P07. Compact omnidirectional vision sensor, US patent, 2014, led.
P06. Shared control of autonomous vehicles, US patent, 2014, led.
P05. Automated charging for aerial vehicles, US patent, 2014, led.
P04. Omnidirectional Spherical Blimp, International patent, 2012, led.
P03. Robotic Textures, US patent, 2012, led.
P02. Display with robotic pixels - divisorial, US patent, 2011, led.
P01. Display with robotic pixels, US patent 8723872.