Nora Ayanian

AAMAS Conference 2025 Conference Paper

Empirical Hardness in Multi-Agent Pathfinding: Research Challenges and Opportunities

• Jingyao Ren
• Eric Ewing
• T. K. Satish Kumar
• Sven Koenig
• Nora Ayanian

Multi-agent pathfinding (MAPF) is the problem of finding collisionfree paths for a team of agents on a map. Although MAPF is NPhard, the hardness of solving individual instances varies significantly, revealing a gap between theoretical complexity and actual hardness. This paper outlines three key research challenges in MAPF empirical hardness to understand such phenomena. The first challenge, known as algorithm selection, is determining the bestperforming algorithms for a given instance. The second challenge is understanding the key instance features that affect MAPF empirical hardness, such as structural properties like phase transition and backbone/backdoor. The third challenge is how to leverage our knowledge of MAPF empirical hardness to effectively generate hard MAPF instances or diverse benchmark datasets. This work establishes a foundation for future empirical hardness research and encourages deeper investigation into these promising and underexplored areas.

IROS Conference 2024 Conference Paper

Hierarchical Large Scale Multirobot Path (Re)Planning

• Lishuo Pan
• Kevin Hsu
• Nora Ayanian

We consider a large-scale multi-robot path planning problem in a cluttered environment. Our approach achieves real-time replanning by dividing the workspace into cells and utilizing a hierarchical planner. Specifically, we propose novel multi-commodity flow-based high-level planners that route robots through cells with reduced congestion, along with an anytime low-level planner that computes collision-free paths for robots within each cell in parallel. A highlight of our method is a significant improvement in computation time. Specifically, we show empirical results of a 500-times speedup in computation time compared to the baseline multi-agent pathfinding approach on the environments we study. We account for the robot’s embodiment and support non-stop execution with continuous replanning. We demonstrate the real-time performance of our algorithm with up to 142 robots in simulation, and a representative 32 physical Crazyflie nanoquadrotor experiment.

ICAPS Conference 2024 Conference Paper

Map Connectivity and Empirical Hardness of Grid-based Multi-Agent Pathfinding Problem

• Jingyao Ren
• Eric Ewing
• T. K. Satish Kumar
• Sven Koenig
• Nora Ayanian

We present an empirical study of the relationship between map connectivity and the empirical hardness of the multi-agent pathfinding (MAPF) problem. By analyzing the second smallest eigenvalue (commonly known as lambda2) of the normalized Laplacian matrix of different maps, our initial study indicates that maps with smaller lambda2 tend to create more challenging instances when agents are generated uniformly randomly. Additionally, we introduce a map generator based on Quality Diversity (QD) that is capable of producing maps with specified lambda2 ranges, offering a possible way for generating challenging MAPF instances. Despite the absence of a strict monotonic correlation with lambda2 and the empirical hardness of MAPF, this study serves as a valuable initial investigation for gaining a deeper understanding of what makes a MAPF instance hard to solve.

AAMAS Conference 2022 Conference Paper

Betweenness Centrality in Multi-Agent Path Finding

• Eric Ewing
• Jingyao Ren
• Dhvani Kansara
• Vikraman Sathiyanarayanan
• Nora Ayanian

Multi-Agent Path Finding (MAPF) is a well studied problem with many existing optimal algorithms capable of solving a wide variety of instances, each with its own strengths and weaknesses. While for some instances the fastest algorithm can be easily determined, not enough is known about their performance to predict the fastest algorithm for every MAPF instance, or what makes some instances more difficult than others. There is no clear answer for which features dominate the hardness of MAPF instances. In this work, we study how betweenness centrality affects the empirical difficulty of MAPF instances. To that end, we benchmark the largest and most complete optimal MAPF algorithm portfolio to date. We analyze the algorithms’ performance independently and as part of the portfolio, and discuss how betweenness centrality can be used to improve estimations of algorithm performance on a given instance of MAPF.

AAAI Conference 2021 Short Paper

Automatic Optimal Multi-Agent Path Finding Algorithm Selector (Student Abstract)

• Jingyao Ren
• Vikraman Sathiyanarayanan
• Eric Ewing
• Baskin Senbaslar
• Nora Ayanian

Solving Multi-Agent Path Finding (MAPF) problems optimally is known to be NP-Hard for both make-span and total arrival time minimization. Many algorithms have been developed to solve MAPF problems optimally and they all have different strengths and weaknesses. There is no dominating MAPF algorithm that works well in all types of problems and no standard guidelines for when to use which algorithm. Therefore, there is a need for developing an automatic algorithm selector that suggests the best optimal algorithm to use given a MAPF problem instance. We propose a model based on convolutions and inception modules by treating the input MAPF instance as an image. We further show that techniques such as single-agent shortest path annotation and graph embedding are very effective for improving training quality. We evaluate our model and show that it outperforms all individual algorithms in its portfolio, as well as an existing state-of-theart MAPF algorithm selector.

ICRA Conference 2021 Conference Paper

Double Meta-Learning for Data Efficient Policy Optimization in Non-Stationary Environments

• Elahe Aghapour
• Nora Ayanian

We are interested in learning models of non-stationary environments, which can be framed as a multitask learning problem. Model-free reinforcement learning algorithms can achieve good asymptotic performance in multitask learning at a cost of extensive sampling, due to their approach, which requires learning from scratch. While model-based approaches are among the most data efficient learning algorithms, they still struggle with complex tasks and model uncertainties. Meta-reinforcement learning addresses the efficiency and generalization challenges on multi task learning by quickly leveraging the meta-prior policy for a new task. In this paper, we propose a meta-reinforcement learning approach to learn the dynamic model of a non-stationary environment to be used for meta-policy optimization later. Due to the sample efficiency of model-based learning methods, we are able to simultaneously train both the meta-model of the non-stationary environment and the meta-policy until dynamic model convergence. Then, the meta-learned dynamic model of the environment will generate simulated data for meta-policy optimization. Our experiment demonstrates that our proposed method can meta-learn the policy in a non-stationary environment with the data efficiency of model-based learning approaches while achieving the high asymptotic performance of model-free meta-reinforcement learning.

AAMAS Conference 2021 Conference Paper

MAPFAST: A Deep Algorithm Selector for Multi Agent Path Finding using Shortest Path Embeddings

• Jingyao Ren
• Vikraman Sathiyanarayanan
• Eric Ewing
• Baskin Senbaslar
• Nora Ayanian

Solving the Multi-Agent Path Finding (MAPF) problem optimally is known to be NP-Hard for both make-span and total arrival time minimization. While many algorithms have been developed to solve MAPF problems, there is no dominating optimal MAPF algorithm that works well in all types of problems and no standard guidelines for when to use which algorithm. In this work, we develop the deep convolutional network MAPFAST (Multi-Agent Path Finding Algorithm SelecTor), which takes a MAPF problem instance and attempts to select the fastest algorithm to use from a portfolio of algorithms. We improve the performance of our model by including single-agent shortest paths in the instance embedding given to our model and by utilizing supplemental loss functions in addition to a classification loss. We evaluate our model on a large and diverse dataset of MAPF instances, showing that it outperforms all individual algorithms in its portfolio as well as the state-of-the-art optimal MAPF algorithm selector. We also provide an analysis of algorithm behavior in our dataset to gain a deeper understanding of optimal MAPF algorithms’ strengths and weaknesses to help other researchers leverage different heuristics in algorithm designs.

IROS Conference 2020 Conference Paper

Inter-Robot Range Measurements in Pose Graph Optimization

• Elizabeth R. Boroson
• Robert Hewitt
• Nora Ayanian
• Jean-Pierre de la Croix

For multiple robots performing exploration in a previously unmapped environment, such as planetary exploration, maintaining accurate localization and building a consistent map are vital. If the robots do not have a map to localize against and do not explore the same area, they may not be able to find visual loop closures to constrain their relative poses, making traditional SLAM impossible. This paper presents a method for using UWB ranging sensors in multi-robot SLAM, which allows the robots to localize and build a map together even without visual loop closures. The ranging measurements are added to the pose graph as edges and used in optimization to estimate the robots' relative poses. This method builds a map using all robots' observations that is consistent and usable. It performs similarly to visual loop closures when they are available, and provides a good map when they are not, which other methods cannot do. The method is demonstrated on PUFFER robots, developed for autonomous planetary exploration, in an unstructured environment.

ICRA Conference 2019 Conference Paper

3D Keypoint Repeatability for Heterogeneous Multi-Robot SLAM

• Elizabeth R. Boroson
• Nora Ayanian

For robots with different types of sensors, loop closure in a multi-robot SLAM scenario requires keypoints that can be matched between sensor measurement point clouds with different properties such as point density and noise. In this paper, we evaluate the performance of several 3D keypoint detectors (Harris3D, ISS, KPQ, KPQ-SI, and NARF) for repeatability between scans from different sensors towards building a heterogeneous multi-robot SLAM system. We find that KPQ-SI and NARF have the best relative repeatability, with KPQ-SI finding more keypoints overall and a higher number of repeatable keypoints, at the cost of significantly worse computational performance. In scans of the same area from different poses, both detectors find enough keypoints for point cloud registration and loop closure. For heterogenous multirobot SLAM applications with computational or bandwidth restrictions, the NARF detector consistently finds repeatable keypoints while also allowing for real-time performance.

SoCS Conference 2019 Conference Paper

Extended Abstract: Lifelong Path Planning with Kinematic Constraintsfor Multi-Agent Pickup and Delivery

• Hang Ma 0001
• Wolfgang Hönig
• T. K. Satish Kumar
• Nora Ayanian
• Sven Koenig

The Multi-Agent Pickup and Delivery (MAPD) problem models applications where a large number of agents attend to a stream of incoming pickup-and-delivery tasks. Token Passing (TP) is a recent MAPD algorithm that is efficient and effective. We make TP even more efficient and effective by using a novel combinatorial search algorithm, called Safe Interval Path Planning with Reservation Table (SIPPwRT), for single-agent path planning. SIPPwRT uses an advanced data structure that allows for fast updates and lookups of the current paths of all agents in an online setting. The resulting MAPD algorithm TP-SIPPwRT takes kinematic constraints of real robots into account directly during planning, computes continuous agent movements with given velocities that work on non-holonomic robots rather than discrete agent movements with uniform velocity, and is complete for well-formed MAPD instances. We demonstrate its benefits for automated warehouses using both an agent simulator and a standard robot simulator. For example, we demonstrate that it can compute paths for hundreds of agents and thousands of tasks in seconds and is more efficient and effective than existing MAPD algorithms that use a post-processing step to adapt their paths to continuous agent movements with given velocities. This paper was published at AAAI 2019.

AAAI Conference 2019 Conference Paper

Lifelong Path Planning with Kinematic Constraints for Multi-Agent Pickup and Delivery

• Hang Ma
• Wolfgang Hönig
• T. K. Satish Kumar
• Nora Ayanian
• Sven Koenig

The Multi-Agent Pickup and Delivery (MAPD) problem models applications where a large number of agents attend to a stream of incoming pickup-and-delivery tasks. Token Passing (TP) is a recent MAPD algorithm that is efficient and effective. We make TP even more efficient and effective by using a novel combinatorial search algorithm, called Safe Interval Path Planning with Reservation Table (SIPPwRT), for single-agent path planning. SIPPwRT uses an advanced data structure that allows for fast updates and lookups of the current paths of all agents in an online setting. The resulting MAPD algorithm TP-SIPPwRT takes kinematic constraints of real robots into account directly during planning, computes continuous agent movements with given velocities that work on non-holonomic robots rather than discrete agent movements with uniform velocity, and is complete for wellformed MAPD instances. We demonstrate its benefits for automated warehouses using both an agent simulator and a standard robot simulator. For example, we demonstrate that it can compute paths for hundreds of agents and thousands of tasks in seconds and is more efficient and effective than existing MAPD algorithms that use a post-processing step to adapt their paths to continuous agent movements with given velocities.

IROS Conference 2019 Conference Paper

Sim-to-(Multi)-Real: Transfer of Low-Level Robust Control Policies to Multiple Quadrotors

• Artem Molchanov
• Tao Chen
• Wolfgang Hönig
• James A. Preiss
• Nora Ayanian
• Gaurav S. Sukhatme

Quadrotor stabilizing controllers often require careful, model-specific tuning for safe operation. We use reinforcement learning to train policies in simulation that transfer remarkably well to multiple different physical quadrotors. Our policies are low-level, i. e. , we map the rotorcrafts’ state directly to the motor outputs. The trained control policies are very robust to external disturbances and can withstand harsh initial conditions such as throws. We show how different training methodologies (change of the cost function, modeling of noise, use of domain randomization) might affect flight performance. To the best of our knowledge, this is the first work that demonstrates that a simple neural network can learn a robust stabilizing low-level quadrotor controller (without the use of a stabilizing PD controller) that is shown to generalize to multiple quadrotors. The video of our experiments can be found at https://sites.google.com/view/sim-to-multi-quad.

AAMAS Conference 2019 Conference Paper

Summary: Distributed Task Assignment and Path Planning with Limited Communication for Robot Teams

• Dario Albani
• Wolfgang Höenig
• Nora Ayanian
• Daniele Nardi
• Vito Trianni

AAMAS Conference 2018 Conference Paper

Conflict-Based Search with Optimal Task Assignment

• Wolfgang H�nig
• Scott Kiesel
• Andrew Tinka
• Joseph W. Durham
• Nora Ayanian

We consider a variant of the Multi-Agent Path-Finding problem that seeks both task assignments and collision-free paths for a set of agents navigating on a graph, while minimizing the sum of costs of all agents. Our approach extends Conflict-Based Search (CBS), a framework that has been previously used to find collision-free paths for a given fixed task assignment. Our approach is based on two key ideas: (i) we operate on a search forest rather than a search tree; and (ii) we create the forest on demand, avoiding a factorial explosion of all possible task assignments. We show that our new algorithm, CBS-TA, is complete and optimal. The CBS framework allows us to extend our method to ECBS-TA, a bounded suboptimal version. We provide extensive empirical results comparing CBS-TA to task assignment followed by CBS, Conflict-Based Min-Cost-Flow (CBM), and an integer linear program (ILP) solution, demonstrating the advantages of our algorithm. Our results highlight a significant advantage in jointly optimizing the task assignment and path planning for very dense cases compared to the traditional method of solving those two problems independently. For large environments with many robots we show that the traditional approach is reasonable, but that we can achieve similar results with the same runtime but stronger suboptimality guarantees.

IROS Conference 2018 Conference Paper

Intelligent Robotic IoT System (IRIS)Testbed

• Jason A. Tran
• Pradipta Ghosh
• Yutong Gu
• Richard Kim
• Daniel D'Souza
• Nora Ayanian
• Bhaskar Krishnamachari

We present the Intelligent Robotic IoT System (IRIS), a modular, portable, scalable, and open-source testbed for robotic wireless network research. There are two key features that separate IRIS from most of the state-of-the-art multi-robot testbeds. (1)Portability: IRIS does not require a costly static global positioning system such as a VICON system nor time-intensive vision-based SLAM for its operation. Designed with an inexpensive Time Difference of Arrival (TDoA)localization system with centimeter level accuracy, the IRIS testbed can be deployed in an arbitrary uncontrolled environment in a matter of minutes. (2)Programmable Wireless Communication Stack: IRIS comes with a modular programmable low-power IEEE 802. 15. 4 radio and IPv6 network stack on each node. For the ease of administrative control and communication, we also developed a lightweight publish-subscribe overlay protocol called ROMANO that is used for bootstrapping the robots (also referred to as the IRISbots), collecting statistics, and direct control of individual robots, if needed. We detail the modular architecture of the IRIS testbed design along with the system implementation details and localization performance statistics.

IROS Conference 2018 Conference Paper

Trajectory Planning for Heterogeneous Robot Teams

• Mark Debord
• Wolfgang Hönig
• Nora Ayanian

We describe a trajectory planning method for heterogeneous mobile robot teams in known environments. We consider two core problems that arise with heterogeneous robot teams: asymmetric inter-robot collision constraints and varying dynamic limits. Asymmetric collision constraints are important for close-proximity flight of rotorcraft due to the downwash effect, which complicates spatial coordination. Varying dynamic limits complicate temporal coordination between robots and must be taken into account during planning. Our method builds upon a hybrid planner that combines graph-planning techniques with trajectory optimization and scales well to large homogeneous robot teams. We extend the hybrid planning approach to include the additional spatial and temporal coordination to support heterogeneous teams. Our method scales well with the number of robots and robot types and we demonstrate our approach on a team of 15 physical robots of 4 different types, including quadrotors and differential drive robots.

ICRA Conference 2017 Conference Paper

Crazyswarm: A large nano-quadcopter swarm

• James A. Preiss
• Wolfgang Hönig
• Gaurav S. Sukhatme
• Nora Ayanian

We define a system architecture for a large swarm of miniature quadcopters flying in dense formation indoors. The large number of small vehicles motivates novel design choices for state estimation and communication. For state estimation, we develop a method to reliably track many small rigid bodies with identical motion-capture marker arrangements. Our communication infrastructure uses compressed one-way data flow and supports a large number of vehicles per radio. We achieve reliable flight with accurate tracking (<; 2 cm mean position error) by implementing the majority of computation onboard, including sensor fusion, control, and some trajectory planning. We provide various examples and empirically determine latency and tracking performance for swarms with up to 49 vehicles.

IROS Conference 2017 Conference Paper

Downwash-aware trajectory planning for large quadrotor teams

• James A. Preiss
• Wolfgang Hönig
• Nora Ayanian
• Gaurav S. Sukhatme

We describe a method for formation-change trajectory planning for large quadrotor teams in obstacle-rich environments. Our method decomposes the planning problem into two stages: a discrete planner operating on a graph representation of the workspace, and a continuous refinement that converts the non-smooth graph plan into a set of C k -continuous trajectories, locally optimizing an integral-squared-derivative cost. We account for the downwash effect, allowing safe flight in dense formations. We demonstrate the computational efficiency in simulation with up to 200 robots and the physical plausibility with an experiment with 32 nano-quadrotors. Our approach can compute safe and smooth trajectories for hundreds of quadrotors in dense environments with obstacles in a few minutes.

IS Journal 2017 Journal Article

Overview: A Hierarchical Framework for Plan Generation and Execution in Multirobot Systems

• Hang Ma
• Wolfgang Hönig
• Liron Cohen
• Tansel Uras
• Hong Xu
• T.K. Satish Kumar
• Nora Ayanian
• Sven Koenig

The authors present an overview of a hierarchical framework for coordinating task- and motion-level operations in multirobot systems. Their framework is based on the idea of using simple temporal networks to simultaneously reason about precedence/causal constraints required for task-level coordination and simple temporal constraints required to take some kinematic constraints of robots into account. In the plan-generation phase, the framework provides a computationally scalable method for generating plans that achieve high-level tasks for groups of robots and take some of their kinematic constraints into account. In the plan-execution phase, the framework provides a method for absorbing an imperfect plan execution to avoid time-consuming re-planning in many cases. The authors use the multirobot path-planning problem as a case study to present the key ideas behind their framework for the long-term autonomy of multirobot systems.

IJCAI Conference 2017 Conference Paper

Summary: Multi-Agent Path Finding with Kinematic Constraints

• Wolfgang Hönig
• T. K. Satish Kumar
• Liron Cohen
• Hang Ma
• Hong Xu
• Nora Ayanian
• Sven Koenig

Multi-Agent Path Finding (MAPF) is well studied in both AI and robotics. Given a discretized environment and agents with assigned start and goal locations, MAPF solvers from AI find collision-free paths for hundreds of agents with user-provided sub-optimality guarantees. However, they ignore that actual robots are subject to kinematic constraints (such as velocity limits) and suffer from imperfect plan-execution capabilities. We therefore introduce MAPF-POST to postprocess the output of a MAPF solver in polynomial time to create a plan-execution schedule that can be executed on robots. This schedule works on non-holonomic robots, considers kinematic constraints, provides a guaranteed safety distance between robots, and exploits slack to avoid time-intensive replanning in many cases. We evaluate MAPF-POST in simulation and on differential-drive robots, showcasing the practicality of our approach.

IROS Conference 2016 Conference Paper

Dynamic multi-target coverage with robotic cameras

• Wolfgang Hönig
• Nora Ayanian

When tracking multiple targets with autonomous cameras for 3D scene reconstruction, e. g. , in sports, a significant challenge is handling the unpredictable nature of the targets' motion. Such a monitoring system must reposition according to the targets' movements and maintain satisfactory coverage of the targets. We propose an approximate, centralized approach for maximizing the visible boundary of dynamic targets using mobile cameras in a bounded 2D environment. Targets and obstacles translate, rotate, and deform independently, and cameras are only aware of the current position and shape of the targets and obstacles. Using current information, the environment is searched for better viewing positions, then cameras navigate to those positions while avoiding collisions with targets and obstacles. We present a benchmark and metrics to evaluate the performance of our method, and compare our approach to a simple gradient-based local method in several real-time simulations.

IROS Conference 2016 Conference Paper

Formation change for robot groups in occluded environments

• Wolfgang Hönig
• T. K. Satish Kumar
• Hang Ma 0001
• Sven Koenig
• Nora Ayanian

We study formation change for robot groups in known environments. We are given a team of robots partitioned into groups, where robots in the same group are interchangeable with each other. A formation specifies the locations occupied by each group. The objective is to find collision-free paths that move all robots from a given start formation to a given goal formation. Our algorithm TAPF* has the following features: (a) it incorporates kinematic constraints of robots in form of velocity limits; (b) it maintains a user-specified safety distance between robots; (c) it attempts to minimize the makespan; and (d) it runs efficiently for hundreds of robots and dozens of groups even in dense 3D environments with narrow corridors and other occlusions. We demonstrate the efficiency and effectiveness of TAPF* in simulation and on robots.

IJCAI Conference 2016 Conference Paper

Improved Solvers for Bounded-Suboptimal Multi-Agent Path Finding

• Liron Cohen
• Tansel Uras
• T. K. Satish Kumar
• Hong Xu
• Nora Ayanian
• Sven Koenig

Multi-Agent Path Finding (MAPF) with the objective to minimize the sum of the travel times of the agents along their paths is a hard combinatorial problem. Recent work has shown that bounded-suboptimal MAPF solvers, such as Enhanced Conflict-Based Search or ECBS(w1) for short, run often faster than optimal MAPF solvers at the cost of incurring a suboptimality factor w1, that is due to using focal search. Other recent work has used experience graphs to guide the search of ECBS(w1) and speed it up, at the cost of incurring a separate suboptimality factor w2, that is due to inflating the heuristic values. Thus, the combination has suboptimality factor w1w2. In this first feasibility study, we develop a bounded-suboptimal MAPF solver, Improved-ECBS or iECBS(w1) for short, that has sub optimality factor w1 rather than w1w2 (because it uses experience graphs to guide its search without inflating the heuristic values) and can run faster than ECBS(w1). We also develop two first approaches for automatically generating experience graphs for a given MAPF instance. Finally, we observe heavy-tailed behavior in the runtimes of these MAPF solvers and develop a simple rapid randomized restart strategy that can increase the success rate of iECBS(w1) within a given runtime limit.

AAMAS Conference 2016 Conference Paper

Local Search on Trees and a Framework for Automated Construction Using Multiple Identical Robots (Extended Abstract)

• Trevor Cai
• David Y. Zhang
• T. K. Satish Kumar
• Sven Koenig
• Nora Ayanian

We present an algorithmic framework for automated construction using multiple identical robots. Our approach is based on the principle of tree-based dynamic programming and a concomitant idea of local search on trees to improve the quality of the generated plans. Inspired by the TER- MES project of Harvard University, robots in this domain are required to gather construction blocks from a reservoir and coordinate with each other in building user-specified structures much larger than themselves. While the robots are roughly of the same size as the blocks, they can scale greater heights by using temporarily constructed ramps in the substructures. Our algorithm employs an inner loop in which the planning problem is solved by performing dynamic programming on a tree that spans the footprint of the user-specified structure. The outer loop of the algorithm furnishes a good tree for the inner loop. We show how we can search for a good tree in the outer loop using local search methods that yield significant improvements in plan quality. Synchronization rules are then applied to parallelize the execution of the generated plan for multiple identical robots. General Terms Algorithms, Performance, Experimentation

ICAPS Conference 2016 Conference Paper

Multi-Agent Path Finding with Kinematic Constraints

• Wolfgang Hönig
• T. K. Satish Kumar
• Liron Cohen 0002
• Hang Ma 0001
• Hong Xu 0003
• Nora Ayanian
• Sven Koenig

Multi-Agent Path Finding (MAPF) is well studied in both AI and robotics. Given a discretized environment and agents with assigned start and goal locations, MAPF solvers from AI find collision-free paths for hundreds of agents with user-provided sub-optimality guarantees. However, they ignore that actual robots are subject to kinematic constraints (such as finite maximum velocity limits) and suffer from imperfect plan-execution capabilities. We therefore introduce MAPF-POST, a novel approach that makes use of a simple temporal network to postprocess the output of a MAPF solver in polynomial time to create a plan-execution schedule that can be executed on robots. This schedule works on non-holonomic robots, takes their maximum translational and rotational velocities into account, provides a guaranteed safety distance between them, and exploits slack to absorb imperfect plan executions and avoid time-intensive replanning in many cases. We evaluate MAPF-POST in simulation and on differential-drive robots, showcasing the practicality of our approach.

IROS Conference 2015 Conference Paper

Mixed reality for robotics

• Wolfgang Hönig
• Christina Milanes
• Lisa Scaria
• Thai Phan
• Mark T. Bolas
• Nora Ayanian

Mixed Reality can be a valuable tool for research and development in robotics. In this work, we refine the definition of Mixed Reality to accommodate seamless interaction between physical and virtual objects in any number of physical or virtual environments. In particular, we show that Mixed Reality can reduce the gap between simulation and implementation by enabling the prototyping of algorithms on a combination of physical and virtual objects, including robots, sensors, and humans. Robots can be enhanced with additional virtual capabilities, or can interact with humans without sharing physical space. We demonstrate Mixed Reality with three representative experiments, each of which highlights the advantages of our approach. We also provide a testbed for Mixed Reality with three different virtual robotics environments in combination with the Crazyflie 2. 0 quadcopter.

IROS Conference 2015 Conference Paper

The optimism principle: A unified framework for optimal robotic network deployment in an unknown obstructed environment

• Shangxing Wang
• Bhaskar Krishnamachari
• Nora Ayanian

We consider the problem of deploying a team of robots in an unknown, obstructed environment to form a multi-hop communication network. As a solution, we present a unified framework, onLinE rObotic Network formAtion (LEONA), that is general enough to permit optimizing the communication network for different utility functions in non-convex environments. LEONA adopts the principle of “optimism in the face of uncertainty” to allow the team of robots to form optimal network configurations efficiently and rapidly without having to map link qualities in the entire area. We demonstrate and evaluate this framework on two specific scenarios concerning the formation of a multi-hop communication path between fixed end-points: one minimizing the total path cost, and another maximizing the bottleneck communication rate. Our simulation-based evaluation shows that the use of the optimism principle can significantly reduce resources spent in exploring and mapping the entire region prior to network optimization. We also present a mathematical modeling of how the searched area scales with various relevant parameters in each case.

ICRA Conference 2014 Conference Paper

Controlling a team of robots with a single input

• Nora Ayanian
• Andrew Spielberg
• Matthew Arbesfeld
• Jason Strauss
• Daniela Rus

We present a novel end-to-end solution for distributed multirobot coordination that translates multitouch gestures into low-level control inputs for teams of robots. Highlighting the need for a holistic solution to the problem of scalable human control of multirobot teams, we present a novel control algorithm with provable guarantees on the robots' motion that lends itself well to input from modern tablet and smartphone interfaces. Concretely, we develop an iOS application in which the user is presented with a team of robots and a bounding box (prism). The user carefully translates and scales the prism in a virtual environment; these prism coordinates are wirelessly transferred to our server and then received as input to distributed onboard robot controllers. We develop a novel distributed multirobot control policy which provides guarantees on convergence to a goal with distance bounded linearly in the number of robots, and avoids interrobot collisions. This approach allows the human user to solve the cognitive tasks such as path planning, while leaving precise motion to the robots. Our system was tested in simulation and experiments, demonstrating its utility and effectiveness.

ICRA Conference 2013 Conference Paper

Improving the performance of multi-robot systems by task switching

• Cynthia R. Sung
• Nora Ayanian
• Daniela Rus

We consider the problem of task assignment for a multi-robot system where each robot must attend to one or more queues of tasks. We assume that individual robots have no knowledge of tasks in the environment that are not in their queue. Robots in communication with each other may share information about active tasks and exchange queues to achieve lower cost for the system. We show that allowing this kind of task switching causes tasks to be completed more efficiently. In addition, we present conditions under which queues can be guaranteed to make progress, and we support these claims with simulation and experimental results. This work has potential applications in manufacturing, environmental exploration, and pickup-delivery tasks.

SoCS Conference 2012 Conference Paper

Subdimensional Expansion and Optimal Task Reassignment

• Glenn Wagner
• Howie Choset
• Nora Ayanian

Multirobot path planning and task assignment are traditionally treated separately, however task assignment can greatly impact the difficulty of the path planning problem, and the ultimate quality of solution is dependent upon both. We introduce task reassignment, an approach to optimally solving the coupled task assignment and path planning problems. We show that task reassignment improves solution quality, and reduces planning time in some situations.

IROS Conference 2011 Conference Paper

Synthesis of feedback controllers for multiple aerial robots with geometric constraints

• Nora Ayanian
• Vinutha Kallem
• Vijay Kumar 0001

We address the problem of developing feedback controllers for a group of robots with second-order dynamics in an obstacle-filled, D-dimensional environment. Our control algorithm takes into account communication constraints, obstacle avoidance, and inter-robot collision avoidance, by synthesizing a piecewise smooth vector field for safe navigation. First, the feasible free joint configuration space is tessellated into polytopes that account for the desired constraints. We search the graph of these polytopes to find a discrete path to the goal polytope. We then use a novel navigation function-based feedback controller that drives the system from one polytope to the next and eventually to the goal. The controller exploits the fact that two adjoining polytopes in the planned discrete path together form a star-shaped object that is obstacle free; this enables the design of navigation function-based controller for kinematic and dynamic fully actuated robots without spurious minima. We sequentially compose these controllers to drive the state to the goal. For a polygonal space, the algorithm we propose is complete. We present successful simulation results of the algorithm on a group of ground vehicles and quadrotors performing a cooperative navigation task in constrained environments.

ICRA Conference 2010 Conference Paper

Abstractions and controllers for groups of robots in environments with obstacles

• Nora Ayanian
• Vijay Kumar 0001

We address the problem of controlling a formation of robots in a cluttered environment. Instead of explicitly controlling the relative positions between the robots and the environment, we construct a lower-dimensional abstraction of the group that establishes a boundary for the group. We then synthesize feedback controllers that allow the abstracted group to navigate a two-dimensional environment to a desired goal position, while automatically adapting the shape of the boundary as well as the position and orientation of the group to avoid collisions between the virtual boundary and the environment. In contrast to previous approaches, we address the planning and control problems concurrently and are naturally able to establish bounds on the positions of the robots through the abstraction. The complexity of the method is independent of the number of robots which promises scalability to large teams.

ICRA Conference 2008 Conference Paper

Decentralized feedback controllers for multi-agent teams in environments with obstacles

• Nora Ayanian
• Vijay Kumar 0001

We propose a method for synthesizing decentralized feedback controllers for a team of multiple heterogeneous agents navigating a known environment with obstacles. The controllers are designed to drive agents with limited team state information to goal sets while avoiding collisions and maintaining specified proximity constraints. The method, its successful application to nonholonomic agents in dynamic simulation, and its limitations are presented in this paper.