Arrow Research search

Author name cluster

Wolfgang Hönig

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

22 papers
2 author rows

Possible papers

22

AAMAS Conference 2026 Conference Paper

ANN-CMCGS: Generalizing Continuous Monte-Carlo Graph Search with Approximate Nearest Neighbors

  • Christoph Scherer
  • Wolfgang Hönig

Continuous Monte Carlo Graph Search (CMCGS) enables state reuse in continuous domains but still relies on a layered, acyclic structure, limiting its effectiveness. We introduce ANN-CMCGS, a generalized, non-layered formulation to detect approximate transpositions in continuous spaces via approximate nearest-neighbor search. By allowing arbitrary directed graphs and enabling incremental reuse across decision steps, ANN-CMCGS demonstrates improved exploration efficiency and success rates in challenging continuous domains.

PDF

AAAI Conference 2026 Conference Paper

db-ECBS: Interaction-Aware Multirobot Kinodynamic Motion Planning (Abstract Reprint)

  • Akmaral Moldagalieva
  • Joaquim Ortiz-Haro
  • Wolfgang Hönig

Kinodynamic motion planning for a multirobot system with different dynamics and actuation limits is a challenging problem. The difficulty increases with the presence of aerodynamic interaction forces that occur when aerial robots fly in close proximity. Due to these complexities, existing planners either rely on simplified assumptions (like ignoring robot dynamics and interaction forces) or produce highly suboptimal solutions. This article presents a kinodynamic motion planner for a heterogeneous team of robots that respects robot dynamics, scales well to 16 robots, and directly reasons about interaction forces between aerial robots operating in close proximity. Our method, db-ECBS, generalizes the multiagent path-finding method Enhanced Conflict-Based Search (ECBS) to the continuous domain by using the single-robot kinodynamic motion planner discontinuity-bounded A. The planner db-ECBS operates on three levels. Initially, individual robot trajectories are computed using a graph search that allows bounded discontinuities between precomputed motion primitives. The second level identifies interrobot collisions or interaction force violations and resolves them by imposing constraints on the first level. The third and final level uses the resulting solution with discontinuities as an initial guess for a joint-space trajectory optimization. The procedure is repeated with a reduced discontinuity bound, resulting in an anytime, probabilistically complete, and asymptotically bounded suboptimal planner. We provide a benchmark of 65 problems with six different dynamics. We demonstrate that db-ECBS produces trajectories that are less than half the cost of existing planners. We show that the interaction-awareness is particularly important for very dense scenarios.

PDF Details DOI

ICRA Conference 2024 Conference Paper

db-CBS: Discontinuity-Bounded Conflict-Based Search for Multi-Robot Kinodynamic Motion Planning

  • Akmaral Moldagalieva
  • Joaquim Ortiz de Haro
  • Marc Toussaint
  • Wolfgang Hönig

This paper presents a multi-robot kinodynamic motion planner that enables a team of robots with different dynamics, actuation limits, and shapes to reach their goals in challenging environments. We solve this problem by combining Conflict-Based Search (CBS), a multi-agent path finding method, and discontinuity-bounded A*, a single-robot kinodynamic motion planner. Our method, db-CBS, operates in three levels. Initially, we compute trajectories for individual robots using a graph search that allows bounded discontinuities between precomputed motion primitives. The second level identifies inter-robot collisions and resolves them by imposing constraints on the first level. The third and final level uses the resulting solution with discontinuities as an initial guess for a joint space trajectory optimization. The procedure is repeated with a reduced discontinuity bound. Our approach is anytime, probabilistically complete, asymptotically optimal, and finds near-optimal solutions quickly. Experimental results with robot dynamics such as unicycle, double integrator, and car with trailer in different settings show that our method is capable of solving challenging tasks with a higher success rate and lower cost than the existing state-of-the-art.

Details

ICRA Conference 2024 Conference Paper

Effort Level Search in Infinite Completion Trees with Application to Task-and-Motion Planning

  • Marc Toussaint
  • Joaquim Ortiz de Haro
  • Valentin N. Hartmann
  • Erez Karpas
  • Wolfgang Hönig

Solving a Task-and-Motion Planning (TAMP) problem can be represented as a sequential (meta-) decision process, where early decisions concern the skeleton (sequence of logic actions) and later decisions concern what to compute for such skeletons (e. g. , action parameters, bounds, RRT paths, or full optimal manipulation trajectories). We consider the general problem of how to schedule compute effort in such hierarchical solution processes. More specifically, we introduce infinite completion trees as a problem formalization, where before we can expand or evaluate a node, we have to solve a preemptible computational sub-problem of a priori unknown compute effort. Infinite branchings represent an infinite choice of random initializations of computational sub-problems. Decision making in such trees means to decide on where to invest compute or where to widen a branch. We propose a heuristic to balance branching width and compute depth using polynomial level sets. We show completeness of the resulting solver and that a round robin baseline strategy used previously for TAMP becomes a special case. Experiments confirm the robustness and efficiency of the method on problems including stochastic bandits and a suite of TAMP problems, and compare our approach to a round robin baseline. An appendix comparing the framework to bandit methods and proposing a corresponding tree policy version is found on the supplementary webpage 1.

Details

IROS Conference 2024 Conference Paper

GSRM: Building Roadmaps for Query-Efficient and Near-Optimal Path Planning Using a Reaction Diffusion System

  • Christian Henkel
  • Marc Toussaint
  • Wolfgang Hönig

Mobile robots frequently navigate on roadmaps, i. e. , graphs where edges represent safe motions, in applications such as healthcare, hospitality, and warehouse automation. Often the environment is quasi-static, i. e. , it is sufficient to construct a roadmap once and then use it for any future planning queries. Roadmaps are typically used with graph search algorithm to find feasible paths for the robots. Therefore, the roadmap should be well-connected, and graph searches should produce near-optimal solutions with short solution paths while simultaneously be computationally efficient to execute queries quickly. We propose a new method to construct roadmaps based on the Gray-Scott reaction diffusion system and Delaunay triangulation. Our approach, GSRM, produces roadmaps with evenly distributed vertices and edges that are well-connected even in environments with challenging narrow passages. Empirically, we compare to classical roadmaps generated by 8-connected grids, probabilistic roadmaps (PRM, SPARS2), and optimized roadmap graphs (ORM). Our results show that GSRM consistently produces superior roadmaps that are well-connected, have high query efficiency, and result in short solution paths.

Details

IROS Conference 2024 Conference Paper

iDb-RRT: Sampling-based Kinodynamic Motion Planning with Motion Primitives and Trajectory Optimization

  • Joaquim Ortiz de Haro
  • Wolfgang Hönig
  • Valentin N. Hartmann
  • Marc Toussaint
  • Ludovic Righetti

Rapidly-exploring Random Trees (RRT) and its variations have emerged as a robust and efficient tool for finding collision-free paths in robotic systems. However, adding dynamic constraints makes the motion planning problem significantly harder, as it requires solving two-value boundary problems (computationally expensive) or propagating random control inputs (uninformative). Alternatively, Iterative Discontinuity Bounded A* (iDb-A*), introduced in our previous study, combines search and optimization iteratively. The search step connects short trajectories (motion primitives) while allowing a bounded discontinuity between the motion primitives, which is later repaired in the trajectory optimization step. Building upon these foundations, in this paper, we present iDb-RRT, a sampling-based kinodynamic motion planning algorithm that combines motion primitives and trajectory optimization within the RRT framework. iDb-RRT is probabilistically complete and can be implemented in forward or bidirectional mode. We have tested our algorithm across a benchmark suite comprising 30 problems, spanning 8 different systems, and shown that iDb-RRT can find solutions up to 10x faster than previous methods, especially in complex scenarios that require long trajectories or involve navigating through narrow passages.

Details

IROS Conference 2024 Conference Paper

Kinodynamic Motion Planning for a Team of Multirotors Transporting a Cable-Suspended Payload in Cluttered Environments

  • Khaled Wahba
  • Joaquim Ortiz de Haro
  • Marc Toussaint
  • Wolfgang Hönig

We propose a motion planner for cable-driven payload transportation using multiple unmanned aerial vehicles (UAVs) in an environment cluttered with obstacles. Our planner is kinodynamic, i. e. , it considers the full dynamics model of the transporting system including actuation constraints. Due to the high dimensionality of the planning problem, we use a hierarchical approach where we first solve for the geometric motion using a sampling-based method with a novel sampler, followed by constrained trajectory optimization that considers the full dynamics of the system. Both planning stages consider inter-robot and robot/obstacle collisions. We demonstrate in a software-in-the-loop simulation and real flight experiments that there is a significant benefit in kinodynamic motion planning for such payload transport systems with respect to payload tracking error and energy consumption compared to the standard methods of planning for the payload alone. Notably, we observe a significantly higher success rate in scenarios where the team formation changes are needed to move through tight spaces.

Details

IROS Conference 2022 Conference Paper

db-A*: Discontinuity-bounded Search for Kinodynamic Mobile Robot Motion Planning

  • Wolfgang Hönig
  • Joaquim Ortiz de Haro
  • Marc Toussaint

We consider time-optimal motion planning for dynamical systems that are translation-invariant, a property that holds for many mobile robots, such as differential-drives, cars, airplanes, and multirotors. Our key insight is that we can extend graph-search algorithms to the continuous case when used symbiotically with optimization. For the graph search, we introduce discontinuity-bounded A* (db-A*), a generalization of the A* algorithm that uses concepts and data structures from sampling-based planners. Db-A* reuses short trajectories, so-called motion primitives, as edges and allows a maximum user-specified discontinuity at the vertices. These trajectories are locally repaired with trajectory optimization, which also provides new improved motion primitives. Our novel kinodynamic motion planner, kMP-db-A*, has almost surely asymptotic optimal behavior and computes near-optimal solutions quickly. For our empirical validation, we provide the first benchmark that compares search-, sampling-, and optimization- based time-optimal motion planning on multiple dynamical systems in different settings. Compared to the baselines, kMP- db-A* consistently solves more problem instances, finds lower- cost initial solutions, and converges more quickly.

Details

IROS Conference 2022 Conference Paper

Sequence-of-Constraints MPC: Reactive Timing-Optimal Control of Sequential Manipulation

  • Marc Toussaint
  • Jason Harris
  • Jung-Su Ha
  • Danny Driess
  • Wolfgang Hönig

Task and Motion Planning has made great progress in solving hard sequential manipulation problems. However, a gap between such planning formulations and control methods for reactive execution remains. In this paper we pro-pose a model predictive control approach dedicated to robustly execute a single sequence of constraints, which corresponds to a discrete decision sequence of a TAMP plan. We decompose the overall control problem into three sub-problems (solving for sequential waypoints, their timing, and a short receding horizon path) that each is a non-linear program solved online in each MPC cycle. The resulting control strategy can account for long-term interdependencies of constraints and reactively plan for a timing-optimal transition through all constraints. We additionally propose phase backtracking when running constraints of the current phase cannot be fulfilled, leading to a fluent re-initiation behavior that is robust to perturbations and interferences by an experimenter.

Details

ICRA Conference 2020 Conference Paper

Neural-Swarm: Decentralized Close-Proximity Multirotor Control Using Learned Interactions

  • Guanya Shi
  • Wolfgang Hönig
  • Yisong Yue
  • Soon-Jo Chung

In this paper, we present Neural-Swarm, a nonlinear decentralized stable controller for close-proximity flight of multirotor swarms. Close-proximity control is challenging due to the complex aerodynamic interaction effects between multirotors, such as downwash from higher vehicles to lower ones. Conventional methods often fail to properly capture these interaction effects, resulting in controllers that must maintain large safety distances between vehicles, and thus are not capable of close-proximity flight. Our approach combines a nominal dynamics model with a regularized permutation-invariant Deep Neural Network (DNN) that accurately learns the high-order multi-vehicle interactions. We design a stable nonlinear tracking controller using the learned model. Experimental results demonstrate that the proposed controller significantly outperforms a baseline nonlinear tracking controller with up to four times smaller worst-case height tracking errors. We also empirically demonstrate the ability of our learned model to generalize to larger swarm sizes.

Details

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.

Details

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.

PDF Details

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.

Details

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.

Details

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.

Details

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.

Details

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.

Details DOI

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.

PDF Details

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.

Details

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.

Details

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.

Details

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.

Details
v2026.09.13