Autonomous navigation requires robots to generate trajectories for collision avoidance efficiently. Although plenty of previous works have proven successful in generating smooth and spatially collision-free trajectories, their solutions often suffer from suboptimal time efficiency and potential un-safety, particularly when accounting for uncertainties in robot perception and control. To address this issue, this paper presents the Robust Optimal Time Allocation (ROTA) framework. This framework is designed to optimize the time progress of the trajectories temporally, serving as a post-processing tool to enhance trajectory time efficiency and safety under uncertainties. In this study, we begin by formulating a non-convex optimization problem aimed at minimizing trajectory execution time while incorporating constraints on collision probability as the robot approaches obstacles. Subsequently, we introduce the concept of the trajectory braking zone and adopt the chance-constrained formulation for robust collision avoidance in the braking zones. Finally, the non-convex optimization problem is reformulated into a second-order cone programming problem to achieve real-time performance. Through simulations and physical flight experiments, we demonstrate that the proposed approach effectively reduces trajectory execution time while enabling robust collision avoidance in complex environments. Our software1is available on GitHub, along with the developed autonomy framework2, as open-source ROS packages.

Autonomous exploration in dynamic environments necessitates a planner that can proactively respond to changes and make efficient and safe decisions for robots. Although plenty of sampling-based works have shown success in exploring static environments, their inherent sampling randomness and limited utilization of previous samples often result in sub-optimal exploration efficiency. Additionally, most of these methods struggle with efficient replanning and collision avoidance in dynamic settings. To overcome these limitations, we propose the Heuristic-based Incremental Probabilistic Roadmap Exploration (HIRE) planner for UAVs exploring dynamic environments. The proposed planner adopts an incremental sampling strategy based on the probabilistic roadmap constructed by heuristic sampling toward the unexplored region next to the free space, defined as the heuristic frontier regions. The heuristic frontier regions are detected by applying a lightweight vision-based method to the different levels of the occupancy map. Moreover, our dynamic module ensures that the planner dynamically updates roadmap information based on the environment changes and avoids dynamic obstacles. Simulation and physical experiments prove that our planner can efficiently and safely explore dynamic environments. Our software1is available on GitHub with the experiment video2.

Navigating dynamic environments requires the robot to generate collision-free trajectories and actively avoid moving obstacles. Most previous works designed path planning algorithms based on one single map representation, such as the geometric, occupancy, or ESDF map. Although they have shown success in static environments, due to the limitation of map representation, those methods cannot reliably handle static and dynamic obstacles simultaneously. To address the problem, this paper proposes a gradient-based B-spline trajectory optimization algorithm utilizing the robot's onboard vision. The depth vision enables the robot to track and represent dynamic objects geometrically based on the voxel map. The proposed optimization first adopts the circle-based guide-point algorithm to approximate the costs and gradients for avoiding static obstacles. Then, with the vision-detected moving objects, our receding-horizon distance field is simultaneously used to prevent dynamic collisions. Finally, the iterative re-guide strategy is applied to generate the collision-free trajectory. The simulation and physical experiments prove that our method can run in real-time to navigate dynamic environments safely.

The real-time dynamic environment perception has become vital for autonomous robots in crowded spaces. Although the popular voxel-based mapping methods can efficiently represent 3D obstacles with arbitrarily complex shapes, they can hardly distinguish between static and dynamic obstacles, leading to the limited performance of obstacle avoidance. While plenty of sophisticated learning-based dynamic obstacle detection algorithms exist in autonomous driving, the quad-copter's limited computation resources cannot achieve real-time performance using those approaches. To address these issues, we propose a real-time dynamic obstacle tracking and mapping system for quadcopter obstacle avoidance using an RGB-D camera. The proposed system first utilizes a depth image with an occupancy voxel map to generate potential dynamic obstacle regions as proposals. With the obstacle region proposals, the Kalman filter and our continuity filter are applied to track each dynamic obstacle. Finally, the environment-aware trajectory prediction method is proposed based on the Markov chain using the states of tracked dynamic obstacles. We implemented the proposed system with our custom quadcopter and navigation planner. The simulation and physical experiments show that our methods can successfully track and represent obstacles in dynamic environments in real-time and safely avoid obstacles.

Safe UAV navigation is challenging due to the complex environment structures, dynamic obstacles, and uncertainties from measurement noises and unpredictable moving obstacle behaviors. Although plenty of recent works achieve safe navigation in complex static environments with sophisticated mapping algorithms, such as occupancy map and ESDF map, these methods cannot reliably handle dynamic environments due to the mapping limitation from moving obstacles. To address the limitation, this paper proposes a trajectory planning framework to achieve safe navigation considering complex static environments with dynamic obstacles. To reliably handle dynamic obstacles, we divide the environment representation into static mapping and dynamic object representation, which can be obtained from computer vision methods. Our framework first generates a static trajectory based on the proposed iterative corridor shrinking algorithm. Then, reactive chance-constrained model predictive control with temporal goal tracking is applied to avoid dynamic obstacles with uncertainties. The simulation results in various environments demonstrate the ability of our algorithm to navigate safely in complex static environments with dynamic obstacles.

We present a multi-UAV Coverage Path Planning (CPP) framework for the inspection of large-scale, complex 3D structures. In the proposed sampling-based coverage path planning method, we formulate the multi-UAV inspection applications as a multi-agent coverage path planning problem. By combining two NP-hard problems: Set Covering Problem (SCP) and Vehicle Routing Problem (VRP), a Set-Covering Vehicle Routing Problem (SC-VRP) is formulated and subsequently solved by a modified Biased Random Key Genetic Algorithm (BRKGA) with novel, efficient encoding strategies and local improvement heuristics. We test our proposed method for several complex 3D structures with the 3D model extracted from OpenStreetMap. The proposed method outperforms previous methods, by reducing the length of the planned inspection path by up to 48%.

There is a strong demand for covering a large area autonomously by multiple UAVs (Unmanned Aerial Vehicles) supported by a ground vehicle. Limited by UAVs' battery life and communication distance, complete coverage of large areas typically involves multiple take-offs and landings to recharge batteries, and the transportation of UAVs between operation areas by a ground vehicle. In this paper, we introduce a novel large-area-coverage planning framework which collectively optimizes the paths for aerial and ground vehicles. Our method first partitions a large area into sub-areas, each of which a given fleet of UAVs can cover without recharging batteries. UAV operation routes, or trails, are then generated for each sub-area. Next, the assignment of trials to different UAVs and the order in which UAVs visit their assigned trails are simultaneously optimized to minimize the total UAV flight distance. Finally, a ground vehicle transportation path which visits all sub-areas is found by solving an asymmetric traveling salesman problem (ATSP). Although finding the globally optimal trail assignment and transition paths can be formulated as a Mixed Integer Quadratic Program (MIQP), the MIQP is intractable even for small problems. We show that the solution time can be reduced to close-to-real-time levels by first finding a feasible solution using a Random Key Genetic Algorithm (RKGA), which is then locally optimized by solving a much smaller MIQP.

Planning the path to gather the surface information of the target objects is crucial to improve the efficiency of and reduce the overall cost, for visual inspection applications with Unmanned Aerial Vehicles (UAVs). Coverage Path Planning (CPP) problem is often formulated for these inspection applications because of the coverage requirement. Traditionally, researchers usually plan and optimize the viewpoints to capture the surface information first, and then optimize the path to visit the selected viewpoints. In this paper, we propose a novel planning method to directly sample and plan the inspection path for a camera-equipped UAV to acquire visual and geometric information of the target structures as a video stream setting in complex 3D environment. The proposed planning method first generates via-points and path primitives around the target object by using sampling methods based on voxel dilation and subtraction. A novel Primitive Coverage Graph (PCG) is then proposed to encode the topological information, flying distances, and visibility information, with the sampled via-points and path primitives. Finally graph search is performed to find the resultant path in the PCG to complete the inspection task with the coverage requirements. The effectiveness of the proposed method is demonstrated through simulation and field tests in this paper.

In Japan, inspection of irrigation water canals has been mostly conducted manually. However, the huge demand for more regular inspections as infrastructure ages, coupled with the limited time window available for inspection, has rendered manual inspection increasingly insufficient. With shortened inspection time and reduced labor cost, automated inspection using a combination of unmanned aerial vehicles (UAVs) and ground vehicles (cars) has emerged as an attractive alternative to manual inspection. In this paper, we propose a path planning framework that generates optimal plans for UAVs and cars to inspect water canals in a large agricultural area (tens of square kilometers). In addition to optimality, the paths need to satisfy several constraints, in order to guarantee UAV navigation safety and to abide by local traffic regulations. In the proposed framework, the canal and road networks are first modeled as two graphs, which are then partitioned into smaller subgraphs that can be covered by a given fleet of UAVs within one battery charge. The problem of finding optimal paths for both UAVs and cars on the graphs, subject to the constraints, is formulated as a integer quadratic program (IQP). The proposed framework can also quickly generate new plans when a current plan is interrupted. The effectiveness of the proposed framework is validated by simulation results showing the successful generation of plans covering all given canal segments, and the ability to quickly revise the plan when conditions change.

The performance of a robot system heavily relies on its model. The present paper proposes an efficient online Bayesian regression algorithm based on Gaussian Mixture Model. By using the mixture model of local Gaussian experts, the algorithm decouples global correlation of data and achieves linear computational cost to the size of the local model set. The proposed algorithm also realizes on-line implementation. To manage the size of local model on-the-fly, a strategy of adding and pruning local model based on a probabilistic criteria is proposed. Additionally, a forgetting strategy to treat outliers and non-stationary system is suggested. In the end, the algorithm achieved comparable results to other on-line regression algorithms.

This paper presents a novel sampling-based motion planning method for shape inspection applications with a redundant robotic system. In this paper, a 7-Degree-of-Freedom (DOF) redundant robotic system consisting of a 6-DOF manipulator and a 1-DOF turntable is used for the industrial inspection problem. A Set Covering Problem (SCP) is formulated to select suitable viewpoints that satisfy the inspection requirements, and a Generalized Travelling Salesman Problem (GTSP) is formulated to determine both the robot poses and the visiting sequences. While previous studies solve the two problems separately, we formulate the SCP and GTSP problems as a combined sequencing SC-GTSP problem. A Random-Key Genetic Algorithm (RKGA) is then used to solve the combined SC-GTSP problem in a one-step optimization process. To validate the effectiveness of our method, we applied the proposed method to several motion planning cases. The results show that the proposed method outperforms the previous approaches by requiring up to 28.1% less total inspection time.

This paper presents a novel view planning method to generate suitable viewpoints for the reconstruction of the 3D shape of buildings, based on publicly available 2D map data. The proposed method first makes use of 2D map data, along with estimated height information, to generate a rough 3D model of the target building. Randomized sampling procedures are then employed to generate a set of initial candidate viewpoints for the reconstruction process. The most suitable viewpoints are selected from the candidate viewpoint set by first formulating a modified Set Covering Problem (SCP) which considers image registration constraints, as well as uncertainties present in the rough 3D model. A neighborhood greedy search algorithm is proposed to solve this SCP problem and select a series of individual viewpoints deemed most suitable for the 3D reconstruction task. The paper concludes with both computational and real-world field tests to demonstrate the overall effectiveness of the proposed method.

Robot calibration is critical for industrial robot applications that require high accuracy. This paper presents a novel calibration method that utilizes Product-Of-Exponential (POE) and Gaussian Process (GP) regression to compensate for both geometric and non-geometric errors within the robot manipulator. Effects of a payload at the end-effector is also considered in the GP regression model in order to further improve robot positioning accuracy in the task space. Simulation and experimental results demonstrate the effectiveness of the proposed method. The experimental results show that the proposed method reduces norm pose error by 65.5% and 50.2% on average compared to conventional base-tool calibration and POE calibration respectively.

The view planning problem is the problem that involves finding suitable viewpoints for vision-related tasks such as inspection or reconstruction. In this paper, we propose a novel view planning algorithm for a camera-equipped Unmanned Aerial Vehicle (UAV) acquiring visual geometric information of target objects in its surrounding environment. The proposed model-based approach makes use of iterative random sampling and a probabilistic potential-field method to generate candidate viewpoints in a non-deterministic manner. Combinatorial optimization is then applied to select the most suitable subset of these candidate viewpoints to complete the given visual inspection or shape reconstruction task. The effectiveness of the proposed method is demonstrated through a number of computational tests that compare its overall performance against two previous methods. A field-test is also performed to demonstrate the method's applicability in a real world UAV-based shape reconstruction task of an outdoor statue.

Finding an optimal path for a redundant robotic system to visit a sequence of several goal placements poses two technical challenges. First, while searching for an optimal sequence, infinitely many feasible configurations can be used to reach each goal placement. Second, obstacle avoidance has to be considered while optimizing the path from one goal placement to the next. Previous works focused on solving a discrete formulation of this optimization problem where only few configurations are used to represent each goal placement. We instead model it as a Traveling Salesman Problem with Neighborhoods (TSPN), where each neighborhood is defined as the set of the infinitely many configurations corresponding to the same goal placement. A solution procedure based on a Hybrid Random-key Genetic Algorithm (HRKGA) and bidirectional Rapidly-exploring Random Trees (biRRTs) is then proposed. Finally, experimental tests performed on a 7-Degree Of Freedom (DOF) industrial vision inspection system show that the proposed method is able to drastically reduce the cycle time currently required by the system.

In recent years, robots have been increasingly utilized in applications with complex unknown environments, which makes system modeling challenging. In order to meet the demand from such applications, an experience-based learning approach can be used. In this paper, a novel learning algorithm is proposed, which can learn an unknown system model from given data iteratively using a localization approach to manage the computational costs for real time applications. The algorithm segments the data domain by measuring significance of data. As case studies, the proposed algorithm is tested on the control of the mecanum-wheeled robot and in learning the inverse kinematics of a kinematically-redundant manipulator. As the result, the algorithm achieves the on-line system model learning for real time robotics applications.

Kinematically redundant manipulators are coveted for their ability to perform more complex and a greater variety of tasks than their non-redundant counterparts. This increased utility demands that manipulator designs be carefully optimized to achieve the kinematic dexterity required to perform their numerous intended tasks. The optimization of redundant manipulator designs to improve isotropy has been studied at great length, but a vast majority of the work done focuses on planar manipulation tasks and workspaces that, unlike many modern manufacturing environments, offer few or no physical impediments to motion. In this paper we investigate the incorporation of secondary manipulation goals, in particular obstacle avoidance, into the calculation of kinematic isotropy measures. We will use these weighted isotropy measures as a performance metric for redundant manipulators working in obstacle-laden workspaces, and employ the metric as part of an objective function for a global search design optimization problem. The effectiveness of the weighted isotropy design optimization will be demonstrated by increasing the global dexterity of a sub-optimal seven degree-of-freedom manipulator design used for pick-and-place tasks within a small, enclosed workspace.

This paper presents a computational method for converting a tetrahedral mesh to a prism-tetrahedral hybrid mesh for improved solution accuracy and computational efficiency of finite element analysis. The proposed method inserts layers of prism elements and deletes tetrahedral elements in sweepable sub-domains, in which cross-sections remain topologically identical and geometrically similar along a certain sweeping path. The total number of finite elements is reduced because roughly three tetrahedral elements are converted to one prism element. The solution accuracy of the finite element analysis improves since a prism element yields a more accurate solution than a tetrahedral element. Only previously known method for creating such a prism-tetrahedral mesh was to manually decompose a target volume into sweepable and non-sweepable sub-volumes and mesh each sub-volume separately. The proposed method starts from a cross-section of a tetrahedral mesh and replaces the tetrahedral elements with layers of prism elements until prescribed quality criteria can no longer be satisfied. The method applies a sequence of edge-collapse, local-transformation, and smoothing operations to remove or displace nodes located within the volume to be replaced with a layer of prism elements. Series of computational fluid dynamics simulations and structural analyses have been conducted, and the results verified a better performance of prismtetrahedral hybrid mesh in finite element simulations.

This paper describes a new approach to industrial styling design that combines the advantages of pen-based sketching with concepts from variational design to facilitate rapid and fluid development of 3D geometry. The approach is particularly useful for designing products that are primarily stylistic variations of existing ones. The input to the system is a 2D concept sketch of the object, and a generic 3D wireframe template. In the first step, the underlying template is aligned with the input sketch using a camera calibration algorithm. Next, the user traces the feature edges of the sketch on the computer screen; user's 2D strokes are processed and interpreted in 3D to modify the edges of the template. The resulting wireframe is then surfaced, followed by a user-controlled refinement of the initial surfaces using physically-based deformation techniques. Finally, new design edges can be added and manipulated through direct sketching over existing surfaces. Our preliminary evaluation involving several industrial products have demonstrated that with the proposed system, design times can be significantly reduced compared to those obtained through conventional software.

This paper presents a method for occlusion-free animation of geographical landmarks, and its application to a new type of car navigation system in which driving routes of interest are always visible. This is achieved by animating a nonperspective image where geographical landmarks such as mountain tops and roads are rendered as if they are seen from different viewpoints. The technical contribution of this paper lies in formulating the nonperspective terrain navigation as an inverse problem of continuously deforming a 3D terrain surface from the 2D screen arrangement of its associated geographical landmarks. The present approach provides a perceptually reasonable compromise between the navigation clarity and visual realism where the corresponding nonperspective view is fully augmented by assigning appropriate textures and shading effects to the terrain surface according to its geometry. An eye tracking experiment is conducted to prove that the present approach actually exhibits visually-pleasing navigation frames while users can clearly recognize the shape of the driving route without occlusion, together with the spatial configuration of geographical landmarks in its neighborhood.

This paper describes a method for creating a well-shaped, layered tetrahedral mesh of a thin-walled solid by adapting the surface triangle sizes to the estimated wall thickness. The primary target application of the method is the finite element analysis of plastic injection molding, in which a layered mesh improves the accuracy of the solution. The edge lengths of the surface triangles must be proportional to the thickness of the domain to create well-shaped tetrahedrons; when the edge lengths are too short or too long, the shape of the tetrahedron tends to become thin or flat. The proposed method creates such a layered tetrahedral mesh in three steps: (1) create a preliminary tetrahedral mesh of the target geometric domain and estimate thickness distribution over the domain; (2) create a non-uniform surface triangular mesh with edge length adapted to the estimated thickness, then create a single-layer tetrahedral mesh using the surface triangular mesh; and (3) subdivide tetrahedrons of the single-layer mesh into multiple layers by applying a subdivision template. The effectiveness of the layered tetrahedral mesh is verified by running some experimental finite element analyses of plastic injection molding.

This paper describes a new computational method for creating a triangular and quadrilateral mesh of an arbitrary polygonal surface while controlling the anisotropy and directionality of the mesh. The input polygonal surface may include non-manifold edges and holes, and it can be either a closed polyhedron or an open polygonal surface. The method creates a mesh in two steps. In the first step, volumetric cells are packed - ellipsoidal bubbles for a triangular mesh or rectangular solid bubbles for a quadrilateral mesh - on the input polygonal surface, then vertices are created at the centers of the bubbles and superimposed onto the input polygonal surface. In the second step, the original vertices of the input polygonal surface are deleted. The method is tolerant to the noise typically introduced by the measurement error of a laser range scanner, it can control element size and anisotropy precisely, and it creates high quality mesh elements. Applications of the proposed scheme include: reducing the number of elements of a mesh created by a laser range scanner, CT scanner, or MRI scanner; creating a surface mesh that can be a starting mesh for a tetrahedral or a hexahedral finite element mesh; and solution-adaptive anisotropic remeshing for finite element analysis.

A new computational method that creates a hex-dominant mesh of an arbitrary 3D geometric domain is presented. The proposed method generates a high-quality hex-dominant mesh by: (1) controlling the directionality of the output hex-dominant mesh; and (2) avoiding ill-shaped elements induced by nodes located too closely to each other. The proposed method takes a 3D geometric domain as input and creates a hex-dominant mesh that consists of mostly hexahedral elements with additional prism elements and tetrahedral elements. The proposed method packs rectangular solid cells on the boundary of and inside the input domain to obtain ideal node locations for a hex-dominant mesh. Each cell has a potential energy field that mimics a body centered cubic (BCC) structure, and the cells are moved to stable positions by a physically-based simulation. The simulation mimics the formation of a crystal pattern so that the centers of the cells give ideal node locations for a hex-dominant mesh. The domain is then meshed into a tetrahedral mesh by the advancing front method, and finally the tetrahedral mesh is converted to a hex-dominant mesh by merging some tetrahedrons.

This paper uses a configuration space (c-space) based method to compute interference-free configuration for stacking polyhedral sheet metal parts. This work forms the interference analysis module of a stacking planner developed by us. Parts in a stack should not interfere with each other and should also satisfy stability, grasping, and stacking plan feasibility related constraints. We present two techniques to speed up the expensive step of c-space obstacle computation. The first technique identifies orientation intervals (for a convex pair of solids) within which the topology of face-edge-vertex graph of an obstacle stays the same. Within this interval, c-space obstacle geometry for one orientation can be extrapolated from obstacle geometry for another orientation. Our experiments show that extrapolation takes an order of magnitude less than the time taken to compute an obstacle from scratch. The second technique computes near optimal interference-free positions for a discrete orientation without having to compute the complete c-space obstacle. Our experiments show that, for complex sheet metal parts, less than 0.1% of the convex component pairs are evaluated in order to compute an interference-free configuration. We describe a configuration space-based method to compute a list of interference-free configurations that can be tested to see if they satisfy the above mentioned constraints. The cost function is a weighted sum of components that penalize floor space utilization and height of center of gravity of parts. The algorithm is able to pick nested stacks that tend to be stable and compact without having to explicitly enumerate features that can be nested. It is also able to accommodate flanges in holes to reduce the value of the user specified cost function. We use three test parts to illustrate the effect of the two techniques to speed up c-space obstacle computation. We also show the stacking plans generated for three different values of the weighting parameter in the cost function used by the stacking planner.

We present a general method for automatically reconstructing a network of B-spline patches based on the Doo-Sabin subdivision surface. This method consists of two parts, surface fitting and surface construction. In surface fitting, mesh simplification based on QEM (Quadric Error Metrics) is used and a control mesh that approximates a Doo-Sabin subdivision surface is constructed. In surface construction, we define a B-spline surface using a surface spline method; and a constructed network of B-spline patches is guaranteed G/sup 1/ continuous. In addition, this method has the advantage of enabling the user to select detail levels of the control mesh by utilizing a mesh simplification process.

The ability to generate fair curves and surfaces is important in computer graphics (CG), computer-aided design (CAD), and other geometric modeling applications. In this paper, we present an iteration-based algorithm for generating fair polygonal curves and surfaces that is based on a new discrete spring model. In the spring model, a linear spring, whose length approximately represents a curvature radius, is attached along the normal line of each polygon node. Energy is assigned to the difference of the lengths, that is, the difference in curvature radius, of neighboring springs. Our algorithm then minimizes the total energy by an iterative approach. It accepts as inputs (1) an initial polygonal curve (surface), which consists of a set of polygonal segments (faces) and a set of nodes as polygon-vertices, and (2) constraints for controlling the shape. The outputs are polygonal curves (surfaces) with smooth shapes. We also describe a method for improving the performance of our iterative process to obtain a linear execution time. Our algorithm provides a tool for the fair curve and surface design in an interactive environment.