To solve the autonomous navigation problem in complex environments, an efficient motion planning approach is newly presented in this paper. Considering the challenges from large-scale, partially unknown complex environments, a three-layer motion planning framework is elaborately designed, including global path planning, local path optimization, and time-optimal velocity planning. Compared with existing approaches, the novelty of this work is twofold: 1) a novel heuristic-guided pruning strategy of motion primitives is proposed and fully integrated into the state lattice-based global path planner to further improve the computational efficiency of graph search, and 2) a new soft-constrained local path optimization approach is proposed, wherein the sparse-banded system structure of the underlying optimization problem is fully exploited to efficiently solve the problem. We validate the safety, smoothness, flexibility, and efficiency of our approach in various complex simulation scenarios and challenging real-world tasks. It is shown that the computational efficiency is improved by 66.21% in the global planning stage and the motion efficiency of the robot is improved by 22.87% compared with the recent quintic B\'{e}zier curve-based state space sampling approach. We name the proposed motion planning framework E$ \mathrm{^3} $MoP, where the number 3 not only means our approach is a three-layer framework but also means the proposed approach is efficient in three stages.
We consider a coded compressed sensing approach for the unsourced random access and replace the outer tree code proposed by Amalladinne et al. with the list recoverable code capable of correcting t errors. A finite-length random coding bound for such codes is derived. The numerical experiments in the single antenna quasi-static Rayleigh fading MAC show that transition to list recoverable codes correcting t errors improves the performance of coded compressed sensing scheme by 7-10 dB compared to the tree code-based scheme. We propose two practical constructions of outer codes. The first is a modification of the tree code. It utilizes the same code structure, and a key difference is a decoder capable of correcting up to t errors. The second is based on the Reed-Solomon codes and Guruswami-Sudan list decoding algorithm. The first scheme provides an energy efficiency very close to the random coding bound when the decoding complexity is unbounded. But for the practical parameters, the second scheme is better and improves the performance of a tree code-based scheme when the number of active users is less than 200.
Rapidly-exploring random tree (RRT) has been applied for autonomous parking due to quickly solving high-dimensional motion planning and easily reflecting constraints. However, planning time increases by the low probability of extending toward narrow parking spots without collisions. To reduce the planning time, the target tree algorithm was proposed, substituting a parking goal in RRT with a set (target tree) of backward parking paths. However, it consists of circular and straight paths, and an autonomous vehicle cannot park accurately because of curvature-discontinuity. Moreover, the planning time increases in complex environments; backward paths can be blocked by obstacles. Therefore, this paper introduces the continuous-curvature target tree algorithm for complex parking environments. First, a target tree includes clothoid paths to address such curvature-discontinuity. Second, to reduce the planning time further, a cost function is defined to construct a target tree that considers obstacles. Integrated with optimal-variant RRT and searching for the shortest path among the reached backward paths, the proposed algorithm obtains a near-optimal path as the sampling time increases. Experiment results in real environments show that the vehicle more accurately parks, and continuous-curvature paths are obtained more quickly and with higher success rates than those acquired with other sampling-based algorithms.
Integrated sensing and communication (ISAC) has been regarded as one of the most promising technologies for future wireless communications. However, the mutual interference in the communication radar coexistence system cannot be ignored. Inspired by the studies of reconfigurable intelligent surface (RIS), we propose a double-RIS-assisted coexistence system where two RISs are deployed for enhancing communication signals and suppressing mutual interference. We aim to jointly optimize the beamforming of RISs and radar to maximize communication performance while maintaining radar detection performance. The investigated problem is challenging, and thus we transform it into an equivalent but more tractable form by introducing auxiliary variables. Then, we propose a penalty dual decomposition (PDD)-based algorithm to solve the resultant problem. Moreover, we consider two special cases: the large radar transmit power scenario and the low radar transmit power scenario. For the former, we prove that the beamforming design is only determined by the communication channel and the corresponding optimal joint beamforming strategy can be obtained in closed-form. For the latter, we minimize the mutual interference via the block coordinate descent (BCD) method. By combining the solutions of these two cases, a low-complexity algorithm is also developed. Finally, simulation results show that both the PDD-based and low-complexity algorithms outperform benchmark algorithms.
We consider a cost sharing problem to connect all nodes in a weighted undirected graph, where the weight of each edge represents the cost to use the edge for the connectivity and the cost has to be shared among all connected nodes. There is one node called the source to which all the other nodes want to connect and it does not share the costs of the connectivity. As a node may need to go through other nodes to reach the source, the intermediate nodes may behave strategically to block the connection by cutting the edges adjacent to them. To prevent such strategical behavior, we design cost sharing mechanisms to incentivize all nodes not to cut any edge so that we can minimize the total cost for connecting all the nodes.
Solving high-dimensional optimal control problems in real-time is an important but challenging problem, with applications to multi-agent path planning problems, which have drawn increased attention given the growing popularity of drones in recent years. In this paper, we propose a novel neural network method called SympOCnet that applies the Symplectic network to solve high-dimensional optimal control problems with state constraints. We present several numerical results on path planning problems in two-dimensional and three-dimensional spaces. Specifically, we demonstrate that our SympOCnet can solve a problem with more than 500 dimensions in 1.5 hours on a single GPU, which shows the effectiveness and efficiency of SympOCnet. The proposed method is scalable and has the potential to solve truly high-dimensional path planning problems in real-time.
The solution of the shortest path problem on a surface is not only a theoretical problem to be solved in the field of mathematics, but also problems that need to be solved in very different fields such as medicine, defense and construction technologies. When it comes to the land specific, solution algorithms for these problems are also of great importance in terms of determination of the shortest path in an open area where the road will pass in the field of civil engineering, or route determination of manned or unmanned vehicles for various logistic needs, especially in raw terrains. In addition, path finding problems in the raw terrains are also important for manned and unmanned ground vehicles (UGV) used in the defense industry. Within the scope of this study, a method that can be used for instant route determinations within sight range or for route determinations covering wider areas is proposed. Although the examples presented within the scope of the study are land-based, the method can be applied to almost all problem types of similar nature. The approach used in the study can be briefly described as the mechanical analysis of a surface transformed into a structural load bearing system based on mechanical analogies. In this approach, the determination of the shortest path connecting two points can be realized by following the stress-strain values that will occur by moving the points away from each other or by following a linear line that will be formed between two points during the mechanical analysis. If the proposed approach is to be carried out with multiple rigid body dynamics approaches instead of flexible bodies mechanics, it can be carried out easily and very quickly by determining the shortest path between two points or by tracking the forces. However, the proposed approach in this study is presented by simulating examples of flexible bodies using FEM.
We present Neural A*, a novel data-driven search method for path planning problems. Despite the recent increasing attention to data-driven path planning, a machine learning approach to search-based planning is still challenging due to the discrete nature of search algorithms. In this work, we reformulate a canonical A* search algorithm to be differentiable and couple it with a convolutional encoder to form an end-to-end trainable neural network planner. Neural A* solves a path planning problem by encoding a problem instance to a guidance map and then performing the differentiable A* search with the guidance map. By learning to match the search results with ground-truth paths provided by experts, Neural A* can produce a path consistent with the ground truth accurately and efficiently. Our extensive experiments confirmed that Neural A* outperformed state-of-the-art data-driven planners in terms of the search optimality and efficiency trade-off, and furthermore, successfully predicted realistic human trajectories by directly performing search-based planning on natural image inputs.
Retrosynthetic planning is a critical task in organic chemistry which identifies a series of reactions that can lead to the synthesis of a target product. The vast number of possible chemical transformations makes the size of the search space very big, and retrosynthetic planning is challenging even for experienced chemists. However, existing methods either require expensive return estimation by rollout with high variance, or optimize for search speed rather than the quality. In this paper, we propose Retro*, a neural-based A*-like algorithm that finds high-quality synthetic routes efficiently. It maintains the search as an AND-OR tree, and learns a neural search bias with off-policy data. Then guided by this neural network, it performs best-first search efficiently during new planning episodes. Experiments on benchmark USPTO datasets show that, our proposed method outperforms existing state-of-the-art with respect to both the success rate and solution quality, while being more efficient at the same time.
Vision-based Simultaneous Localization And Mapping (VSLAM) is a mature problem in Robotics. Most VSLAM systems are feature based methods, which are robust and present high accuracy, but yield sparse maps with limited application for further navigation tasks. Most recently, direct methods which operate directly on image intensity have been introduced, capable of reconstructing richer maps at the cost of higher processing power. In this work, an edge-based monocular SLAM system (SE-SLAM) is proposed as a middle point: edges present good localization as point features, while enabling a structural semidense map reconstruction. However, edges are not easy to associate, track and optimize over time, as they lack descriptors and biunivocal correspondence, unlike point features. To tackle these issues, this paper presents a method to match edges between frames in a consistent manner; a feasible strategy to solve the optimization problem, since its size rapidly increases when working with edges; and the use of non-linear optimization techniques. The resulting system achieves comparable precision to state of the art feature-based and dense/semi-dense systems, while inherently building a structural semi-dense reconstruction of the environment, providing relevant structure data for further navigation algorithms. To achieve such accuracy, state of the art non-linear optimization is needed, over a continuous feed of 10000 edgepoints per frame, to optimize the full semi-dense output. Despite its heavy processing requirements, the system achieves near to real-time operation, thanks to a custom built solver and parallelization of its key stages. In order to encourage further development of edge-based SLAM systems, SE-SLAM source code will be released as open source.
Reinforcement learning and symbolic planning have both been used to build intelligent autonomous agents. Reinforcement learning relies on learning from interactions with real world, which often requires an unfeasibly large amount of experience. Symbolic planning relies on manually crafted symbolic knowledge, which may not be robust to domain uncertainties and changes. In this paper we present a unified framework {\em PEORL} that integrates symbolic planning with hierarchical reinforcement learning (HRL) to cope with decision-making in a dynamic environment with uncertainties. Symbolic plans are used to guide the agent's task execution and learning, and the learned experience is fed back to symbolic knowledge to improve planning. This method leads to rapid policy search and robust symbolic plans in complex domains. The framework is tested on benchmark domains of HRL.