Dan Halperin

ICRA Conference 2025 Conference Paper

A Full-Cycle Assembly Operation: From Digital Planning to Trajectory Execution Using a Robotic Arm

• Dror Livnat
• Yuval Lavi
• Dan Halperin

We present an end-to-end framework for planning tight assembly operations, where the input is a set of digital models, and the output is a full execution plan for a physical robotic arm, including the trajectory placement and the grasping. The framework builds on our earlier results on tight assembly plan-ning for free-flying objects and includes the following novel components: (i) the framework itself together with physical demon-strations, (ii) trajectory placement based on novel dynamic path-wise IK and (iii) post processing of the free-flying paths to relax the tightness and smooth the path. The framework provides guarantees as to the quality of the outcome trajectory. For each component we provide the algorithmic details and a full open-source software package for reproducing the process. Lastly, we demonstrate the framework with tight and challenging assembly problems (as well as puzzles, which are planned to be hard to assemble), using a UR5e robotic arm in the real world and in simulation. See the figure at the top for a physical UR5e assembling the alpha-z puzzle (known to be considerably more complicated to assemble than the celebrated alpha puzzle). Full video clips of all the assembly demonstrations together with our open source software are available at our project page: https://tau-cgl.github.io/Full-Cycle-Assembly-Operation/

ICRA Conference 2025 Conference Paper

Indoor Localization of UAVs Using Only Few Measurements by Output-Sensitive Preimage Intersection

• Michael M. Bilevich
• Tomer Buber
• Dan Halperin

We present a deterministic approach for the localization of an Unmanned Aerial Vehicle (UAV) in a known indoor environment by using only a few downward distance measurements and the corresponding odometries between measurements. For each distance measurement and odometry, we look at the preimage of that distance measurement under the downwards distance function combined with the corresponding odometry where the motion between every two measurements has four degrees of freedom: three of translation and one of azimuth change. The intersection of these preimages yields the set of all possible locations for the UAV. In this work, we present an efficient method for approximating that intersection of preimages. We perform a spatial subdivision search, which splits only voxels containing that intersection. We present a novel technique, based on geometric insights, for correctly evaluating whether a voxel indeed contains a true localization. This technique is also robust under different kinds of errors that might occur. Our method is guaranteed to contain the ground truth location, and its runtime complexity is output sensitive, in the Hausdorff dimension and measure of the resulting intersection of preimages. We demonstrate the effectiveness of this method in various indoor scenarios, showing that it can be used to significantly decrease the uncertainty of localization when solving the kidnapped robot problem in simulation and on a physical drone. Our method can be performed in real-time. Furthermore, our method requires only a map of the environment, odometry and ToF sensors, which is advantageous in terms of cost, privacy and transmission bandwidth. Our open-source software and supplementary materials are available at https://github.com/TAU-CGL/uav-fdml-public.

SODA Conference 2024 Conference Paper

Near-Optimal Min-Sum Motion Planning for Two Square Robots in a Polygonal Environment

• Pankaj K. Agarwal
• Dan Halperin
• Micha Sharir
• Alex Steiger

ICRA Conference 2024 Conference Paper

Tight Motion Planning by Riemannian Optimization for Sliding and Rolling with Finite Number of Contact Points

• Dror Livnat
• Michael M. Bilevich
• Dan Halperin

We address a challenging problem in motion planning where robots must navigate through narrow passages in their configuration space. Our novel approach leverages optimization techniques to facilitate sliding and rolling movements across critical regions, which represent semi-free configurations, where the robot and the obstacles are in contact. Our algorithm seamlessly traverses widely free regions, follows semi-free paths in narrow passages, and smoothly transitions between the two types. We specifically focus on scenarios resembling 3D puzzles, intentionally designed to be complex for humans by requiring intricate simultaneous translations and rotations. Remarkably, these complexities also present computational challenges. Our contributions are threefold: First, we solve previously unsolved problems; second, we outperform state-of-the-art algorithms on certain problem types; and third, we present a rigorous analysis supporting the consistency of the algorithm. In the Supplementary Material we provide theoretical foundations for our approach. The Supplementary Material and our open source software are available at https://github.com/TAU-CGL/tr-rrt-public.This research sheds light on effective approaches to address motion planning difficulties in intricate 3D puzzle-like scenarios.

AAMAS Conference 2023 Conference Paper

Coordination of Multiple Robots along Given Paths with Bounded Junction Complexity

• Mikkel Abrahamsen
• Tzvika Geft
• Dan Halperin
• Barak Ugav

We study a fundamental NP-hard motion coordination problem for multi-robot/multi-agent systems: We are given a graph 𝐺 and set of agents, where each agent has a given directed path in 𝐺. Each agent is initially located on the first vertex of its path. At each time step an agent can move to the next vertex on its path, provided that the vertex is not occupied by another agent. The goal is to find a sequence of such moves along the given paths so that each agent reaches its target or to report that no such sequence exists. The problem models guidepath-based transport systems, which is a pertinent abstraction for traffic in a variety of contemporary applications, ranging from train networks or Automated Guided Vehicles (AGVs) in factories, through computer game animations, to qubit transport in quantum computing. It also arises as a subproblem in the more general multi-robot motion-planning problem. We provide a fine-grained tractability analysis of the problem by considering new assumptions and identifying minimal values of key parameters for which the problem remains NP-hard. Our analysis identifies a critical parameter called vertex multiplicity (VM), defined as the maximum number of paths passing through the same vertex. We show that a prevalent variant of the problem, which is equivalent to Sequential Resource Allocation (concerning deadlock prevention for concurrent processes), is NP-hard even when VM is 3. On the positive side, for VM ≤ 2 we give an efficient algorithm that iteratively resolves cycles of blocking relations among agents. We also present a variant that is NP-hard when the VM is 2 even when 𝐺 is a 2D grid and each path lies in a single grid row or column. By studying highly distilled yet NP-hard variants, we deepen the understanding of what makes the problem intractable and thereby guide the search for efficient solutions.

ICRA Conference 2023 Conference Paper

Sensor Localization by Few Distance Measurements via the Intersection of Implicit Manifolds

• Michael M. Bilevich
• Steven M. LaValle
• Dan Halperin

We present a general approach for determining the unknown (or uncertain) position and orientation of a sensor mounted on a robot in a known environment, using only a few distance measurements (between 2 to 6 typically), which is advantageous, among others, in sensor cost, and storage and information-communication resources. In-between the measurements, the robot can perform predetermined local motions in its workspace, which are useful for narrowing down the candidate poses of the sensor. We demonstrate our approach for planar workspaces, and show that, under mild transversality assumptions, already two measurements are sufficient to reduce the set of possible poses to a set of curves (one-dimensional objects) in the three-dimensional configuration space of the sensor $\mathbb{R}^{2}\times \mathbb{S}^{1}, $ and three or more measurements reduce the set of possible poses to a finite collection of points. However, analytically computing these potential poses for non-trivial intermediate motions between measurements raises substantial hardships and thus we resort to numerical approximation. We reduce the localization problem to a carefully tailored procedure of intersecting two or more implicitly defined two-manifolds, which we carry out to any desired accuracy, proving guarantees on the quality of the approximation. We demonstrate the real-time effectiveness of our method even at high accuracy on various scenarios and different allowable intermediate motions. We also present experiments with a physical robot. Our open-source software and supplementary materials are available at https://bitbucket.org/taucgl/vb-fdml-public.

AAMAS Conference 2022 Conference Paper

Refined Hardness of Distance-Optimal Multi-Agent Path Finding

• Tzvika Geft
• Dan Halperin

We study the computational complexity of multi-agent path finding (MAPF). Given a graph𝐺 and a set of agents, each having a start and target vertex, the goal is to find collision-free paths minimizing the total distance traveled. To better understand the source of difficulty of the problem, we aim to study the simplest and least constrained graph class for which it remains hard. To this end, we restrict 𝐺 to be a 2D grid, which is a ubiquitous abstraction, as it conveniently allows for modeling well-structured environments (e. g. , warehouses). Previous hardness results considered highly constrained 2D grids having only one vertex unoccupied by an agent, while the most restricted hardness result that allowed multiple empty vertices was for (non-grid) planar graphs. We therefore refine previous results by simultaneously considering both 2D grids and multiple empty vertices. We show that even in this case distance-optimal MAPF remains NP-hard, which settles an open problem posed by Banfi et al. [4]. We present a reduction directly from 3-SAT using simple gadgets, making our proof arguably more informative than previous work in terms of potential progress towards positive results. Furthermore, our reduction is the first linear one for the case where 𝐺 is planar, appearing nearly four decades after the first related result. This allows us to go a step further and exploit the Exponential Time Hypothesis (ETH) to obtain an exponential lower bound for the running time of the problem. Finally, as a stepping stone towards our main results, we prove the NP-hardness of the monotone case, in which agents move one by one with no intermediate stops.

ICRA Conference 2021 Conference Paper

Near-Optimal Multi-Robot Motion Planning with Finite Sampling

• Dror Dayan
• Kiril Solovey
• Marco Pavone 0001
• Dan Halperin

An underlying structure in several sampling-based methods for continuous multi-robot motion planning (MRMP) is the tensor roadmap (PR), which emerges from combining multiple PRM graphs constructed for the individual robots via a tensor product. We study the conditions under which the TR encodes a near-optimal solution for MRMP—satisfying these conditions implies near optimality for a variety of popular planners, including dRRT*, and the discrete methods M* and CBS when applied to the continuous domain. We develop the first finite-sample analysis of this kind, which specifies the number of samples, their deterministic distribution, and magnitude of the connection radii that should be used by each individual PRM graph, to guarantee near-optimality using the TR. This significantly improves upon a previous asymptotic analysis, wherein the number of samples tends to infinity. Our new finite sample-size analysis supports guaranteed high- quality solutions in practice within finite time. To achieve our new result, we first develop a sampling scheme, which we call the staggered grid, for finite-sample motion planning for individual robots, which requires significantly less samples than previous work. We then extend it to the much more involved MRMP setting which requires to account for interactions among multiple robots. Finally, we report on a few experiments that serve as a verification of our theoretical findings and raise interesting questions for further investigation.

SODA Conference 2021 Conference Paper

On Two-Handed Planar Assembly Partitioning with Connectivity Constraints

• Pankaj K. Agarwal
• Boris Aronov
• Tzvika Geft
• Dan Halperin

Assembly planning is a fundamental problem in robotics and automation, which aims to design a sequence of motions that brings the separate constituent parts of a product into their final placement in the product. It is convenient to study assembly planning in reverse order, where the following key problem, assembly partitioning, arises: Given a set of parts in their final placement in a product, partition them into two sets, each regarded as a rigid body, which we call a subassembly, such that these two subassemblies can be moved sufficiently far away from each other, without colliding with one another. The basic assembly planning problem is further complicated by practical consideration such as how to hold the parts in a subassembly together. Therefore, a desired property of a valid assembly partition is for each of the two subassemblies to be connected. In this paper we study a natural special case of the connected-assembly-partitioning problem: Given a connected set A of unit-grid squares in the plane, find a connected subset S ⊂ A such that A \ S is also connected and S can be rigidly translated to infinity along a prescribed direction without colliding with A\S. We show that even this simple problem is NP-complete, settling an open question posed by Wilson et al. a quarter of a century ago [16]. We complement the hardness result with two positive results. First, we show that the problem is fixed-parameter tractable and present an O (2 k n 2 )-time algorithm, where n = | A| and k = |S|. Second, we describe a special case of this problem where a connected partition can always be found in O ( n ) time.

ICRA Conference 2020 Conference Paper

Refined Analysis of Asymptotically-Optimal Kinodynamic Planning in the State-Cost Space

• Michal Kleinbort
• Edgar Granados
• Kiril Solovey
• Riccardo Bonalli
• Kostas E. Bekris
• Dan Halperin

We present a novel analysis of AO-RRT: a tree-based planner for motion planning with kinodynamic constraints, originally described by Hauser and Zhou (AO-X, 2016). AO-RRT explores the state-cost space and has been shown to efficiently obtain high-quality solutions in practice without relying on the availability of a computationally-intensive two-point boundary-value solver. Our main contribution is an optimality proof for the single-tree version of the algorithm-a variant that was not analyzed before. Our proof only requires a mild and easily-verifiable set of assumptions on the problem and system: Lipschitz-continuity of the cost function and the dynamics. In particular, we prove that for any system satisfying these assumptions, any trajectory having a piecewise-constant control function and positive clearance from the obstacles can be approximated arbitrarily well by a trajectory found by AORRT. We also discuss practical aspects of AORRT and present experimental comparisons of variants of the algorithm.

IROS Conference 2017 Conference Paper

Efficient sampling-based bottleneck pathfinding over cost maps

• Kiril Solovey
• Dan Halperin

We introduce a simple yet effective sampling-based planner that is tailored for bottleneck pathfinding: Given an implicitly-defined cost map M: R d Å R, which assigns to every point in space a real value, we wish to find a path connecting two given points, which minimizes the maximal value with respect to M. We demonstrate the capabilities of our algorithm, which we call bottleneck tree (BTT), on several challenging instances of the problem involving multiple agents, where it outperforms the state-of-the-art cost-map planning technique T-RRT. In addition to its efficiency, BTT requires the tuning of only a single parameter: the number of samples. On the theoretical side, we study the asymptotic properties of our method and consider the special setting where the computed trajectories must be monotone in all coordinates. This constraint arises in cases where the problem involves the coordination of multiple agents that are restricted to forward motions along predefined paths.

ICRA Conference 2015 Conference Paper

Asymptotically-optimal Motion Planning using lower bounds on cost

• Oren Salzman
• Dan Halperin

Many path-finding algorithms on graphs such as A* are sped up by using a heuristic function that gives lower bounds on the cost to reach the goal. Aiming to apply similar techniques to speed up sampling-based motion-planning algorithms, we use effective lower bounds on the cost between configurations to tightly estimate the cost-to-go. We then use these estimates in an anytime asymptotically-optimal algorithm which we call Motion Planning using Lower Bounds (MPLB). MPLB is based on the Fast Marching Trees (FMT*) algorithm [1] recently presented by Janson and Pavone. An advantage of our approach is that in many cases (especially as the number of samples grows) the weight of collision detection in the computation is almost negligible compared to the weight of nearest-neighbor queries. We prove that MPLB performs no more collision-detection calls than an anytime version of FMT*. Additionally, we demonstrate in simulations that for certain scenarios, the algorithmic tools presented here enable efficiently producing low-cost paths while spending only a small fraction of the running time on collision detection.

ICRA Conference 2015 Conference Paper

Efficient high-quality motion planning by fast all-pairs r-nearest-neighbors

• Michal Kleinbort
• Oren Salzman
• Dan Halperin

Sampling-based motion-planning algorithms typically rely on nearest-neighbor (NN) queries when constructing a roadmap. Recent results suggest that in various settings NN queries may be the computational bottleneck of such algorithms. Moreover, in several asymptotically-optimal algorithms these NN queries are of a specific form: Given a set of points and a radius r report all pairs of points whose distance is at most r. This calls for an application-specific NN data structure tailored to efficiently answering this type of queries. Randomly transformed grids (RTG) were recently proposed by Aiger et al. [1] as a tool to answer such queries in Euclidean spaces and have been shown to outperform common implementations of NN data structures for this type of queries. In this work we employ RTG for sampling-based motion-planning algorithms and describe an efficient implementation of the approach. We show that for motion planning, RTG allow for faster convergence to high-quality solutions when compared to existing NN data structures. Additionally, RTG enable significantly shorter construction times for batched-PRM variants; specifically, we demonstrate a speedup by a factor of two to three for some scenarios.

ICRA Conference 2015 Conference Paper

Optimal motion planning for a tethered robot: Efficient preprocessing for fast shortest paths queries

• Oren Salzman
• Dan Halperin

We study the problem of planning the shortest path for a polygonal robot anchored to a fixed base point by a finite tether translating among polygonal obstacles in the plane. Specifically, we preprocess the workspace to efficiently answer queries of the following type: Given a source location of the robot and an initial configuration of the tether, compute the shortest path to reach a target location while avoiding obstacles and adhering to the tether's constraints. Our work is an extension of the recent work by Kim et al. [1] who considered the problem for a point robot. Their algorithm relies on a discretization of the workspace and is optimal with respect to this discretization. We first replace their grid-based approach with a visibility-graph based approach. This allows to improve the running time of their algorithm by several orders of magnitude. Specifically, testing on a scenario similar to one presented by Kim et al. , the running time is improved by a factor of more than 500. Moreover, our approach, which plans optimal paths, is applicable to polygonal (translating) robots and can be used to plan a shortest path while ensuring a predefined clearance from the obstacles. We report on our experimental results on a variety of scenarios. In all cases the preprocessing time is less than one second on a standard-commodity laptop, and a typical query takes several tens of miliseconds.

ICRA Conference 2014 Conference Paper

Asymptotically near-optimal RRT for fast, high-quality, motion planning

• Oren Salzman
• Dan Halperin

We present Lower Bound Tree-RRT (LBT-RRT), a single-query sampling-based algorithm that is asymptotically near-optimal. Namely, the solution extracted from LBT-RRT converges to a solution that is within an approximation factor of 1 + ε of the optimal solution. Our algorithm allows for a continuous interpolation between the fast RRT algorithm and the asymptotically optimal RRT* and RRG algorithms. When the approximation factor is 1 (i. e. , no approximation is allowed), LBT-RRT behaves like the RRT* algorithm. When the approximation factor is unbounded, LBT-RRT behaves like the RRT algorithm. In between, LBT-RRT is shown to produce paths that have higher quality than RRT would produce and run faster than RRT* would run. This is done by maintaining a tree which is a sub-graph of the RRG roadmap and a second, auxiliary tree, which we call the lower-bound tree. The combination of the two trees, which is faster to maintain than the tree maintained by RRT*, efficiently guarantee asymptotic near-optimality. We suggest to use LBT-RRT for high-quality, anytime motion planning. We demonstrate the performance of the algorithm for scenarios ranging from 3 to 12 degrees of freedom and show that even for small approximation factors, the algorithm produces high-quality solutions (comparable to RRT*) with little runtime overhead when compared to RRT.

ICRA Conference 2013 Conference Paper

Sparsification of motion-planning roadmaps by edge contraction

• Doron Shaharabani
• Oren Salzman
• Pankaj K. Agarwal
• Dan Halperin

We present Roadmap Sparsification by Edge Contraction (RSEC), a simple and effective algorithm for reducing the size of a motion-planning roadmap. The algorithm exhibits minimal effect on the quality of paths that can be extracted from the new roadmap. The primitive operation used by RSEC is edge contraction-the contraction of a roadmap edge to a single vertex and the connection of the new vertex to the neighboring vertices of the contracted edge. For certain scenarios, we compress more than 98% of the edges and vertices at the cost of degradation of average shortest path length by at most 2%.

SODA Conference 1998 Conference Paper

The Dynamic Servers Problem

• Moses Charikar
• Dan Halperin
• Rajeev Motwani 0001

SODA Conference 1996 Conference Paper

Efficient Generation of k-Directional Assembly Sequences

• Pankaj K. Agarwal
• Mark de Berg
• Dan Halperin
• Micha Sharir

ICRA Conference 1995 Conference Paper

A Simple and Effeicient Procedure for Polyhedral Assembly Partitioning under Infinitesimal Motions

• Leonidas J. Guibas
• Dan Halperin
• Hirohisa Hirukawa
• Jean-Claude Latombe
• Randall H. Wilson

We study the following problem: Given a collection A of polyhedral parts in 3D, determine whether there exists a subset S of the parts that can be moved as a rigid body by an infinitesimal translation and rotation, without colliding with the rest of the parts, AS. A negative result implies that the object whose constituent parts are the collection A cannot be taken apart with two hands. A positive result, together with the list of movable parts in S and a direction of motion for S, can be used by an assembly sequence planner. This problem has attracted considerable attention within and outside the robotics community. We devise an efficient algorithm to solve this problem. Our solution is based on the ability to focus on selected portions of the tangent space of rigid motions and efficiently access these portions. The algorithm is complete (in the sense that it is guaranteed to find a solution if one exists), simple, and improves significantly over the best previously known solutions. We report experimental results with an implementation of our algorithm.

ICRA Conference 1995 Conference Paper

Assembly Partitioning along Simple Paths: the Case of Multiple Translations

• Dan Halperin
• Randall H. Wilson

We consider the following problem that arises in assembly planning: given an assembly, identify a subassembly that can be removed as a rigid object without disturbing the rest of the assembly. This is the assembly partitioning problem. Specifically, we consider planar assemblies of simple polygons and subassembly removal paths consisting of a single finite translation followed by a translation to infinity. Such paths are typical of the capabilities of simple actuators in fixed automation and other high-volume assembly machines. We present a polynomial-time algorithm to identify such a subassembly and removal path. We discuss extending the algorithm to 3D, other types of motions typical in non-robotic automated assembly, and motions consisting of more than two translations.

TCS Journal 1995 Journal Article

Reaching a goal with directional uncertainty

• Mark de Berg
• Leonidas Guibas
• Dan Halperin
• Mark Overmars
• Otfried Schwarzkopf
• Micha Sharir
• Monique Teillaud

We study two problems related to planar motion planning for robots with imperfect control, where, if the robot starts a linear movement in a certain commanded direction, we only know that its actual movement will be confined in a cone of angle α centered around the specified direction. First, we consider a single goal region, namely the “region at infinity”, and a set of polygonal obstacles, modeled as a set S of n line segments. We are interested in the region R α(S) from where we can reach infinity with a directional uncertainty of α. We prove that the maximum complexity of R α(S) is O( n α5 ). Second, we consider a collection of k polygonal goal regions of total complexity m, but without any obstacles. Here we prove an O(k 3 m) bound on the complexity of the region from where we can reach a goal region with a directional uncertainty of α. For both situations we also prove lower bounds on the maximum complexity, and we give efficient algorithms for computing the regions.

FOCS Conference 1993 Conference Paper

Near-Quadratic Bounds for the Motion Planning Problem for a Polygon in a Polygonal Environment

• Dan Halperin
• Micha Sharir

We consider the problem of planning the motion of an arbitrary k-sided polygonal robot B, free to translate and rotate in a polygonal environment V bounded by n edges. We show that the combinatorial complexity of a single connected component of the free configuration space of B is k/sup 3/n/sup 2/2/sup O(log(2/3)/ n). This is a significant improvement of the naive bound O((kn)/sup 3/); when k is constant, which is often the case in practice, this yields a near-quadratic bound on the complexity of such a component, which almost settles (in this special case) a long-standing conjecture regarding the complexity of a single cell in a three-dimensional arrangement of surfaces. We also present an algorithm that constructs a single component of the free configuration space of B in time O(n/sup 2+/spl epsi//), for any /spl epsi/>0, assuming B has a constant number of sides. This algorithm, combined with some standard techniques in motion planning, yields a solution to the underlying motion planning problem, within the same asymptotic running time. >