Navigation and obstacle avoidance in aquatic en-vironments for autonomous surface vehicles (ASVs) in high-traffic maritime scenarios is still an open challenge, as the Convention on the International Regulations for Preventing Collisions at Sea (COLREGs) is not defined for multi-encounter situations. Current state-of-the-art methods resolve single-to-single encounters with sequential actions and assume that other obstacles follow COLREGs. Our work proposes a novel real-time non-myopic obstacle avoidance method, allowing an ASV that has only partial knowledge of the surroundings within the sensor radius to navigate in high-traffic maritime scenarios. Specifically, we achieve a holistic view of the feasible ASV action space able to avoid deadlock scenarios, by proposing (1) a clustering method based on motion attributes of other obstacles, (2) a geometric framework for identifying the feasible action space, and (3) a multi-objective optimization to determine the best action. Theoretical analysis and extensive realistic experiments in simulation considering real-world traffic scenarios demonstrate that our proposed real-time obstacle avoidance method is able to achieve safer trajectories than other state-of-the-art methods and that is robust to uncertainty present in the current information available to the ASV.
more »
« less
Risk Vector-based Near miss Obstacle Avoidance for Autonomous Surface Vehicles
This paper presents a novel risk vector-based near miss prediction and obstacle avoidance method. The proposed method uses the sensor readings about the pose of the other obstacles to infer their motion model (velocity and heading) and, accordingly, adapt the risk assessment and take corrective actions if necessary. Relative vector calculations allow the method to perform in real-time. The algorithm has 1.68 times faster computation performance with less change of motion than other methods and it enables a robot to avoid 25 obstacles in a congested area. Fallback behaviors are also proposed in case of faulty sensors or situation changes. Simulation experiments with parameters inferred from experiments in the ocean with our custom-made robotic boat show the flexibility and adaptability of the proposed method to many obstacles present in the environment. Results highlight more efficient trajectories and comparable safety as other state-of-the-art methods, as well as robustness to failures.
more »
« less
- NSF-PAR ID:
- 10224192
- Date Published:
- Journal Name:
- 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)
- Page Range / eLocation ID:
- 1805 to 1812
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We consider the problem of motion planning in the presence of uncertain obstacles, modeled as polytopes with Gaussian-distributed faces (PGDFs). A number of practical algorithms exist for motion planning in the presence of known obstacles by constructing a graph in configuration space, then efficiently searching the graph to find a collision-free path. We show that such an exact algorithm is unlikely to be practical in the domain with uncertain obstacles. In particular, we show that safe 2D motion planning among PGDF obstacles is [Formula: see text]-hard with respect to the number of obstacles, and remains [Formula: see text]-hard after being restricted to a graph. Our reduction is based on a path encoding of MAXQHORNSAT and uses the risk of collision with an obstacle to encode variable assignments and literal satisfactions. This implies that, unlike in the known case, planning under uncertainty is hard, even when given a graph containing the solution. We further show by reduction from [Formula: see text]-SAT that both safe 3D motion planning among PGDF obstacles and the related minimum constraint removal problem remain [Formula: see text]-hard even when restricted to cases where each obstacle overlaps with at most a constant number of other obstacles.more » « less
-
A mini quadrotor can be used in many applications, such as indoor airborne surveillance, payload delivery, and warehouse monitoring. In these applications, vision-based autonomous navigation is one of the most interesting research topics because precise navigation can be implemented based on vision analysis. However, pixel-based vision analysis approaches require a high-powered computer, which is inappropriate to be attached to a small indoor quadrotor. This paper proposes a method called the Motion-vector-based Moving Objects Detection. This method detects and avoids obstacles using stereo motion vectors instead of individual pixels, thereby substantially reducing the data processing requirement. Although this method can also be used in the avoidance of stationary obstacles by taking into account the ego-motion of the quadrotor, this paper primarily focuses on providing our empirical verification on the real-time avoidance of moving objects.more » « less
-
This work considers a Motion Planning Problem with Dynamic Obstacles (MPDO) in 2D that requires finding a minimum-arrivaltime collision-free trajectory for a point robot between its start and goal locations amid dynamic obstacles moving along known trajectories. Existing methods, such as continuous Dijkstra paradigm, can find an optimal solution by restricting the shape of the obstacles or the motion of the robot, while this work makes no such assumptions. Other methods, such as search-based planners and sampling-based approaches can compute a feasible solution to this problem but do not provide approximation bounds. Since finding the optimum is challenging for MPDO, this paper develops a framework that can provide tight lower bounds to the optimum. These bounds act as proxies for the optimum which can then be used to bound the deviation of a feasible solution from the optimum. To accomplish this, we develop a framework that consists of (i) a bi-level discretization approach that converts the MPDO to a relaxed path planning problem, and (ii) an algorithm that can solve the relaxed problem to obtain lower bounds. We also present numerical results to corroborate the performance of the proposed framework. These results show that the bounds obtained by our approach for some instances are up to twice tighter than a baseline approach showcasing potential advantages of the proposed approach.more » « less
-
Safety-guaranteed motion planning is critical for self-driving cars to generate collision-free trajectories. A layered motion planning approach with decoupled path and speed planning is widely used for this purpose. This approach is prone to be suboptimal in the presence of dynamic obstacles. Spatial-temporal approaches deal with path planning and speed planning simultaneously; however, the existing methods only support simple-shaped corridors like cuboids, which restrict the search space for optimization in complex scenarios. We propose to use trapezoidal prism-shaped corridors for optimization, which significantly enlarges the solution space compared to the existing cuboidal corridors-based method. Finally, a piecewise Bezier curve optimization is conducted in our proposed ´ corridors. This formulation theoretically guarantees the safety of the continuous-time trajectory. We validate the efficiency and effectiveness of the proposed approach in numerical and CommonRoad simulationsmore » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1109/IROS45743.2020.9341105
