Author name cluster

Jyh-Ming Lien

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

22 papers

1 author row

IROS Conference 2022 Conference Paper

Learning to Herd Amongst Obstacles from an Optimized Surrogate

Jixuan Zhi
Jyh-Ming Lien

This paper investigates how a shepherd robot can efficiently steer a coherent group by intelligently moving behind the group in obstacle-filled environments. It was been shown that a model trained by deep reinforcement learning can guide a small number (2–4) of agents among obstacles. However, herding a larger group becomes significantly more challenging because it exhibits the characteristics similar to manipulating a deformable object, i. e. , the system is dynamic and the problem is highly underactuated. To overcome these challenges, we show that a model can be trained more effectively via an optimized surrogate, such as a potential field that optimizes the control quality of the group without explicitly considering the placement of the shepherd. Our experiments demonstrate that the trained model is robust to noise for group behaviors and environments. Compared to the rule-based method, the proposed approach maintains a higher probability of guiding the sheep and better control quality.

ICRA Conference 2021 Conference Paper

Planning Laser-Forming Folding Motion with Thermal Simulation

Yue Hao 0003
Weilin Guan
Edwin Alexander Peraza Hernandez
Jyh-Ming Lien

Designing a robot or structure that can fold into a target shape is a process that involves challenges originated from multiple sources. For example, the designer of self-folding robots must consider foldability from geometric and kinematic aspects to avoid self-collisions and undesired deformations. Recent works have shown success in estimating foldability of a design using robot motion planners. However, many foldable structures are actuated using physically coupled reactions, e. g. , folding originated from thermal, chemical, or electromagnetic loads. Therefore, a reliable folding process must consider additional constraints that result from these critical and coupled phenomena. This work investigates the idea of efficiently incorporating computationally intensive physics simulations within the folding motion planner to affect the physical folding results. We will use the manufacturing process of laser-forming origami as an example to demonstrate the benefits of considering the physical properties of the foldable structure beyond its kinematics. We show that designs produced by the proposed method can be fabricated more efficiently.

IROS Conference 2015 Conference Paper

Continuous unfolding of polyhedra - a motion planning approach

Zhonghua Xi
Jyh-Ming Lien

Cut along the surface of a polyhedron and unfold it to a planar structure without overlapping is known as Unfolding Polyhedra problem which has been extensively studied in the mathematics literature for centuries. However, whether there exists a continuous unfolding motion such that the polyhedron can be continuously transformed to its unfolding has not been well studied. Recently, researchers started to recognize continuous unfolding as a key step in designing and implementation of self-folding robots. In this paper, we model the unfolding of a polyhedron as multi-link tree-structure articulated robot, and address this problem using motion planning techniques. Instead of sampling in continuous domain which traditional motion planners do, we propose to sample only in the discrete domain. Our experimental results show that sampling in discrete domain is efficient and effective for finding feasible unfolding paths.

IROS Conference 2015 Conference Paper

Fast medial-axis approximation via Max-Margin pushing

Guilin Liu
Jyh-Ming Lien

Maintaining clearance, or distance from obstacles and sampling efficient enough configurations on the medial axises are a vital component for successful motion planning. Maintaining high clearance often creates safer paths for robots. Having bias for sampling on medial axis also offers higher possibility to find a path in complex environment where the feasible configuration space only occupies a small proportion of the whole space. Inspired by the similarity between medial axis and max-margin scheme in optimization, especially in Support Vector Machine, we propose a new method to quickly construct the medial axis for the motion planning environment both in low and high dimensional space. However, directly applying the SVM classification on the large volume of uniformly sampled configurations suffers from huge computation and the medial axis is usually not the real medial axis due to SVM's optimization function's tolerance to the mis-classification. Instead, we show a method that can quickly push any configuration to the medial axis by using the characteristics of the Max-Margin's optimization function. Experiments in low and high dimensional space and comparisons with other medial-axis motion planning algorithm are shown.

ICRA Conference 2015 Conference Paper

Folding and unfolding origami tessellation by reusing folding path

Zhonghua Xi
Jyh-Ming Lien

Recent advances in robotics engineering have enabled the realization of self-folding machines. Rigid origami is usually used as the underlying model for the self-folding machines whose surface remains rigid during folding except at joints. A key issue in designing rigid origami is foldability that concerns about finding folding steps from a flat sheet of crease pattern to a desired folded state. Although recent computational methods allow rapid simulation of folding process of certain rigid origamis, these methods can fail even when the input crease pattern is extremely simple. In this paper, we take on the challenge of planning folding and unfolding motion of origami tessellations, which are composed of repetitive crease patterns. The number of crease lines of a tessellation is usually large, thus searching in such a high dimensional configuration space with the requirement of maintaining rigidity is nontrivial. We propose a motion planner that takes symmetry into consideration and reuses folding path found on the essential crease pattern. Both of these strategies enable us to fold large origami tessellation much more efficiently than existing methods. Our experimental results show that the proposed method successfully folds several types of rigid origami tessellations that existing methods fail to fold.

ICRA Conference 2015 Conference Paper

Plan folding motion for rigid self-folding machine via discrete domain sampling

Zhonghua Xi
Jyh-Ming Lien

Self-folding robot is usually modeled as rigid origami, a class of origami whose entire surface remains rigid during folding except at crease lines. In this work, we focus on finding valid folding motion that brings the origami from the unfolded state continuously to the folded state. Although recent computational methods allow rapid simulation of folding process of certain rigid origami, these methods can fail even when the input crease pattern is extremely simple but requires implicit folding orders. Moreover, due to the rigidity requirement, the probability of generating a valid configuration via uniform sampling is zero, which greatly hinders the applicability of traditional sampling-based motion planners. We propose a novel sampling strategy that samples in the discrete domain. Our experimental results show that the proposed method could efficiently generate valid configurations. Using those configurations, the planner successfully folds several types of rigid origami that the existing methods fail to fold and could discover multiple folding paths in different homotopies.

ICRA Conference 2015 Conference Paper

Semantically guided location recognition for outdoors scenes

Arsalan Mousavian
Jana Kosecka
Jyh-Ming Lien

The problem of image based localization has a long history both in robotics and computer vision and shares many similarities with image based retrieval problem. Existing techniques use either local features or (semi)-global image signatures in the context of topological mapping or loop closure detection. Difficulties of the location recognition problem are often affected by large appearance and viewpoint variation between the query view and reference dataset and presence of non-discriminative features due to vegetation, sky and road. In this work we show that semantic segmentation labeling of man-made structures can inform the traditional bag-of-visual words models to obtain proper feature weighting and improve the overall location recognition accuracy. We also demonstrate additional capability of identifying individual buildings and estimating their extent in images, providing the essential building block for semantic localization. Towards this end we introduce a new challenging outdoors urban dataset exhibiting large variations in appearance and viewpoint.

IROS Conference 2014 Conference Paper

Collision prediction among polygons with arbitrary shape and unknown motion

Yanyan Lu
Zhonghua Xi
Jyh-Ming Lien

Collision prediction is a fundamental operation for planning motion in dynamic environment. Existing methods usually exploit complex behavior models or use dynamic constraints in collision prediction. However, these methods all assume simple geometries, such as disc, which significantly limit their applicability. This paper proposes a new approach that advances collision prediction beyond disc robots and handles arbitrary polygons. Our new tool predicts collision by assuming that obstacles are adversarial. Comparing to an online motion planner that replans periodically at fixed time interval and planner that approximates obstacle with discs, our experimental results provide strong evidences that the new method significantly reduces the number of replans while maintaining higher success rate of finding a valid path. Our geometric-based collision prediction method provides a tool to handle highly complex shapes and provides a complimentary approach to those methods that consider behavior and dynamic constraints of objects with simple shapes.

IROS Conference 2013 Conference Paper

Mapping the configuration space of polygons using reduced convolution

Evan Behar
Jyh-Ming Lien

Configuration space (C-space) plays an important role not only in motion planning but also in geometric modeling, shape and kinematic reasoning, and is fundamental to several basic geometric operations, such as continuous collision detection and generalized penetration depth estimation, that also find their applications in motion planning, animation and simulation. In this paper, we developed a new method for constructing the boundary of the C-space obstacles (C-obst) of polygons. This method is simpler to implement and is theoretically more efficient than the existing techniques. Our main idea is to devote the computation on the discontinuity in temporal and spatial coherence where the structure of the C-obst changes. We also developed a method for estimating the generalized penetration depth by computing the distance between the query point and the C-obst surface.

ICRA Conference 2011 Conference Paper

Dynamic Minkowski sum of convex shapes

Evan Behar
Jyh-Ming Lien

Computing the Minkowski sums of rotating ob jects has always been done naively by re-computing every Minkowski sum from scratch. The correspondences between the Minkowski sums are typically completely ignored. We propose a method, called DYMSUM, that can efficiently update the Minkowski sums of rotating convex polyhedra. We show that DYMSUM is significantly more efficient than the traditional approach, in particular when the size of the input polyhedra are large and when the rotation is small between frames. From our experimental results, we show that the computation time of the proposed method grows slowly with respect to the size of the input comparing to the naive approach.

IROS Conference 2011 Conference Paper

Fast and robust 2D minkowski sum using reduced convolution

Evan Behar
Jyh-Ming Lien

We propose a new method for computing the 2-d Minkowski sum of non-convex polygons. Our method is convolution based. The main idea is to use the reduced convolution and filter the boundary by using the topological properties of the Minkowski sum. The main benefit of this proposed approach is from the fact that, in most cases, the complexity of the complete convolution is much higher than the complexity of the final Minkowski sum boundary. Therefore, the traditional approach often wastes a large portion of the computation on computing the arrangement induced by the complete convolution that is later on thrown away. Our method is designed to specifically avoid this waste of computation. We experimentally demonstrate that the proposed method is more efficient than the existing methods.

IROS Conference 2011 Conference Paper

Finding critical changes in dynamic configuration spaces

Yanyan Lu
Jyh-Ming Lien

Given a motion planning problem in a dynamic but fully known environment, we propose the first roadmap-based method, called critical roadmap, that has the ability to identify and exploit the critical topological changes of the free configuration space. Comparing to the existing methods that either ignore temporal coherence or only repair their roadmaps at fixed times, our method provides not only a more complete representation of the free (configuration-time) space but also provides significant efficiency improvement. Our experimental results show that the critical roadmap method has a higher chance of finding solutions, and it is at least one order of magnitude faster than some well-known planners.

IROS Conference 2009 Conference Paper

Behavior-based motion planning for group control

Christopher Vo
Joseph F. Harrison
Jyh-Ming Lien

Despite the large body of work in both motion planning and multi-agent simulation, little work has focused on the problem of planning motion for groups of robots using external ¿controller¿ agents. We call this problem the group control problem. This problem is complex because it is highly underactuated, dynamic, and requires multi-agent cooperation. In this paper, we present a variety of new motion planning algorithms based on EST, RRT, and PRM methods for shepherds to guide flocks of robots through obstacle-filled environments. We show using simulation on several environments that under certain circumstances, motion planning can find paths that are too complicated for nai¿ve ¿simulation only¿ approaches. However, inconsistent results indicate that this problem is still in need of additional study.

IROS Conference 2009 Conference Paper

Planning motion in point-represented contact spaces using approximate star-shaped decomposition

Jyh-Ming Lien
Yanyan Lu

Star-shaped decomposition partitions a shape into a set of star-shaped components. A shape is star shaped if and only if there exists at least one point which can see all the points in the shape. Due to this interesting property, decomposing a configuration space into star-shaped components can be beneficial, e. g. , for solving motion planning problem. In this paper, we propose a simple method to decompose the contact space, represented by point set data, into approximate star-shaped components. We propose two motion planning methods, one deterministic and one probabilistic, both based on this idea.

IROS Conference 2007 Conference Paper

A framework for planning motion in environments with moving obstacles

Samuel Rodríguez
Jyh-Ming Lien
Nancy M. Amato

In this paper we present a heuristic approach to planning in an environment with moving obstacles. Our approach assumes that the robot has no knowledge of the future trajectory of the moving objects. Our framework also distinguishes between two types of moving objects in the environment: hard and soft objects. We distinguish between the two types of objects in the environment as varying application domains could allow for some collision between some types of moving objects. For example, a robot planning a path in an environment with people could have the people modeled as circular disks with a safe zone surrounding each person. Although the robot may try to stay out of each safe zone, violating that criteria would not necessarily result in planning failure. We will show the effectiveness of our planner in general dynamic environments with the soft objects having varying behaviors.

ICRA Conference 2006 Conference Paper

An Obstacle-based Rapidly-exploring Random Tree

Samuel Rodríguez
Xinyu Tang 0002
Jyh-Ming Lien
Nancy M. Amato

Tree-based path planners have been shown to be well suited to solve various high dimensional motion planning problems. Here we present a variant of the Rapidly-Exploring Random Tree (RRT) path planning algorithm that is able to explore narrow passages or difficult areas more effectively. We show that both workspace obstacle information and C-space information can be used when deciding which direction to grow. The method includes many ways to grow the tree, some taking into account the obstacles in the environment. This planner works best in difficult areas when planning for free flying rigid or articulated robots. Indeed, whereas the standard RRT can face difficulties planning in a narrow passage, the tree based planner presented here works best in these areas

ICRA Conference 2006 Conference Paper

Planning Motion in Completely Deformable Environments

Samuel Rodríguez
Jyh-Ming Lien
Nancy M. Amato

Though motion planning has been studied extensively for rigid and articulated robots, motion planning for deformable objects is an area that has received far less attention. In this paper we present a framework for planning paths in completely deformable, elastic environments. We apply a deformable model to the robot and obstacles in the environment and present a kinodynamic planning algorithm suited for this type of deformable motion planning. The planning algorithm is based on the rapidly-exploring random tree (RRT) path planning algorithm. To the best of our knowledge, this is the first work that plans paths in totally deformable environments

ICRA Conference 2006 Conference Paper

VIZMO++: a Visualization, Authoring, and Educational Tool for Motion Planning

Aimée Vargas Estrada
Jyh-Ming Lien
Nancy M. Amato

Comprehension of concepts and algorithms involved in the robotics field can be improved through the use of an interactive visualization tool. In this paper we present an interactive tool for visualizing and editing motion planning environments, problem instances, and their solutions. Teachers can take advantage of visualization tools to help their students to better understand motion planning and its complexity as well as the different strategies that have been developed to solve the motion planning problem. While the tool we present allows the animation, manipulation, and evaluation of solution paths found by any motion planner, it is specialized for sampling-based randomized planners such as probabilistic roadmap (PRM) and rapidly-exploring random tree (RRT) methods

ICRA Conference 2005 Conference Paper

Shepherding Behaviors with Multiple Shepherds

Jyh-Ming Lien
Samuel Rodríguez
Jean-Phillipe Malric
Nancy M. Amato

Shepherding behaviors are a type of group be haviors in which one group (the shepherds) tries to control the motion of another group (the flock). Shepherding behaviors can be found in many forms in nature and have various important robotic applications. In this paper we extend our previous work of shepherding behaviors with a single shepherd to multiple shepherds. More specifically, we study how a group of shepherds can work cooperatively without communication to efficiently control the flock.

ICRA Conference 2004 Conference Paper

Shepherding Behaviors

Jyh-Ming Lien
O. Burçhan Bayazit
Ross T. Sowell
Samuel Rodríguez
Nancy M. Amato

Shepherding behaviors are a type of flocking behavior in which outside agents guide or control members of a flock. Shepherding behaviors can be found in various forms in nature. For example, herding, covering, patrolling and collecting are common types of shepherding behaviors. In this work, we investigate ways to simulate these types of behaviors. A shepherd uses roadmaps to steer the flock and to re-group separated flock members. This paper focuses on improving the shepherd's movements to gain better control of the flock's motion and use this improved control to demonstrate a wider variety of shepherding behaviors.

ICRA Conference 2003 Conference Paper

A general framework for sampling on the medial axis of the free space

Jyh-Ming Lien
Shawna L. Thomas
Nancy M. Amato

We propose a general framework for sampling the configuration space in which randomly generated configurations, free or not, are retracted onto the medial axis of the free space. Generalizing our previous work, this framework provides a template encompassing all possible retraction approaches. It also removes the requirement of exactly computing distance metrics thereby enabling application to more realistic high dimensional problems. In particular, our framework supports methods that retract a given configuration exactly or approximately onto the medial axis. As in our previous work, exact methods provide fast and accurate retraction in low (2 or 3) dimensional space. We also propose new approximate methods that can be applied to high dimensional problems, such as many DOF articulated robots. Theoretical and experimental results show improved performance on problems requiring traversal of narrow passages. We also study tradeoffs between accuracy and efficiency for different levels of approximation, and how the level of approximation effects the quality of the resulting roadmap.

ICRA Conference 2002 Conference Paper

Probabilistic Roadmap Motion Planning for Deformable Objects

O. Burçhan Bayazit
Jyh-Ming Lien
Nancy M. Amato

In this paper, we investigate methods for motion planning for deformable robots. Our framework is based on a probabilistic roadmap planner. As with traditional motion planning, the planner's goal is to find a valid path for the robot. Unlike typical motion planning, the robot is allowed to change its shape (deform) to avoid collisions as it moves along the path. We propose a two-stage approach. First, an 'approximate' path which may contain collisions is found. Next, we attempt to correct any collisions on this path by deforming the robot. We propose and analyze two methods for performing the deformations. Both techniques are inspired by a physically correct behavior, but are more efficient than completely, physically correct methods. Our approach can be applied in several domains, including flexible robots, computer modeling and animation, and biological simulations.