Tag Archives: Obstacle Avoidance

Graph NNs in RL for improving sample efficiency

March 14, 2024 15:39 ,

Feng Zhang, Chengbin Xuan, Hak-Keung Lam, An obstacle avoidance-specific reinforcement learning method based on fuzzy attention mechanism and heterogeneous graph neural networks, Engineering Applications of Artificial Intelligence, Volume 130, 2024 DOI: 10.1016/j.engappai.2023.107764.

Deep reinforcement learning (RL) is an advancing learning tool to handle robotics control problems. However, it typically suffers from sample efficiency and effectiveness. The emergence of Graph Neural Networks (GNNs) enables the integration of the RL and graph representation learning techniques. It realises outstanding training performance and transfer capability by forming controlling scenarios into the corresponding graph domain. Nevertheless, the existing approaches strongly depend on the artificial graph formation processes with intensive bias and cannot propagate messages discriminatively on explicit physical dependence, which leads to restricted flexibility, size transfer capability and suboptimal performance. This paper proposes a fuzzy attention mechanism-based heterogeneous graph neural network (FAM-HGNN) framework for resolving the control problem under the RL context. FAM emphasises the significant connections and weakening of the trivial connections in a fully connected graph, which mitigates the potential negative influence caused by the artificial graph formation process. HGNN obtains a higher level of relational inductive bias by conducting graph propagations on a masked graph. Experimental results show that our FAM-HGNN outperforms the multi-layer perceptron-based and the existing GNN-based RL approaches regarding training performance and size transfer capability. We also conducted an ablation study and sensitivity analysis to validate the efficacy of the proposed method further.

Posted in: Applications of reinforcement learning to robots , Tagged: , ,

Motion planning with uncertain obstacles is NP-hard

July 7, 2023 11:21 ,

Shimanuki L, Axelrod B., Hardness of Motion Planning with Obstacle Uncertainty in Two Dimensions, . The International Journal of Robotics Research. 2021;40(10-11):1151-1166 DOI: 10.1177/0278364921992787.

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 NP-hard with respect to the number of obstacles, and remains NP-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 3-SAT that both safe 3D motion planning among PGDF obstacles and the related minimum constraint removal problem remain NP-hard even when restricted to cases where each obstacle overlaps with at most a constant number of other obstacles.

Posted in: Robot motion planning , Tagged:

Evaluating the safeness of a motion plan for mobile robot navigation

June 12, 2018 07:54 ,

Brian Axelrod, Leslie Pack Kaelbling, and Tomás Lozano-Pérez Provably safe robot navigation with obstacle uncertainty, The International Journal of Robotics Research Vol 37, Issue 7 DOI: 10.1177/0278364918778338.

As drones and autonomous cars become more widespread, it is becoming increasingly important that robots can operate safely under realistic conditions. The noisy information fed into real systems means that robots must use estimates of the environment to plan navigation. Efficiently guaranteeing that the resulting motion plans are safe under these circumstances has proved difficult. We examine how to guarantee that a trajectory or policy has at most ϵ collision probability (ϵ-safe) with only imperfect observations of the environment. We examine the implications of various mathematical formalisms of safety and arrive at a mathematical notion of safety of a long-term execution, even when conditioned on observational information. We explore the idea of shadows that generalize the notion of a confidence set to estimated shapes and present a theorem that allows us to understand the relationship between shadows and their classical statistical equivalents such as confidence and credible sets. We present efficient algorithms that use shadows to prove that trajectories or policies are safe with much tighter bounds than in previous work. Notably, the complexity of the environment does not affect our method’s ability to evaluate whether a trajectory or policy is safe. We then use these safety-checking methods to design a safe variant of the rapidly exploring random tree (RRT) planning algorithm.

Posted in: Robot motion planning , Tagged:

Real-time modification of user inputs in the teleoperation of an UAV in order to avoid obstacles with a reactive algorithm, transparently from the user control

July 26, 2017 08:55 ,

Daman Bareiss, Joseph R. Bourne & Kam K. Leang, On-board model-based automatic collision avoidance: application in remotely-piloted unmanned aerial vehicles, Auton Robot (2017) 41:1539–1554, DOI: 10.1007/s10514-017-9614-4.

This paper focuses on real-world implementation and verification of a local, model-based stochastic automatic collision avoidance algorithm, with application in
remotely-piloted (tele-operated) unmanned aerial vehicles (UAVs). Automatic collision detection and avoidance for tele-operated UAVs can reduce the workload of pilots to allow them to focus on the task at hand, such as searching for victims in a search and rescue scenario following a natural disaster. The proposed algorithm takes the pilot’s input and exploits the robot’s dynamics to predict the robot’s trajectory for determining whether a collision will occur. Using on-board sensors for obstacle detection, if a collision is imminent, the algorithm modifies the pilot’s input to avoid the collision while attempting to maintain the pilot’s intent. The algorithm is implemented using a low-cost on-board computer, flight-control system, and a two-dimensional laser illuminated detection and ranging sensor for obstacle detection along the trajectory of the robot. The sensor data is processed using a split-and-merge segmentation algorithm and an approximate Minkowski difference. Results from flight tests demonstrate the algorithm’s capabilities for teleoperated collision-free control of an experimental UAV.

Posted in: Robot motion planning , Tagged: , ,