Author name cluster

Kostas E. Bekris

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.

65 papers

2 author rows

ICRA Conference 2025 Conference Paper

Integrating Model-Based Control and RL for Sim2Real Transfer of Tight Insertion Policies

Isidoros Marougkas
Dhruv Metha Ramesh
Joe Doerr
Edgar Granados
Aravind Sivaramakrishnan
Abdeslam Boularias
Kostas E. Bekris

Object insertion under tight tolerances (<Imm) is an important but challenging assembly task as even small errors can result in undesirable contacts. Recent efforts focused on Reinforcement Learning (RL), which often depends on careful definition of dense reward functions. This work proposes an effective strategy for such tasks that integrates traditional model-based control with RL to achieve improved insertion accuracy. The policy is trained exclusively in simulation and is zero-shot transferred to the real system. It employs a potential field-based controller to acquire a model-based policy for inserting a plug into a socket given full observability in simulation. This policy is then integrated with residual RL, which is trained in simulation given only a sparse, goal-reaching reward. A curriculum scheme over observation noise and action magnitude is used for training the residual RL policy. Both policy components use as input the SE(3) poses of both the plug and the socket and return the plug's SE (3) pose transform, which is executed by a robotic arm using a controller. The integrated policy is deployed on the real system without further training or fine-tuning, given a visual SE (3) object tracker. The proposed solution and alternatives are evaluated across a variety of objects and conditions in simulation and reality. The proposed approach outperforms recent RL-based methods in this domain and prior efforts with hybrid policies. Ablations highlight the impact of each component of the approach. For more information please refer to the corresponding website.

ICRA Conference 2025 Conference Paper

PROBE: Proprioceptive Obstacle Detection and Estimation while Navigating in Clutter

Dhruv Metha Ramesh
Aravind Sivaramakrishnan
Shreesh Keskar
Kostas E. Bekris
Jingjin Yu
Abdeslam Boularias

In critical applications, including search-and-rescue in degraded environments, blockages can be prevalent and prevent the effective deployment of certain sensing modalities, particularly vision, due to occlusion and the constrained range of view of onboard camera sensors. To enable robots to tackle these challenges, we propose a new approach, Proprioceptive Obstacle Detection and Estimation while navigating in clutter (PROBE), which instead relies only on the robot's proprioception to infer the presence or absence of occluded rectangular obstacles while predicting their dimensions and poses in SE (2). The proposed approach is a Transformer neural network that receives as input a history of applied torques and sensed whole-body movements of the robot and returns a parameterized representation of the obstacles in the environment. The effectiveness of PROBE is evaluated on simulated environments in Isaac Gym and with a real Unitree Go1 quadruped robot. The project webpage can be found at https://dhruvmetha.github.io/legged-probe/.

ICRA Conference 2024 Conference Paper

MORALS: Analysis of High-Dimensional Robot Controllers via Topological Tools in a Latent Space

Ewerton R. Vieira
Aravind Sivaramakrishnan
Sumanth Tangirala
Edgar Granados
Konstantin Mischaikow
Kostas E. Bekris

Estimating the region of attraction (RoA) for a robot controller is essential for safe application and controller composition. Many existing methods require a closed-form expression that limit applicability to data-driven controllers. Methods that operate only over trajectory rollouts tend to be data-hungry. In prior work, we have demonstrated that topological tools based on Morse Graphs (directed acyclic graphs that combinatorially represent the underlying nonlinear dynamics) offer data-efficient RoA estimation without needing an analytical model. They struggle, however, with high-dimensional systems as they operate over a state-space discretization. This paper presents Morse Graph-aided discovery of Regions of Attraction in a learned Latent Space (MORALS) **. The approach combines auto-encoding neural networks with Morse Graphs. MORALS shows promising predictive capabilities in estimating attractors and their RoAs for data-driven controllers operating over high-dimensional systems, including a 67-dim humanoid robot and a 96-dim 3-fingered manipulator. It first projects the dynamics of the controlled system into a learned latent space. Then, it constructs a reduced form of Morse Graphs representing the bistability of the underlying dynamics, i. e. , detecting when the controller results in a desired versus an undesired behavior. The evaluation on high-dimensional robotic datasets indicates data efficiency in RoA estimation.

IROS Conference 2024 Conference Paper

Roadmaps with Gaps over Controllers: Achieving Efficiency in Planning under Dynamics

Aravind Sivaramakrishnan
Sumanth Tangirala
Edgar Granados
Noah R. Carver
Kostas E. Bekris

This paper aims to improve the computational efficiency of motion planning for mobile robots with non-trivial dynamics through the use of learned controllers. Offline, a system-specific controller is first trained in an empty environment. Then, for the target environment, the approach constructs a data structure, a "Roadmap with Gaps, " to approximately learn how to solve planning queries using the learned controller. The roadmap nodes correspond to local regions. Edges correspond to applications of the learned controller that approximately connect these regions. Gaps arise as the controller does not perfectly connect pairs of individual states along edges. Online, given a query, a tree sampling-based motion planner uses the roadmap so that the tree’s expansion is informed towards the goal region. The tree expansion selects local subgoals given a wavefront on the roadmap that guides towards the goal. When the controller cannot reach a subgoal region, the planner resorts to random exploration to maintain probabilistic completeness and asymptotic optimality. The accompanying experimental evaluation shows that the approach significantly improves the computational efficiency of motion planning on various benchmarks, including physics-based vehicular models on uneven and varying friction terrains as well as a quadrotor under air pressure effects. Website: https://prx-kinodynamic.github.io/projects/rogue

ICRA Conference 2023 Conference Paper

Data-Efficient Characterization of the Global Dynamics of Robot Controllers with Confidence Guarantees

Ewerton R. Vieira
Aravind Sivaramakrishnan
Yao Song
Edgar Granados
Marcio Gameiro
Konstantin Mischaikow
Ying Hung
Kostas E. Bekris

This paper proposes an integration of surrogate modeling and topology to significantly reduce the amount of data required to describe the underlying global dynamics of robot controllers, including closed-box ones. A Gaussian Process (GP), trained with randomized short trajectories over the state-space, acts as a surrogate model for the underlying dynamical system. Then, a combinatorial representation is built and used to describe the dynamics in the form of a directed acyclic graph, known as Morse graph. The Morse graph is able to describe the system's attractors and their corresponding regions of attraction (RoA). Furthermore, a pointwise confidence level of the global dynamics estimation over the entire state space is provided. In contrast to alternatives, the framework does not require estimation of Lyapunov functions, alleviating the need for high prediction accuracy of the GP. The framework is suit-able for data-driven controllers that do not expose an analytical model as long as Lipschitz-continuity is satisfied. The method is compared against established analytical and recent machine learning alternatives for estimating Roas, outperforming them in data efficiency without sacrificing accuracy. Link to code: https://go.rutgers.edu/49hy35en

IROS Conference 2023 Conference Paper

Real2Sim2Real Transfer for Control of Cable-Driven Robots Via a Differentiable Physics Engine

Kun Wang 0038
William R. Johnson III
Shiyang Lu
Xiaonan Huang
Joran W. Booth
Rebecca Kramer-Bottiglio
Mridul Aanjaneya
Kostas E. Bekris

Tensegrity robots, composed of rigid rods and flexible cables, exhibit high strength-to-weight ratios and significant deformations, which enable them to navigate unstructured terrains and survive harsh impacts. They are hard to control, however, due to high dimensionality, complex dynamics, and a coupled architecture. Physics-based simulation is a promising avenue for developing locomotion policies that can be transferred to real robots. Nevertheless, modeling tensegrity robots is a complex task due to a substantial sim2real gap. To address this issue, this paper describes a Real2Sim2Real (R2S2R) strategy for tensegrity robots. This strategy is based on a differentiable physics engine that can be trained given limited data from a real robot. These data include offline measurements of physical properties, such as mass and geometry for various robot components, and the observation of a trajectory using a random control policy. With the data from the real robot, the engine can be iteratively refined and used to discover locomotion policies that are directly transferable to the real robot. Beyond the R2S2R pipeline, key contributions of this work include computing non-zero gradients at contact points, a loss function for matching tensegrity locomotion gaits, and a trajectory segmentation technique that avoids conflicts in gradient evaluation during training. Multiple iterations of the R2S2R process are demonstrated and evaluated on a real 3-bar tensegrity robot.

ICRA Conference 2023 Conference Paper

Resolution Complete In-Place Object Retrieval given Known Object Models

Daniel Nakhimovich
Yinglong Miao
Kostas E. Bekris

This work proposes a robot task planning framework for retrieving a target object in a confined workspace among multiple stacked objects that obstruct the target. The robot can use prehensile picking and in-workspace placing actions. The method assumes access to 3D models for the visible objects in the scene. The key contribution is in achieving desirable properties, i. e. , to provide (a) safety, by avoiding collisions with sensed obstacles, objects, and occluded regions, and (b) resolution completeness (RC) - or probabilistic completeness (PC) depending on implementation - which indicates a solution will be eventually found (if it exists) as the resolution of algorithmic parameters increases. A heuristic variant of the basic RC algorithm is also proposed to solve the task more efficiently while retaining the desirable properties. Simulation results compare using random picking and placing operations against the basic RC algorithm that reasons about object dependency as well as its heuristic variant. The success rate is higher for the RC approaches given the same amount of time. The heuristic variant is able to solve the problem even more efficiently than the basic approach. The integration of the RC algorithm with perception, where an RGB-D sensor detects the objects as they are being moved, enables real robot demonstrations of safely retrieving target objects from a cluttered shelf.

ICRA Conference 2023 Conference Paper

Self-Supervised Learning of Object Segmentation from Unlabeled RGB-D Videos

Shiyang Lu
Yunfu Deng
Abdeslam Boularias
Kostas E. Bekris

This work proposes a self-supervised learning system for segmenting rigid objects in RGB images. The proposed pipeline is trained on unlabeled RGB-D videos of static objects, which can be captured with a camera carried by a mobile robot. A key feature of the self-supervised training process is a graph-matching algorithm that operates on the over-segmentation output of the point cloud that is reconstructed from each video. The graph matching, along with point cloud registration, is able to find reoccurring object patterns across videos and combine them into 3D object pseudo labels, even under occlusions or different viewing angles. Projected 2D object masks from 3D pseudo labels are used to train a pixel-wise feature extractor through contrastive learning. During online inference, a clustering method uses the learned features to cluster foreground pixels into object segments. Experiments highlight the method's effectiveness on both real and synthetic video datasets, which include cluttered scenes of tabletop objects. The proposed method outperforms existing unsupervised methods for object segmentation by a large margin.

ICRA Conference 2022 Conference Paper

A Recurrent Differentiable Engine for Modeling Tensegrity Robots Trainable with Low-Frequency Data

Kun Wang 0038
Mridul Aanjaneya
Kostas E. Bekris

Tensegrity robots, composed of rigid rods and flexible cables, are difficult to accurately model and control given the presence of complex dynamics and high number of DoFs. Differentiable physics engines have been recently proposed as a data-driven approach for model identification of such complex robotic systems. These engines are often executed at a high-frequency to achieve accurate simulation. Ground truth trajectories for training differentiable engines, however, are not typically available at such high frequencies due to limitations of real-world sensors. The present work focuses on this frequency mismatch, which impacts the modeling accuracy. We proposed a recurrent structure for a differentiable physics engine of tensegrity robots, which can be trained effectively even with low-frequency trajectories. To train this new recurrent engine in a robust way, this work introduces relative to prior work: (i) a new implicit integration scheme, (ii) a progressive training pipeline, and (iii) a differentiable collision checker. A model of NASA's icosahedron SUPERballBot on MuJoCo is used as the ground truth system to collect training data. Simulated experiments show that once the recurrent differentiable engine has been trained given the low-frequency trajectories from MuJoCo, it is able to match the behavior of MuJoCo's system. The criterion for success is whether a locomotion strategy learned using the differentiable engine can be transferred back to the ground-truth system and result in a similar motion. Notably, the amount of ground truth data needed to train the differentiable engine, such that the policy is transferable to the ground truth system, is 1% of the data needed to train the policy directly on the ground-truth system.

ICRA Conference 2022 Conference Paper

CaTGrasp: Learning Category-Level Task-Relevant Grasping in Clutter from Simulation

Bowen Wen
Wenzhao Lian
Kostas E. Bekris
Stefan Schaal

Task-relevant grasping is critical for industrial assembly, where downstream manipulation tasks constrain the set of valid grasps. Learning how to perform this task, however, is challenging, since task-relevant grasp labels are hard to define and annotate. There is also yet no consensus on proper representations for modeling or off-the-shelf tools for performing task-relevant grasps. This work proposes a framework to learn task-relevant grasping for industrial objects without the need of time-consuming real-world data collection or manual annotation. To achieve this, the entire framework is trained solely in simulation, including supervised training with synthetic label generation and self-supervised, hand-object interaction. In the context of this framework, this paper proposes a novel, object-centric canonical representation at the category level, which allows establishing dense correspondence across object instances and transferring task-relevant grasps to novel instances. Extensive experiments on task-relevant grasping of densely-cluttered industrial objects are conducted in both simulation and real-world setups, demonstrating the effectiveness of the proposed framework. Code and data are available at https://sites.google.com/view/catgrasp.

ICRA Conference 2022 Conference Paper

Efficient and High-quality Prehensile Rearrangement in Cluttered and Confined Spaces

Rui Wang 0087
Yinglong Miao
Kostas E. Bekris

Prehensile object rearrangement in cluttered and confined spaces has broad applications but is also challenging. For instance, rearranging products in a grocery shelf means that the robot cannot directly access all objects and has limited free space. This is harder than tabletop rearrangement where objects are easily accessible with top-down grasps, which simplifies robot-object interactions. This work focuses on problems where such interactions are critical for completing tasks. It proposes a new efficient and complete solver under general constraints for monotone instances, which can be solved by moving each object at most once. The monotone solver reasons about robot-object constraints and uses them to effectively prune the search space. The new monotone solver is integrated with a global planner to solve non-monotone instances with high-quality solutions fast. Furthermore, this work contributes an effective pre-processing tool to significantly speed up online motion planning queries for rearrangement in confined spaces. Experiments further demonstrate that the proposed monotone solver, equipped with the pre-processing tool, results in 57. 3% faster computation and 3 times higher success rate than state-of-the-art methods. Similarly, the resulting global planner is computationally more efficient and has a higher success rate, while producing high-quality solutions for non-monotone instances (i. e. , only 1. 3 additional actions are needed on average). Videos of demonstrating solutions on a real robotic system and codes can be found at https://github.com/Rui1223/uniform_object_rearrangement.

ICRA Conference 2022 Conference Paper

Fast High-Quality Tabletop Rearrangement in Bounded Workspace

Kai Gao
Darren Lau
Baichuan Huang
Kostas E. Bekris
Jingjin Yu

In this paper, we examine the problem of rearranging many objects on a tabletop in a cluttered setting using overhand grasps. Efficient solutions for the problem, which capture a common task that we solve on a daily basis, are essential in enabling truly intelligent robotic manipulation. In a given instance, objects may need to be placed at temporary positions (“buffers”) to complete the rearrangement, but allocating these buffer locations can be highly challenging in a cluttered environment. To tackle the challenge, a two-step baseline planner is first developed, which generates a primitive plan based on inherent combinatorial constraints induced by start and goal poses of the objects and then selects buffer locations assisted by the primitive plan. We then employ the “lazy” planner in a tree search framework which is further sped up by adapting a novel preprocessing routine. Simulation experiments show our methods can quickly generate high-quality solutions and are more robust in solving large-scale instances than existing state-of-the-art approaches. source: github.com/arc-l/TRLB

ICAPS Conference 2022 Conference Paper

Lazy Rearrangement Planning in Confined Spaces

Rui Wang 0087
Kai Gao
Jingjin Yu
Kostas E. Bekris

Object rearrangement is important for many applications but remains challenging, especially in confined spaces, such as shelves, where objects cannot be accessed from above and they block reachability to each other. Such constraints require many motion planning and collision checking calls, which are computationally expensive. In addition, the arrangement space grows exponentially with the number of objects. To address these issues, this work introduces a lazy evaluation framework with a local monotone solver and a global planner. Monotone instances are those that can be solved by moving each object at most once. A key insight is that reachability constraints at the grasps for objects' starts and goals can quickly reveal dependencies between objects without having to execute expensive motion planning queries. Given that, the local solver builds lazily a search tree that respects these reachability constraints without verifying that the arm paths are collision free. It only collision checks when a promising solution is found. If a monotone solution is not found, the non-monotone planner loads the lazy search tree and explores ways to move objects to intermediate locations from where monotone solutions to the goal can be found. Results show that the proposed framework can solve difficult instances in confined spaces with up to 16 objects, which state-of-the-art methods fail to solve. It also solves problems faster than alternatives, when the alternatives find a solution. It also achieves high-quality solutions, i. e. , only 1. 8 additional actions on average are needed for non-monotone instances.

ICRA Conference 2022 Conference Paper

Learning Sensorimotor Primitives of Sequential Manipulation Tasks from Visual Demonstrations

Junchi Liang
Bowen Wen
Kostas E. Bekris
Abdeslam Boularias

This work aims to learn how to perform complex robot manipulation tasks that are composed of several, consecutively executed low-level sub-tasks, given as input a few visual demonstrations of the tasks performed by a person. The sub-tasks consist of moving the robot's end-effector until it reaches a sub-goal region in the task space, performing an action, and triggering the next sub-task when a pre-condition is met. Most prior work in this domain has been concerned with learning only low-level tasks, such as hitting a ball or reaching an object and grasping it. This paper describes a new neural network-based framework for learning simultaneously low-level policies as well as high-level policies, such as deciding which object to pick next or where to place it relative to other objects in the scene. A key feature of the proposed approach is that the policies are learned directly from raw videos of task demonstrations, without any manual annotation or post-processing of the data. Empirical results on object manipulation tasks with a robotic arm show that the proposed network can efficiently learn from real visual demonstrations to perform the tasks, and outperforms popular imitation learning algorithms.

ICRA Conference 2022 Conference Paper

Model Identification and Control of a Low-cost Mobile Robot with Omnidirectional Wheels using Differentiable Physics

Edgar Granados
Abdeslam Boularias
Kostas E. Bekris
Mridul Aanjaneya

We present a new data-driven technique for pre-dicting the motion of a low-cost omnidirectional mobile robot under the influence of motor torques and friction forces. Our method utilizes a novel differentiable physics engine for analytically computing the gradient of the deviation between predicted motion trajectories and real-world trajectories. This allows to automatically learn and fine-tune the unknown friction coefficients on-the-fly, by minimizing a carefully designed loss function using gradient descent. Experiments show that the predicted trajectories are in excellent agreement with their real-world counterparts. Our proposed approach is computationally superior to existing black-box optimization methods, requiring very few real-world samples for accurate trajectory prediction compared to physics-agnostic techniques, such as neural net-works. Experiments also demonstrate that the proposed method allows the robot to quickly adapt to changes in the terrain. Our proposed approach combines the data-efficiency of classical analytical models that are derived from first principles, with the flexibility of data-driven methods, which makes it appropriate for low-cost mobile robots. Project website: https://go.rutgers.edu/mqxn2x6h

ICRA Conference 2022 Conference Paper

Online Object Model Reconstruction and Reuse for Lifelong Improvement of Robot Manipulation

Shiyang Lu
Rui Wang 0087
Yinglong Miao
Chaitanya Mitash
Kostas E. Bekris

This work proposes a robotic pipeline for picking and constrained placement of objects without geometric shape priors. Compared to recent efforts developed for similar tasks, where every object was assumed to be novel, the proposed system recognizes previously manipulated objects and per-forms online model reconstruction and reuse. Over a lifelong manipulation process, the system keeps learning features of objects it has interacted with and updates their reconstructed models. Whenever an instance of a previously manipulated object reappears, the system aims to first recognize it and then register its previously reconstructed model given the current observation. This step greatly reduces object shape uncertainty allowing the system to even reason for parts of objects, which are currently not observable. This also results in better manipulation efficiency as it reduces the need for active perception of the target object during manipulation. To get a reusable reconstructed model, the proposed pipeline adopts: i) TSDF for object representation, and ii) a variant of the standard particle filter algorithm for pose estimation and tracking of the partial object model. Furthermore, an effective way to construct and maintain a dataset of manipulated objects is presented. A sequence of real-world manipulation experiments is performed. They show how future manipulation tasks become more effective and efficient by reusing reconstructed models of previously manipulated objects, which were generated during their prior manipulation, instead of treating objects as novel every time.

ICRA Conference 2022 Conference Paper

Persistent Homology for Effective Non-Prehensile Manipulation

Ewerton R. Vieira
Daniel Nakhimovich
Kai Gao
Rui Wang 0087
Jingjin Yu
Kostas E. Bekris

This work explores the use of topological tools for achieving effective non-prehensile manipulation in cluttered, constrained workspaces. In particular, it proposes the use of persistent homology as a guiding principle in identifying the appropriate non-prehensile actions, such as pushing, to clean a cluttered space with a robotic arm so as to allow the retrieval of a target object. Persistent homology enables the automatic identification of connected components of blocking objects in the space without the need for manual input or tuning of parameters. The proposed algorithm uses this information to push groups of cylindrical objects together and aims to minimize the number of pushing actions needed to reach to the target. Simulated experiments in a physics engine using a model of the Baxter robot show that the proposed topology-driven solution is achieving significantly higher success rate in solving such constrained problems relatively to state-of-the-art alternatives from the literature. It manages to keep the number of pushing actions low, is computationally efficient and the resulting decisions and motion appear natural for effectively solving such tasks.

IROS Conference 2022 Conference Paper

Terrain-Aware Learned Controllers for Sampling-Based Kinodynamic Planning over Physically Simulated Terrains

Troy McMahon
Aravind Sivaramakrishnan
Kushal Kedia
Edgar Granados
Kostas E. Bekris

This paper explores learning an effective controller for improving the efficiency of kinodynamic planning for vehicular systems navigating uneven terrains. It describes the pipeline for training the corresponding controller and using it for motion planning purposes. The training process uses a soft actor-critic approach with hindsight experience replay to train a model, which is parameterized by the incline of the robot's local terrain. This trained model is then used during the expansion process of an asymptotically optimal kinodynamic planner to generate controls that allow the robot to reach desired local states. It is also used to define a heuristic cost-to-go function for the planner via a wavefront operation that estimates the cost of reaching the global goal. The cost-to-go function is used both for selecting nodes for expansion as well as for generating local goals for the controller to expand towards. The accompanying experimental section applies the integrated planning solution on models of all-terrain robots in a variety of physically simulated terrains. It shows that the proposed terrain-aware controller and the proposed wavefront function based on the cost-to-go model enable motion planners to find solutions in less time and with lower cost than alternatives. An ablation study emphasizes the benefits of a learned controller that is parameterized by the incline of the robot's local terrain as well as of an incremental training process for the controller.

IROS Conference 2021 Conference Paper

BundleTrack: 6D Pose Tracking for Novel Objects without Instance or Category-Level 3D Models

Bowen Wen
Kostas E. Bekris

Tracking the 6D pose of objects in video sequences is important for robot manipulation. Most prior efforts, however, often assume that the target object's CAD model, at least at a category-level, is available for offline training or during online template matching. This work proposes BundleTrack, a general framework for 6D pose tracking of novel objects, which does not depend upon 3D models, either at the instance or category-level. It leverages the complementary attributes of recent advances in deep learning for segmentation and robust feature extraction, as well as memory-augmented pose graph optimization for spatiotemporal consistency. This enables long-term, low-drift tracking under various challenging scenarios, including significant occlusions and object motions. Comprehensive experiments given two public benchmarks demonstrate that the proposed approach significantly outperforms state-of-art, category-level 6D tracking or dynamic SLAM methods. When compared against state-of-art methods that rely on an object instance CAD model, comparable performance is achieved, despite the proposed method’s reduced information requirements. An efficient implementation in CUDA provides a real-time performance of 10Hz for the entire framework. Code is available at: https://github.com/wenbowen123/BundleTrack

IROS Conference 2021 Conference Paper

Improving Kinodynamic Planners for Vehicular Navigation with Learned Goal-Reaching Controllers

Aravind Sivaramakrishnan
Edgar Granados
Seth Karten
Troy McMahon
Kostas E. Bekris

This paper aims to improve the path quality and computational efficiency of sampling-based kinodynamic planners for vehicular navigation. It proposes a learning framework for identifying promising controls during the expansion process of sampling-based planners. Given a dynamics model, a reinforcement learning process is trained offline to return a low-cost control that reaches a local goal state (i. e. , a waypoint) in the absence of obstacles. By focusing on the system’s dynamics and not knowing the environment, this process is data-efficient and takes place once for a robotic system. In this way, it can be reused in different environments. The planner generates online local goal states for the learned controller in an informed manner to bias towards the goal and consecutively in an exploratory, random manner. For the informed expansion, local goal states are generated either via (a) medial axis information in environments with obstacles, or (b) wavefront information for setups with traversability costs. The learning process and the resulting planning framework are evaluated for a first and second-order differential drive system, as well as a physically simulated Segway robot. The results show that the proposed integration of learning and planning can produce higher quality paths than sampling-based kinodynamic planning with random controls in fewer iterations and computation time.

IROS Conference 2021 Conference Paper

Sim2Sim Evaluation of a Novel Data-Efficient Differentiable Physics Engine for Tensegrity Robots

Kun Wang 0038
Mridul Aanjaneya
Kostas E. Bekris

Learning policies in simulation is promising for reducing human effort when training robot controllers. This is especially true for soft robots that are more adaptive and safe but also more difficult to accurately model and control. The sim2real gap is the main barrier to successfully transfer policies from simulation to a real robot. System identification can be applied to reduce this gap but traditional identification methods require a lot of manual tuning. Data-driven alternatives can tune dynamical models directly from data but are often data hungry, which also incorporates human effort in collecting data. This work proposes a data-driven, end-to-end differentiable simulator focused on the exciting but challenging domain of tensegrity robots. To the best of the authors’ knowledge, this is the first differentiable physics engine for tensegrity robots that supports cable, contact, and actuation modeling. The aim is to develop a reasonably simplified, data-driven simulation, which can learn approximate dynamics with limited ground truth data. The dynamics must be accurate enough to generate policies that can be transferred back to the ground-truth system. As a first step in this direction, the current work demonstrates sim2sim transfer, where the unknown physical model of MuJoCo acts as a ground truth system. Two different tensegrity robots are used for evaluation and learning of locomotion policies, a 6-bar and a 3-bar tensegrity. The results indicate that only 0. 25% of ground truth data are needed to train a policy that works on the ground truth system when the differentiable engine is used for training against training the policy directly on the ground truth system.

ICRA Conference 2021 Conference Paper

Uniform Object Rearrangement: From Complete Monotone Primitives to Efficient Non-Monotone Informed Search

Rui Wang 0087
Kai Gao
Daniel Nakhimovich
Jingjin Yu
Kostas E. Bekris

Object rearrangement is a widely-applicable and challenging task for robots. Geometric constraints must be carefully examined to avoid collisions and combinatorial issues arise as the number of objects increases. This work studies the algorithmic structure of rearranging uniform objects, where robot-object collisions do not occur but object-object collisions have to be avoided. The objective is minimizing the number of object transfers under the assumption that the robot can manipulate one object at a time. An efficiently computable decomposition of the configuration space is used to create a "region graph", which classifies all continuous paths of equivalent collision possibilities. Based on this compact but rich representation, a complete dynamic programming primitive DFS DP performs a recursive depth first search to solve monotone problems quickly, i. e. , those instances that do not require objects to be moved first to an intermediate buffer. DFS DP is extended to solve single-buffer, non-monotone instances, given a choice of an object and a buffer. This work utilizes these primitives as local planners in an informed search framework for more general, non-monotone instances. The search utilizes partial solutions from the primitives to identify the most promising choice of objects and buffers. Experiments demonstrate that the proposed solution returns near-optimal paths with higher success rate, even for challenging non-monotone instances, than other leading alternatives.

ICRA Conference 2020 Conference Paper

Motion Planning with Competency-Aware Transition Models for Underactuated Adaptive Hands

Avishai Sintov
Andrew Kimmel
Kostas E. Bekris
Abdeslam Boularias

Underactuated adaptive hands simplify grasping tasks but it is difficult to model their interactions with objects during in-hand manipulation. Learned data-driven models have been recently shown to be efficient in motion planning and control of such hands. Still, the accuracy of the models is limited even with the addition of more data. This becomes important for long horizon predictions, where errors are accumulated along the length of a path. Instead of throwing more data into learning the transition model, this work proposes to rather invest a portion of the training data in a critic model. The critic is trained to estimate the error of the transition model given a state and a sequence of future actions, along with information of past actions. The critic is used to reformulate the cost function of an asymptotically optimal motion planner. Given the critic, the planner directs planned paths to less erroneous regions in the state space. The approach is evaluated against standard motion planning on simulated and real hands. The results show that it outperforms an alternative where all the available data is used for training the transition model without a critic.

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.

ICRA Conference 2020 Conference Paper

Robust, Occlusion-aware Pose Estimation for Objects Grasped by Adaptive Hands

Bowen Wen
Chaitanya Mitash
Sruthi Soorian
Andrew Kimmel
Avishai Sintov
Kostas E. Bekris

Many manipulation tasks, such as placement or within-hand manipulation, require the object's pose relative to a robot hand. The task is difficult when the hand significantly occludes the object. It is especially hard for adaptive hands, for which it is not easy to detect the finger's configuration. In addition, RGB-only approaches face issues with texture-less objects or when the hand and the object look similar. This paper presents a depth-based framework, which aims for robust pose estimation and short response times. The approach detects the adaptive hand's state via efficient parallel search given the highest overlap between the hand's model and the point cloud. The hand's point cloud is pruned and robust global registration is performed to generate object pose hypotheses, which are clustered. False hypotheses are pruned via physical reasoning. The remaining poses' quality is evaluated given agreement with observed data. Extensive evaluation on synthetic and real data demonstrates the accuracy and computational efficiency of the framework when applied on challenging, highly-occluded scenarios for different object types. An ablation study identifies how the framework's components help in performance. This work also provides a dataset for in-hand 6D object pose estimation. Code and dataset are available at: https://github.com/wenbowen123/icra20-hand-object-pose.

IROS Conference 2020 Conference Paper

Safe and Effective Picking Paths in Clutter given Discrete Distributions of Object Poses

Rui Wang 0087
Chaitanya Mitash
Shiyang Lu
Daniel Boehm
Kostas E. Bekris

Picking an item in the presence of other objects can be challenging as it involves occlusions and partial views. Given object models, one approach is to perform object pose estimation and use the most likely candidate pose per object to pick the target without collisions. This approach, however, ignores the uncertainty of the perception process both regarding the target's and the surrounding objects' poses. This work proposes first a perception process for 6D pose estimation, which returns a discrete distribution of object poses in a scene. Then, an open-loop planning pipeline is proposed to return safe and effective solutions for moving a robotic arm to pick, which (a) minimizes the probability of collision with the obstructing objects; and (b) maximizes the probability of reaching the target item. The planning framework models the challenge as a stochastic variant of the Minimum Constraint Removal (MCR) problem. The effectiveness of the methodology is verified given both simulated and real data in different scenarios. The experiments demonstrate the importance of considering the uncertainty of the perception process in terms of safe execution. The results also show that the methodology is more effective than conservative MCR approaches, which avoid all possible object poses regardless of the reported uncertainty.

IROS Conference 2020 Conference Paper

se(3)-TrackNet: Data-driven 6D Pose Tracking by Calibrating Image Residuals in Synthetic Domains

Bowen Wen
Chaitanya Mitash
Baozhang Ren
Kostas E. Bekris

Tracking the 6D pose of objects in video sequences is important for robot manipulation. This task, however, introduces multiple challenges: (i) robot manipulation involves significant occlusions; (ii) data and annotations are troublesome and difficult to collect for 6D poses, which complicates machine learning solutions, and (iii) incremental error drift often accumulates in long term tracking to necessitate re-initialization of the object's pose. This work proposes a data-driven optimization approach for long-term, 6D pose tracking. It aims to identify the optimal relative pose given the current RGB-D observation and a synthetic image conditioned on the previous best estimate and the object's model. The key contribution in this context is a novel neural network architecture, which appropriately disentangles the feature encoding to help reduce domain shift, and an effective 3D orientation representation via Lie Algebra. Consequently, even when the network is trained only with synthetic data can work effectively over real images. Comprehensive experiments over benchmarks - existing ones as well as a new dataset with significant occlusions related to object manipulation - show that the proposed approach achieves consistently robust estimates and outperforms alternatives, even though they have been trained with real images. The approach is also the most computationally efficient among the alternatives and achieves a tracking frequency of 90. 9Hz.

ICRA Conference 2019 Conference Paper

Towards Robust Product Packing with a Minimalistic End-Effector

Rahul Shome
Wei N. Tang
Changkyu Song
Chaitanya Mitash
Hristiyan Kourtev
Jingjin Yu
Abdeslam Boularias
Kostas E. Bekris

Advances in sensor technologies, object detection algorithms, planning frameworks and hardware designs have motivated the deployment of robots in warehouse automation. A variety of such applications, like order fulfillment or packing tasks, require picking objects from unstructured piles and carefully arranging them in bins or containers. Desirable solutions need to be low-cost, easily deployable and controllable, making minimalistic hardware choices desirable. The challenge in designing an effective solution to this problem relates to appropriately integrating multiple components, so as to achieve a robust pipeline that minimizes failure conditions. The current work proposes a complete pipeline for solving such packing tasks, given access only to RGB-D data and a single robot arm with a vacuum-based end-effector, which is also used as a pushing finger. To achieve the desired level of robustness, three key manipulation primitives are identified, which take advantage of the environment and simple operations to successfully pack multiple cubic objects. The overall approach is demonstrated to be robust to execution and perception errors. The impact of each manipulation primitive is evaluated by considering different versions of the proposed pipeline, which incrementally introduce reasoning about object poses and corrective manipulation actions.

ICRA Conference 2018 Conference Paper

Discovering a Library of Rhythmic Gaits for Spherical Tensegrity Locomotion

Colin Rennie
Kostas E. Bekris

Tensegrity robots, which combine both rigid and soft elements, provide exciting new locomotion capabilities but introduce significant control challenges given their high-dimensionality and non-linear nature. This work first defines an effective parameterization of a spherical tensegrity for generating rhythmic gaits based on Central Pattern Generators (cp G). This allows the definition of periodic and rhythmic control signals, while exposing only five gait parameters. Then, this work proposes a framework for optimizing such gaits by exploring the parameter space through Bayesian Optimization on an underlying Gaussian Process regression model. The objective is to provide gaits that allow the platform to move along different directions with high velocity. Additionally, kNN binary classifiers are trained to estimate whether a parameter sample will result in an effective gait. The classification biases the sampling toward subspaces likely to yield effective gaits. An asynchronous communication layer is defined between the optimization and classification processes. The proposed gait discovery process is shown to efficiently optimize the parameters of gaits defined given the novel CPG architecture and outperforms less holistic approaches and Monte Carlo sampling.

IROS Conference 2018 Conference Paper

Efficient and Asymptotically Optimal Kinodynamic Motion Planning via Dominance-Informed Regions

Zakary Littlefield
Kostas E. Bekris

Motion planners have been recently developed that provide path quality guarantees for robots with dynamics. This work aims to improve upon their efficiency, while maintaining their properties. Inspired by informed search principles, one objective is to use heuristics. Nevertheless, comprehensive and fast spatial exploration of the state space is still important in robotics. For this reason, this work introduces Dominance-Informed Regions (DIR), which express both whether parts of the space are unexplored and whether they lies along a high quality path. Furthermore, to speed up the generation of a successful successor state, which involves collision checking or physics-based simulation, a proposed strategy generates the most promising successor in an informed way, while maintaing properties. Overall, this paper introduces a new informed and asymptotically optimal kinodynamic motion planner, the Dominance-Informed Region Tree (DIRT). The method balances exploration-exploitation tradeoffs without many explicit parameters. It is shown to outperform sampling-based and search-based methods for robots to significant dynamics.

IROS Conference 2018 Conference Paper

Efficient Model Identification for Tensegrity Locomotion

Shaojun Zhu
David Allen Surovik
Kostas E. Bekris
Abdeslam Boularias

This paper aims to identify in a practical manner unknown physical parameters, such as mechanical models of actuated robot links, which are critical in dynamical robotic tasks. Key features include the use of an off-the-shelf physics engine and the Bayesian optimization framework. The task being considered is locomotion with a high-dimensional, compliant Tensegrity robot. A key insight, in this case, is the need to project the space of models into an appropriate lower dimensional space for time efficiency. Comparisons with alternatives indicate that the proposed method can identify the parameters more accurately within the given time budget, which also results in more precise locomotion control.

IJCAI Conference 2018 Conference Paper

Fast Model Identification via Physics Engines for Data-Efficient Policy Search

Shaojun Zhu
Andrew Kimmel
Kostas E. Bekris
Abdeslam Boularias

This paper presents a method for identifying mechanical parameters of robots or objects, such as their mass and friction coefficients. Key features are the use of off-the-shelf physics engines and the adaptation of a Bayesian optimization technique towards minimizing the number of real-world experiments needed for model-based reinforcement learning. The proposed framework reproduces in a physics engine experiments performed on a real robot and optimizes the model's mechanical parameters so as to match real-world trajectories. The optimized model is then used for learning a policy in simulation, before real-world deployment. It is well understood, however, that it is hard to exactly reproduce real trajectories in simulation. Moreover, a near-optimal policy can be frequently found with an imperfect model. Therefore, this work proposes a strategy for identifying a model that is just good enough to approximate the value of a locally optimal policy with a certain confidence, instead of wasting effort on identifying the most accurate model. Evaluations, performed both in simulation and on a real robotic manipulation task, indicate that the proposed strategy results in an overall time-efficient, integrated model identification and learning solution, which significantly improves the data-efficiency of existing policy search algorithms.

ICRA Conference 2018 Conference Paper

Improving 6D Pose Estimation of Objects in Clutter Via Physics-Aware Monte Carlo Tree Search

Chaitanya Mitash
Abdeslam Boularias
Kostas E. Bekris

This work proposes a process for efficiently searching over combinations of individual object 6D pose hypotheses in cluttered scenes, especially in cases involving occlusions and objects resting on each other. The initial set of candidate object poses is generated from state-of-the-art object detection and global point cloud registration techniques. The best scored pose per object by using these techniques may not be accurate due to overlaps and occlusions. Nevertheless, experimental indications provided in this work show that object poses with lower ranks may be closer to the real poses than ones with high ranks according to registration techniques. This motivates a global optimization process for improving these poses by taking into account scene-level physical interactions between objects. It also implies that the Cartesian product of candidate poses for interacting objects must be searched so as to identify the best scene-level hypothesis. To perform the search efficiently, the candidate poses for each object are clustered so as to reduce their number but still keep a sufficient diversity. Then, searching over the combinations of candidate object poses is performed through a Monte Carlo Tree Search (MCTS) process that uses the similarity between the observed depth image of the scene and a rendering of the scene given the hypothesized pose as a score that guides the search procedure. MCTS handles in a principled way the tradeoff between fine-tuning the most promising poses and exploring new ones, by using the Upper Confidence Bound (UCB) technique. Experimental results indicate that this process is able to quickly identify in cluttered scenes physically-consistent object poses that are significantly closer to ground truth compared to poses found by point cloud registration methods.

IROS Conference 2017 Conference Paper

A self-supervised learning system for object detection using physics simulation and multi-view pose estimation

Chaitanya Mitash
Kostas E. Bekris
Abdeslam Boularias

Progress has been achieved recently in object detection given advancements in deep learning. Nevertheless, such tools typically require a large amount of training data and significant manual effort to label objects. This limits their applicability in robotics, where solutions must scale to a large number of objects and variety of conditions. This work proposes an autonomous process for training a Convolutional Neural Network (CNN) for object detection and pose estimation in robotic setups. The focus is on detecting objects placed in cluttered, tight environments, such as a shelf with multiple objects. In particular, given access to 3D object models, several aspects of the environment are physically simulated. The models are placed in physically realistic poses with respect to their environment to generate a labeled synthetic dataset. To further improve object detection, the network self-trains over real images that are labeled using a robust multi-view pose estimation process. The proposed training process is evaluated on several existing datasets and on a dataset collected for this paper with a Motoman robotic arm. Results show that the proposed approach outperforms popular training processes relying on synthetic - but not physically realistic - data and manual annotation. The key contributions are the incorporation of physical reasoning in the synthetic data generation process and the automation of the annotation process over real images.

ICRA Conference 2016 Conference Paper

Efficiently solving general rearrangement tasks: A fast extension primitive for an incremental sampling-based planner

Athanasios Krontiris
Kostas E. Bekris

Manipulating multiple movable obstacles is a hard problem that involves searching high-dimensional C-spaces. A milestone method for this problem was able to compute solutions for monotone instances. These are problems where every object needs to be transferred at most once to achieve a desired arrangement. The method uses backtracking search to find the order with which objects should be moved. This paper first proposes an approximate but significantly faster alternative for monotone rearrangement instances. The method defines a dependency graph between objects given minimum constraint removal paths (MCR) to transfer each object to its target. From this graph, the approach discovers the order of moving objects by performing topological sorting without backtracking search. The approximation arises from the limitation to consider only MCR paths, which minimize, however, the number of conflicts between objects. To solve non-monotone instances, this primitive is incorporated in a higher-level incremental search algorithm for general rearrangement planning, which operates similar to Bi-RRT. Given a start and a goal object arrangement, tree structures of reachable new arrangements are generated by using the primitive as an expansion procedure. The integrated solution achieves probabilistic completeness for the general non-monotone case and based on simulated experiments it achieves very good success ratios, solution times and path quality relative to alternatives.

SoCS Conference 2015 Conference Paper

Computational Tradeoffs of Search Methods for Minimum Constraint Removal Paths

Athanasios Krontiris
Kostas E. Bekris

The typical objective of path planning is to find the shortest feasible path. Many times, however, there may be no solution given the existence of constraints, such as obstacles. In these cases, the minimum constraint removal problem asks for the minimum set of constraints that need to be removed from the state space to find a solution. Unfortunately, minimum constraint removal paths do not exhibit dynamic programming properties, i. e. , subsets of optimum solutions are not necessarily optimal. Thus, searching for such solutions is computationally expensive. This leads to approximate methods, which balance the cost of computing a solution and its quality. This work investigates alternatives in this context and evaluates their performance in terms of such tradeoffs. Solutions that follow a bounded-length approach, i. e. , searching for paths up to a certain length, seem to provide a good balance between minimizing constraints, computational cost and path length.

SoCS Conference 2015 Conference Paper

Expected Path Degradation when Searching over a Sparse Grid Hierarchy

Robert Kolchmeyer
Andrew Dobson
Kostas E. Bekris

The traditional focus of combinatorial search research is to speed up the search algorithm. An alternative, however, is to create a sparser representation of the search space. This relates to the idea of spanners from graph theory. These are subgraphs which retain paths between any two vertices of the original graph while guaranteeing a maximum stretch in path length. In practice, the path degradation of graph spanners is significantly smaller than the theoretical bound. Even so, expected path degradation of graph spanners is typically not studied. This work focuses on grid path-finding to propose an algorithm that constructs a grid spanner, where analysis for the obstacle-free case shows that significant performance gains can be achieved with a small decrease in expected path quality. This is an important first step towards studying the expected performance of spanners. Experiments on game maps show that expected path quality with obstacles is only sometimes marginally lower than that in the obstacle-free case and that a significant reduction in the size of the search space can be achieved.

ICRA Conference 2015 Conference Paper

Geometric probability results for bounding path quality in sampling-based roadmaps after finite computation

Andrew Dobson
George V. Moustakides
Kostas E. Bekris

Sampling-based algorithms provide efficient solutions to high-dimensional, geometrically complex motion planning problems. For these methods asymptotic results are known in terms of completeness and optimality. Previous work by the authors argued that such methods also provide probabilistic near-optimality after finite computation time using indications from Monte Carlo experiments. This work formalizes these guarantees and provides a bound on the probability of finding a near-optimal solution with PRM* after a finite number of iterations. This bound is proven for general-dimension Euclidean spaces and evaluated through simulation. These results are leveraged to create automated stopping criteria for PRM* and sparser near-optimal roadmaps, which have reduced running time and storage requirements.

IROS Conference 2015 Conference Paper

Planning representations and algorithms for prehensile multi-arm manipulation

Andrew Dobson
Kostas E. Bekris

This paper describes the topology of general multi-arm prehensile manipulation. Reasonable assumptions are applied to reduce the number of manipulation modes, which results in an explicit graphical representation for multi-arm manipulation that is computationally manageable to store and search for solution paths. In this context, it is also possible to take advantage of preprocessing steps to significantly speed up online query resolution. The approach is evaluated in simulation for multiple arms showing it is possible to quickly compute multi-arm manipulation paths of high-quality on the fly.

SoCS Conference 2014 Conference Paper

Improved Heuristic Search for Sparse Motion Planning Data Structures

Andrew Dobson
Kostas E. Bekris

Sampling-based methods provide efficient, flexible solutions for motion planning, even for complex, high-dimensional systems. Asymptotically optimal planners ensure convergence to the optimal solution, but produce dense structures. This work shows how to extend sparse methods achieving asymptotic near-optimality using multiple-goal heuristic search during graph constuction. The resulting method produces identical output to the existing Incremental Roadmap Spanner approach but in an order of magnitude less time.

IROS Conference 2013 Conference Paper

A study on the finite-time near-optimality properties of sampling-based motion planners

Andrew Dobson
Kostas E. Bekris

Sampling-based algorithms have proven practical in solving motion planning challenges in relatively high-dimensional instances in geometrically complex workspaces. Early work focused on quickly returning feasible solutions. Only recently was it shown under which conditions these algorithms asymptotically return optimal or near-optimal solutions. These methods yield desired properties only in an asymptotic fashion, i. e. , the properties are attained after infinite computation time. This work studies the finite-time properties of sampling-based planners in terms of path quality. The focus is on roadmap-based methods, due to their simplicity. This work illustrates that existing sampling-based planners which construct roadmaps in an asymptotically (near-)optimal manner exhibit a “probably near-optimal” property in finite time. This means that it is possible to compute a confidence value, i. e. a probability, regarding the existence of upper bounds for the length of the path returned by the roadmap as a function of the number of configuration space samples. This property can result in useful tools for determining existence of solutions and a probabilistic stopping criterion for PRM-like methods. These properties are validated through experimental trials.

IROS Conference 2013 Conference Paper

Efficient sampling-based motion planning with asymptotic near-optimality guarantees for systems with dynamics

Zakary Littlefield
Yanbo Li
Kostas E. Bekris

Recent motion planners, such as RRT*, that achieve asymptotic optimality require a local planner, which connects two states with a trajectory. For systems with dynamics, the local planner corresponds to a two-point boundary value problem (BVP) solver, which is not always available. Furthermore, asymptotically optimal solutions tend to increase computational costs relative to alternatives, such as RRT, that focus on feasibility. This paper describes a sampling-based solution with the following desirable properties: a) it does not require a BVP solver but only uses a forward propagation model, b) it employs a single propagation per iteration similar to RRT, making it very efficient, c) it is asymptotically near-optimal, and d) provides a sparse data structure for answering path queries, which further improves computational performance. Simulations on prototypical dynamical systems show the method is able to improve the quality of feasible solutions over time and that it is computationally efficient.

SoCS Conference 2013 Conference Paper

From Feasibility Tests to Path Planners for Multi-Agent Pathfinding

Athanasios Krontiris
Ryan Luna
Kostas E. Bekris

Multi-agent pathfinding is an important challenge that relates to combinatorial search and has many applications, such as warehouse management, robotics and computer games. Finding an optimal solution is NP-hard and raises scalability issues for optimal solvers. Interestingly, however, it takes linear time to check the feasibility of an instance. These linear-time feasibility tests can be extended to provide path planners but to the best of the authors’ knowledge no such solver has been provided for general graphs. This work first describes a path planner that is inspired by a linear-time feasibility test for multi-agent pathfinding on general graphs. Initial experiments indicated reasonable scalability but worse path quality relative to existing suboptimal solutions. This led to the development of an algorithm that achieves both efficient running time and path quality relative to the alternatives and which finds a solution on available benchmarks. The paper outlines the relation of the final method to the feasibility tests and existing suboptimal planners. Experimental results evaluate the different algorithms, including an optimal solver.

ICRA Conference 2013 Conference Paper

Improving sparse roadmap spanners

Andrew Dobson
Kostas E. Bekris

Roadmap spanners provide a way to acquire sparse data structures that efficiently answer motion planning queries with probabilistic completeness and asymptotic near-optimality. The current SPARS method provides these properties by building two graphs in parallel: a dense asymptotically-optimal roadmap based on PRM* and its spanner. This paper shows that it is possible to relax the conditions under which a sample is added to the spanner and provide guarantees, while not requiring the use of a dense graph. A key aspect of SPARS is that the probability of adding nodes to the roadmap goes to zero as iterations increase, which is maintained in the proposed extension. The paper describes the new algorithm, argues its theoretical properties and evaluates it against PRM* and the original SPARS algorithm. The experimental results show that the memory requirements of the method upon construction are dramatically reduced, while returning competitive quality paths with PRM*. There is a small sacrifice in the size of the final spanner relative to SPARS but the new method still returns graphs orders of magnitudes smaller than PRM*, leading to very efficient online query resolution.

ICRA Conference 2012 Conference Paper

Integrated online localization and navigation for people with visual impairments using smart phones

Ilias Apostolopoulos
Navid Fallah
Eelke Folmer
Kostas E. Bekris

Indoor localization and navigation systems for individuals with visual impairments (VI) typically rely upon extensive augmentation of the physical space or heavy, expensive sensors; thus, few systems have been adopted. This work describes a system able to guide people with VI through buildings using inexpensive sensors, such as accelerometers, which are available in portable devices like smart phones. The method takes advantage of feedback from the human user, who confirms the presence of landmarks. The system calculates the user's location in real time and uses it to provide audio instructions on how to reach the desired destination. Previous work suggested that the accuracy of the approach depended on the type of directions and the availability of an appropriate transition model for the user. A critical parameter for the transition model is the user's step length. The current work investigates different schemes for automatically computing the user's step length and reducing the dependency of the approach to the definition of an accurate transition model. Furthermore, the direction provision method is able to use the localization estimate and adapt to failed executions of paths by the users. Experiments are presented that evaluate the accuracy of the overall integrated system, which is executed online on a smart phone. Both people with visual impairments, as well as blindfolded sighted people, participated in the experiments. The experiments included paths along multiple floors, that required the use of stairs and elevators.

SoCS Conference 2012 Conference Paper

Multi-Agent Pathfinding with Simultaneous Execution of Single-Agent Primitives

Qandeel Sajid
Ryan Luna
Kostas E. Bekris

Multi-agent pathfinding is a challenging combinatorial problem that involves multiple agents moving on a graph from a set of initial nodes to a set of desired goals without inter-agent collisions. Searching the composite space of all agents has exponential complexity and does not scale well. Decoupled methods are more efficient but are generally incomplete. There are, however, polynomial time algorithms, which utilize single or few-agents primitives with completeness guarantees. One limitation of these alternatives is that the resulting solution is sequential, where only one agent moves at a time. Such solutions are of low quality when compared to methods where multiple agents can move simultaneously. This work proposes an algorithm for multi-agent pathfinding that utilizes similar single-agent primitives but allows all agents to move in parallel. The paper describes the algorithm and its properties. Experimental comparisons suggest that the resulting paths are considerably better than sequential ones, even after a post-processing, parallelization step, as well as solutions returned by decoupled and coupled alternatives. The experiments also suggest good scalability and competitive computational performance.

ICRA Conference 2012 Conference Paper

Multi-level formation roadmaps for collision-free dynamic shape changes with non-holonomic teams

Athanasios Krontiris
Sushil J. Louis
Kostas E. Bekris

Teams of robots can utilize formations to accomplish a task, such as maximizing the observability of an environment while maintaining connectivity. In a cluttered space, however, it might be necessary to automatically change formation to avoid obstacles. This work proposes a path planning approach for non-holonomic robots, where a team dynamically switches formations to reach a goal without collisions. The method introduces a multi-level graph, which can be constructed offline. Each level corresponds to a different formation and edges between levels allow for formation transitions. All edges satisfy curvature bounds and clearance requirements from obstacles. During the online phase, the method returns a path for a virtual leader, as well as the points along the path where the team should switch formations. Individual agents can compute their controls using kinematic formation controllers that operate in curvilinear coordinates. The approach guarantees that it is feasible for the agents to follow the trajectory returned. Simulations show that the online cost of the approach is small. The method returns solutions that maximize the maintenance of a desired formation while allowing the team to rearrange its configuration in the presence of obstacles.

ICRA Conference 2012 Conference Paper

Towards small asymptotically near-optimal roadmaps

James D. Marble
Kostas E. Bekris

An exciting recent development is the definition of sampling-based motion planners which guarantee asymptotic optimality. Nevertheless, roadmaps with this property may grow too large and lead to longer query resolution times. If optimality requirements are relaxed, existing asymptotically near-optimal solutions produce sparser graphs by removing redundant edges. Even these alternatives, however, include all sampled configurations as nodes in the roadmap. This work proposes a method, which can reject redundant samples but does provide asymptotic coverage and connectivity guarantees, while keeping local path costs low. Not adding every sample can significantly reduce the size of the final roadmap. An additional advantage is that it is possible to define a reasonable stopping criterion for the approach inspired by previous methods. To achieve these objectives, the proposed method maintains a dense graph that is used for evaluating the performance of the roadmap with regards to local path costs. Experimental results show that the method indeed provides small roadmaps, allowing for shorter query resolution times. Furthermore, smoothing the final paths results in an even more advantageous comparison against alternatives with regards to path quality.

ICRA Conference 2012 Conference Paper

Visual and force-feedback guidance for robot-assisted interventions in the beating heart with real-time MRI

Nikhil V. Navkar
Zhigang Deng 0001
Dipan J. Shah
Kostas E. Bekris
Nikolaos V. Tsekos

Robot-assisted surgical procedures are perpetually evolving due to potential improvement in patient treatment and healthcare cost reduction. Integration of an imaging modality intraoperatively further strengthens these procedures by incorporating the information pertaining to the area of intervention. Such information needs to be effectively rendered to the operator as a human-in-the-loop requirement. In this work, we propose a guidance approach that uses real-time MRI to assist the operator in performing robot-assisted procedure in a beating heart. Specifically, this approach provides both real-time visualization and force-feedback based guidance for maneuvering an interventional tool safely inside the dynamic environment of a heart's left ventricle. Experimental evaluation of the functionality of this approach was tested on a simulated scenario of transapical aortic valve replacement and it demonstrated improvement in control and manipulation by providing effective and accurate assistance to the operator in real-time.

IROS Conference 2011 Conference Paper

Computing spanners of asymptotically optimal probabilistic roadmaps

James D. Marble
Kostas E. Bekris

Asymptotically optimal motion planning algorithms guarantee solutions that approach optimal as more iterations are performed. Nevertheless, roadmaps with this property can grow too large and unwieldy for fast online query resolution. In graph theory there are many algorithms that produce subgraphs, known as spanners, which have guarantees about path quality. Applying such an algorithm to a dense, asymptotically optimal roadmap produces a sparse, asymptotically near optimal roadmap. Experiments performed on typical, geometric problems in SE(3) show that a large reduction in roadmap edges can be achieved with a small increase in path length. Online queries are answered much more quickly with similar results in terms of path quality. This also motivates future work that applies the technique incrementally so edges that won't increase path quality will never be added to the roadmap and won't be checked for collisions.

IROS Conference 2011 Conference Paper

Efficient and complete centralized multi-robot path planning

Ryan Luna
Kostas E. Bekris

Multi-robot path planning is abstracted as the problem of computing a set of non-colliding paths on a graph for multiple robots. A naive search of the composite search space, although complete, has exponential complexity and becomes computationally prohibitive for problems with just a few robots. This paper proposes an efficient and complete algorithm for solving a general class of multi-robot path planning problems, specifically those where there are at most n-2 robots in a connected graph of n vertices. This paper provides a full proof of completeness. The algorithm employs two primitives: “push”, where a robot moves toward its goal until no progress can be made, and “swap”, that allows two robots to swap positions without altering the position of any other robot. Additionally, this paper provides a smoothing procedure for improving solution quality. Simulated experiments compare the proposed approach with several other centralized and decoupled planners, and show that the proposed technique improves computation time and solution quality, while scaling to problems with 100s of robots, solving them in under 5 seconds.

SoCS Conference 2011 Conference Paper

Efficient and Complete Centralized Multi-Robot Path Planning

Ryan Luna
Kostas E. Bekris

Multi-robot path planning is abstracted as the problem of computing a set of non-colliding paths on a graph for multiple robots. A naive search of the composite search space, although complete, has exponential complexity and becomes computationally prohibitive for problems with just a few robots. This work proposes an efficient and complete algorithm for solving a general class of multi-robot path planning problems, specifically those where there are at most n-2 robots in a connected graph of n vertices. The algorithm employs two primitives: a "push" operation where a robot moves toward its goal until no further progress can be made, and a "swap" operation that allows two robots to swap positions without altering the configuration of any other robot. Simulated experiments compare the proposed approach with several other centralized and decoupled planners, and show that the proposed technique has highly competitive computation time and easily scales to problems involving 100s of robots, solving them in under 5 seconds.

ICRA Conference 2011 Conference Paper

General dynamic formations for non-holonomic systems along planar curvilinear coordinates

Athanasios Krontiris
Sushil J. Louis
Kostas E. Bekris

This paper describes a general geometric method for planar formations of non-holonomic systems. The approach directly provides the feasible controls that each individual robot has to execute in order for the team to maintain the formation based on the controls of a reference agent, either a real leader-robot or a virtual one. In order to directly satisfy the non-holonomic constraints, the geometric reasoning takes place in curvilinear coordinates, defined by the curvature of the reference trajectory, instead of the typical rectilinear coordinates. The generality of the approach lies on the ability to define dynamic formations so as to smoothly switch between static ones, where the robots can change both of their relative coordinates as they move, and the ability to acquire a desired formation given an initial random configuration. Furthermore, it is possible to correct errors in the achieved configuration of the vehicles on the fly. Simulated experiments are presented to verify the correctness of the provided derivations.

ICRA Conference 2011 Conference Paper

Learning approximate cost-to-go metrics to improve sampling-based motion planning

Yanbo Li
Kostas E. Bekris

Sampling-based planners have been shown to be effective in searching unexplored parts of a system's state space. Their desirable properties, however, depend on the availability of an appropriate metric, which is often difficult to be defined for some robots, such as non-holonomic and under-actuated ones. This paper investigates a methodology to approximate optimum cost-to-go metrics by employing an offline learning phase in an obstacle-free workspace. The proposed method densely samples a graph that approximates the connectivity properties of the state space. This graph can be used online to compute approximate distances between states using nearest neighbor queries and standard graph search algorithms, such as A*. Unfortunately, this process significantly increases the online cost of a sampling-based planner. This work then investigates ways for the computationally efficient utilization of the learned metric during the planner's online operation. One idea is to map the sampled states into a higher-dimensional Euclidean space through multi-dimensional scaling that retains the relative distances represented by the sampled graph. Simulations on a first-order car and on an illustrative example of an asymmetric state space indicate that the approach has merit and can lead into more effective planning.

IJCAI Conference 2011 Conference Paper

Push and Swap: Fast Cooperative Path-Finding with Completeness Guarantees

Ryan Luna
Kostas E. Bekris

Cooperative path-finding can be abstracted as computing non-colliding paths for multiple agents between their start and goal locations on a graph. This paper proposes a fast algorithm that can provide completeness guarantees for a general class of problems without any assumptions about the graph's topology. Specifically, the approach can address any solvable instance where there are at most n-2 agents in a graph of size n. The algorithm employs two primitives: a "push" operation where agents move towards their goals up to the point that no progress can be made, and a "swap" operation that allows two agents to swap positions without altering the configuration of other agents. Simulated experiments are provided on hard instances of cooperative path-finding, including comparisons against alternative methods. The results are favorable for the proposed algorithm and show that the technique scales to problems that require high levels of coordination, involving hundreds of agents.

PDF Details DOI

IROS Conference 2011 Conference Paper

Using minimal communication to improve decentralized conflict resolution for non-holonomic vehicles

Athanasios Krontiris
Kostas E. Bekris

This work considers the problem of decentralized coordination between multiple non-holonomic vehicles, each navigating to a specified goal. By augmenting the Generalized Roundabout Policy (GRP), which guarantees collision avoidance, this paper improves the performance and liveness characteristics for such problems. These gains are achieved by integrating a second hybrid policy with GRP that updates the desired direction for each vehicle based on a dynamic priority scheme. In this scheme, minimalistic communication between vehicles is employed, such that information is periodically exchanged when changes in the high-level operating mode or prioritization occur. This information exchange is taking place only locally and data are exchanged only between neighboring vehicles. Additionally, each agent selects a control using only this local information and rules established by the two underlying hybrid automata. The proposed technique scales well due to its decentralized nature and as the computational complexity depends on the maximum number of vehicles in communication range for a vehicle. This paper presents simulations which show that the proposed approach can solve problems faster than using GRP alone, as well as solve instances in which GRP fails to find a solution, with minimal communication and computational overhead.

ICRA Conference 2010 Conference Paper

Balancing state-space coverage in planning with dynamics

Yanbo Li
Kostas E. Bekris

Sampling-based kinodynamic planners, such as the popular RRT algorithm, have been proposed as promising solutions to planning for systems with dynamics. Nevertheless, complex systems often raise significant challenges. In particular, the state-space exploration of sampling-based tree planners can be heavily biased towards a specific direction due to the presence of dynamics and underactuation. The premise of this paper is that it is possible to use statistical tools to learn quickly the effects of the constraints in the algorithm's state-space exploration during a training session. Then during the online operation of the algorithm, this information can be utilized so as to counter the undesirable bias due to the dynamics by appropriately adapting the control propagation step. The resulting method achieves a more balanced exploration of the state-space, resulting in faster solutions to planning challenges. The paper provides proof of concept experiments comparing against and improving upon the standard RRT using MATLAB simulations for (a) swinging up different versions of a 3-link Acrobot system with dynamics and (b) a second-order car-like system with significant drift.

IROS Conference 2010 Conference Paper

Network-guided multi-robot path planning in discrete representations

Ryan Luna
Kostas E. Bekris

This work deals with problems where multiple robots move on a roadmap guided by wireless nodes that form a communication network. The nodes compute paths for the robots within their communication range given information about robots only in their vicinity and communicating only with neighbors. The objective is to compute paths that are collision-free, minimize the occurrence of deadlocks, as well as the time it takes to reach the robots' goals. This paper formulates this challenge as a distributed constraint optimization problem. This formulation lends itself to a message-passing solution that guarantees collision-avoidance despite only local knowledge of the world by the network nodes. Simulations on benchmarks that cannot be solved with coupled or simple decoupled schemes are used to evaluate parameters and study the scalability, path quality and computational overhead of the approach.

IROS Conference 2007 Conference Paper

A decentralized planner that guarantees the safety of communicating vehicles with complex dynamics that replan online

Kostas E. Bekris
Konstantinos I. Tsianos
Lydia E. Kavraki

This paper considers the problem of coordinating multiple vehicles with kinodynamic constraints that operate in the same partially-known environment. The vehicles are able to communicate within limited range. Their objective is to avoid collisions between them and with the obstacles, while the vehicles move towards their goals. An important issue of real-time planning for systems with bounded acceleration is that inevitable collision states must also be avoided. The focus of this paper is to guarantee safety despite the dynamic constraints with a decentralized motion planning technique that employs only local information. We propose a coordination framework that allows vehicles to generate and select compatible sets of valid trajectories and prove that this scheme guarantees collision-avoidance in the specified setup. The theoretical results have been also experimentally confirmed with a distributed simulator where each vehicle replans online with a sampling- based, kinodynamic motion planner and uses message-passing to communicate with neighboring agents.

ICRA Conference 2007 Conference Paper

Greedy but Safe Replanning under Kinodynamic Constraints

Kostas E. Bekris
Lydia E. Kavraki

We consider motion planning problems for a vehicle with kinodynamic constraints, where there is partial knowledge about the environment and replanning is required. We present a new tree-based planner that explicitly deals with kinodynamic constraints and addresses the safety issues when planning under finite computation times, meaning that the vehicle avoids collisions in its evolving configuration space. In order to achieve good performance we incrementally update a tree data-structure by retaining information from previous steps and we bias the search of the planner with a greedy, yet probabilistically complete state space exploration strategy. Moreover, the number of collision checks required to guarantee safety is kept to a minimum. We compare our technique with alternative approaches as a standalone planner and show that it achieves favorable performance when planning with dynamics. We have applied the planner to solve a challenging replanning problem involving the mapping of an unknown workspace with a nonholonomic platform

ICRA Conference 2007 Conference Paper

OOPS for Motion Planning: An Online, Open-source, Programming System

Erion Plaku
Kostas E. Bekris
Lydia E. Kavraki

The success of sampling-based motion planners has resulted in a plethora of methods for improving planning components, such as sampling and connection strategies, local planners and collision checking primitives. Although this rapid progress indicates the importance of the motion planning problem and the maturity of the field, it also makes the evaluation of new methods time consuming. We propose that a systems approach is needed for the development and the experimental validation of new motion planners and/or components in existing motion planners. In this paper, we present the online, open-source, programming system for motion planning (OOPS MP ), a programming infrastructure that provides implementations of various existing algorithms in a modular, object-oriented fashion that is easily extendible. The system is open-source, since a community-based effort better facilitates the development of a common infrastructure and is less prone to errors. We hope that researchers will contribute their optimized implementations of their methods and thus improve the quality of the code available for use. A dynamic Web interface and a dynamic linking architecture at the programming level allows users to easily add new planning components, algorithms, benchmarks, and experiment with different parameters. The system allows the direct comparison of new contributions with existing approaches on the same hardware and programming infrastructure

ICRA Conference 2006 Conference Paper

Evaluation of Algorithms for bearing-only SLAM

Kostas E. Bekris
Max Glick
Lydia E. Kavraki

An important milestone for building affordable robots that can become widely popular is to address robustly the simultaneous localization and mapping (SLAM) problem with inexpensive, off-the-shelf sensors, such as monocular cameras. These sensors, however, impose significant challenges on SLAM procedures because they provide only bearing data related to environmental landmarks. This paper starts by providing an extensive comparison of different techniques for bearing-only SLAM in terms of robustness under different noise models, landmark densities and robot paths. We have experimented in a simulated environment with a variety of existing online algorithms including Rao-Blackwellized particle filters (RB-PFs). Our experiments suggest that RB-PFs are more robust compared to other existing methods and run considerably faster. Nevertheless, their performance suffers in the presence of outliers. In order to overcome this limitation we proceed to propose an augmentation of RB-PFs with: (a) Gaussian sum filters for landmark initialization and (b) an online, unsupervised outlier rejection policy. This framework exhibits impressive robustness and efficiency even in the presence of outliers

ICRA Conference 2004 Conference Paper

Angle-based Methods for Mobile Robot Navigation: Reaching the Entire Plane

Kostas E. Bekris
Antonis A. Argyros
Lydia E. Kavraki

Popular approaches for mobile robot navigation involve range information and metric maps of the workspace. For many sensors, however, such as cameras and wireless hardware, the angle between two features or beacons is easier to measure. With these sensors' features in mind, we initially present a control law, which allows a robot with an omni-directional sensor to reach a subset of the plane by monitoring the angles of only three landmarks. By analyzing the law's properties, a second law has been developed that reaches the complementary set of points. The two methods are then combined in a path planning framework that reaches any possible goal configuration in a planar obstacle-free workspace with three landmarks. The proposed framework could be used together with other techniques, such as obstacle avoidance and topological maps to improve the efficiency of autonomous navigation. Experiments have been conducted on a robotic platform using a panoramic camera that exhibits the effectiveness and accuracy of the proposed techniques. This work provides evidence that navigational tasks can be performed using only a small number of primitive sensor cues and without the explicit computation of range information.

IROS Conference 2003 Conference Paper

Multiple query probabilistic roadmap planning using single query planning primitives

Kostas E. Bekris
Brian Y. Chen
Andrew M. Ladd
Erion Plaku
Lydia E. Kavraki

We propose a combination of techniques that solve multiple queries for motion planning problems with single query planners. Our implementation uses a probabilistic roadmap method (PRM) with bidirectional rapidly exploring random trees (BI-RRT) as the local planner. With small modifications to the standard algorithms, we obtain a multiple query planner, which is significantly faster and more reliable than its component parts. Our method provides a smooth spectrum between the PRM and BI-RRT techniques and obtains the advantages of both. We observed that the performance differences are most notable in planning instances with several rigid nonconvex robots in a scene with narrow passages. Our work is in the spirit of non-uniform sampling and refinement techniques used in earlier work on PRM.

IROS Conference 2002 Conference Paper

Using wireless Ethernet for localization

Andrew M. Ladd
Kostas E. Bekris
Guillaume Marceau
Algis Rudys
Dan S. Wallach
Lydia E. Kavraki

IEEE 802. 11b wireless Ethernet is rapidly becoming the standard for in-building and short-range wireless communication. Many mobile devices such as mobile robots, laptops and PDAs already use this protocol for wireless communication. Many wireless Ethernet cards measure the signal strength of incoming packets. This paper investigates the feasibility of implementing a localization system using this sensor. Using a Bayesian localization framework, we show experiments demonstrating that off-the-shelf wireless hardware can accurately be used for location sensing and tracking with about one meter precision in a wireless-enabled office building.