Adaptive Space Expansion for Fast Motion Planning

The sampling process is very inefficient for sam-pling-based motion planning algorithms that excess random sam-ples are generated in the planning space.In this paper,we pro-pose an adaptive space expansion(ASE)approach which belongs to the informed sampling category to improve the sampling effi-ciency for quickly finding a feasible path.The ASE method enlarges the search space gradually and restrains the sampling process in a sequence of small hyper-ellipsoid ring subsets to avoid exploring the unnecessary space.Specifically,for a con-structed small hyper-ellipsoid ring subset,if the algorithm cannot find a feasible path in it,then the subset is expanded.Thus,the ASE method successively does space exploring and space expan-sion until the final path has been found.Besides,we present a particular construction method of the hyper-ellipsoid ring that uniform random samples can be directly generated in it.At last,we present a feasible motion planner BiASE and an asymptoti-cally optimal motion planner BiASE*using the bidirectional exploring method and the ASE strategy.Simulations demon-strate that the computation speed is much faster than that of the state-of-the-art algorithms.The source codes are available at https://github.com/shshlei/ompl.

Evolutionary Decision-Making and Planning for Autonomous Driving Based on Safe and Rational Exploration and Exploitation

Decision-making and motion planning are extremely important in autonomous driving to ensure safe driving in a real-world environment.This study proposes an online evolutionary decision-making and motion planning framework for autonomous driving based on a hybrid data-and model-driven method.First,a data-driven decision-making module based on deep reinforcement learning(DRL)is developed to pursue a rational driving performance as much as possible.Then,model predictive control(MPC)is employed to execute both longitudinal and lateral motion planning tasks.Multiple constraints are defined according to the vehicle’s physical limit to meet the driving task requirements.Finally,two principles of safety and rationality for the self-evolution of autonomous driving are proposed.A motion envelope is established and embedded into a rational exploration and exploitation scheme,which filters out unreasonable experiences by masking unsafe actions so as to collect high-quality training data for the DRL agent.Experiments with a high-fidelity vehicle model and MATLAB/Simulink co-simulation environment are conducted,and the results show that the proposed online-evolution framework is able to generate safer,more rational,and more efficient driving action in a real-world environment.

Motion Planning for Autonomous Driving with Real Traffic Data Validation

Accurate trajectory prediction of surrounding road users is the fundamental input for motion planning,which enables safe autonomous driving on public roads.In this paper,a safe motion planning approach is proposed based on the deep learning-based trajectory prediction method.To begin with,a trajectory prediction model is established based on the graph neural network(GNN)that is trained utilizing the INTERACTION dataset.Then,the validated trajectory prediction model is used to predict the future trajectories of surrounding road users,including pedestrians and vehicles.In addition,a GNN prediction model-enabled motion planner is developed based on the model predictive control technique.Furthermore,two driving scenarios are extracted from the INTERACTION dataset to validate and evaluate the effectiveness of the proposed motion planning approach,i.e.,merging and roundabout scenarios.The results demonstrate that the proposed method can lower the risk and improve driving safety compared with the baseline method.

Safe Motion Planning and Control Framework for Automated Vehicles with Zonotopic TRMPC

Model mismatches can cause multi-dimensional uncertainties for the receding horizon control strategies of automated vehicles(AVs).The uncertainties may lead to potentially hazardous behaviors when the AV tracks ideal trajectories that are individually optimized by the AV's planning layer.To address this issue,this study proposes a safe motion planning and control(SMPAC)framework for AVs.For the control layer,a dynamic model including multi-dimensional uncertainties is established.A zonotopic tube-based robust model predictive control scheme is proposed to constrain the uncertain system in a bounded minimum robust positive invariant set.A flexible tube with varying cross-sections is constructed to reduce the controller conservatism.For the planning layer,a concept of safety sets,representing the geometric boundaries of the ego vehicle and obstacles under uncertainties,is proposed.The safety sets provide the basis for the subsequent evaluation and ranking of the generated trajectories.An efficient collision avoidance algorithm decides the desired trajectory through the intersection detection of the safety sets between the ego vehicle and obstacles.A numerical simulation and hardware-in-the-loop experiment validate the effectiveness and real-time performance of the SMPAC.The result of two driving scenarios indicates that the SMPAC can guarantee the safety of automated driving under multi-dimensional uncertainties.

Heuristic Expanding Disconnected Graph:A Rapid Path Planning Method for Mobile Robots

Existing mobile robots mostly use graph search algorithms for path planning,which suffer from relatively low planning efficiency owing to high redundancy and large computational complexity.Due to the limitations of the neighborhood search strategy,the robots could hardly obtain the most optimal global path.A global path planning algorithm,denoted as EDG*,is proposed by expanding nodes using a well-designed expanding disconnected graph operator(EDG)in this paper.Firstly,all obstacles are marked and their corners are located through the map pre-processing.Then,the EDG operator is designed to find points in non-obstruction areas to complete the rapid expansion of disconnected nodes.Finally,the EDG*heuristic iterative algorithm is proposed.It selects the candidate node through a specific valuation function and realizes the node expansion while avoiding collision with a minimum offset.Path planning experiments were conducted in a typical indoor environment and on the public dataset CSM.The result shows that the proposed EDG*reduced the planning time by more than 90%and total length of paths reduced by more than 4.6%.Compared to A*,Dijkstra and JPS,EDG*does not show an exponential explosion effect in map size.The EDG*showed better performance in terms of path smoothness,and collision avoidance.This shows that the EDG*algorithm proposed in this paper can improve the efficiency of path planning and enhance path quality.

Optimal search path planning of UUV in battlefeld ambush scene

Aiming at the practical application of Unmanned Underwater Vehicle(UUV)in underwater combat,this paper proposes a battlefield ambush scene with UUV considering ocean current.Firstly,by establishing these mathematical models of ocean current environment,target movement,and sonar detection,the probability calculation methods of single UUV searching target and multiple UUV cooperatively searching target are given respectively.Then,based on the Hybrid Quantum-behaved Particle Swarm Optimization(HQPSO)algorithm,the path with the highest target search probability is found.Finally,through simulation calculations,the influence of different UUV parameters and target parameters on the target search probability is analyzed,and the minimum number of UUVs that need to be deployed to complete the ambush task is demonstrated,and the optimal search path scheme is obtained.The method proposed in this paper provides a theoretical basis for the practical application of UUV in the future combat.

A Planning Method for Operational Test of UAV Swarm Based on Mission Reliability

The unmanned aerial vehicle(UAV)swarm plays an increasingly important role in the modern battlefield,and the UAV swarm operational test is a vital means to validate the combat effectiveness of the UAV swarm.Due to the high cost and long duration of operational tests,it is essential to plan the test in advance.To solve the problem of planning UAV swarm operational test,this study considers the multi-stage feature of a UAV swarm mission,composed of launch,flight and combat stages,and proposes a method to find test plans that can maximize mission reliability.Therefore,a multi-stage mission reliability model for a UAV swarm is proposed to ensure successful implementation of the mission.A multi-objective integer optimization method that considers both mission reliability and cost is then formulated to obtain the optimal test plans.This study first constructs a mission reliability model for the UAV swarm in the combat stage.Then,the launch stage and flight stage are integrated to develop a complete PMS(Phased Mission Systems)reliability model.Finally,the Binary Decision Diagrams(BDD)and Multi Objective Quantum Particle Swarm Optimization(MOQPSO)methods are proposed to solve the model.The optimal plans considering both reliability and cost are obtained.The proposed model supports the planning of UAV swarm operational tests and represents a meaningful exploration of UAV swarm test planning.

Efficient Route Planning for Real-Time Demand-Responsive Transit

Demand Responsive Transit (DRT) responds to the dynamic users’ requests without any fixed routes and timetablesand determines the stop and the start according to the demands. This study explores the optimization of dynamicvehicle scheduling and real-time route planning in urban public transportation systems, with a focus on busservices. It addresses the limitations of current shared mobility routing algorithms, which are primarily designedfor simpler, single origin/destination scenarios, and do not meet the complex demands of bus transit systems. Theresearch introduces an route planning algorithm designed to dynamically accommodate passenger travel needsand enable real-time route modifications. Unlike traditional methods, this algorithm leverages a queue-based,multi-objective heuristic A∗ approach, offering a solution to the inflexibility and limited coverage of suburbanbus routes. Also, this study conducts a comparative analysis of the proposed algorithm with solutions based onGenetic Algorithm (GA) and Ant Colony Optimization Algorithm (ACO), focusing on calculation time, routelength, passenger waiting time, boarding time, and detour rate. The findings demonstrate that the proposedalgorithmsignificantly enhances route planning speed, achieving an 80–100-fold increase in efficiency over existingmodels, thereby supporting the real-time demands of Demand-Responsive Transportation (DRT) systems. Thestudy concludes that this algorithm not only optimizes route planning in bus transit but also presents a scalablesolution for improving urban mobility.

Ground threat prediction-based path planning of unmanned autonomous helicopter using hybrid enhanced artificial bee colony algorithm

Unmanned autonomous helicopter(UAH)path planning problem is an important component of the UAH mission planning system.Aiming to reduce the influence of non-complete ground threat information on UAH path planning,a ground threat prediction-based path planning method is proposed based on artificial bee colony(ABC)algorithm by collaborative thinking strategy.Firstly,a dynamic threat distribution probability model is developed based on the characteristics of typical ground threats.The dynamic no-fly zone of the UAH is simulated and established by calculating the distribution probability of ground threats in real time.Then,a dynamic path planning method for UAH is designed in complex environment based on the real-time prediction of ground threats.By adding the collision warning mechanism to the path planning model,the flight path could be dynamically adjusted according to changing no-fly zones.Furthermore,a hybrid enhanced ABC algorithm is proposed based on collaborative thinking strategy.The proposed algorithm applies the leader-member thinking mechanism to guide the direction of population evolution,and reduces the negative impact of local optimal solutions caused by collaborative learning update strategy,which makes the optimization performance of ABC algorithm more controllable and efficient.Finally,simulation results verify the feasibility and effectiveness of the proposed ground threat prediction path planning method.

Stochastic programming based coordinated expansion planning of generation,transmission,demand side resources,and energy storage considering the DC transmission system

With the increasing penetration of wind and solar energies,the accompanying uncertainty that propagates in the system places higher requirements on the expansion planning of power systems.A source-grid-load-storage coordinated expansion planning model based on stochastic programming was proposed to suppress the impact of wind and solar energy fluctuations.Multiple types of system components,including demand response service entities,converter stations,DC transmission systems,cascade hydropower stations,and other traditional components,have been extensively modeled.Moreover,energy storage systems are considered to improve the accommodation level of renewable energy and alleviate the influence of intermittence.Demand-response service entities from the load side are used to reduce and move the demand during peak load periods.The uncertainties in wind,solar energy,and loads were simulated using stochastic programming.Finally,the effectiveness of the proposed model is verified through numerical simulations.

A Reverse Path Planning Approach for Enhanced Performance of Multi-Degree-of-Freedom Industrial Manipulators

In the domain of autonomous industrial manipulators,precise positioning and appropriate posture selection in path planning are pivotal for tasks involving obstacle avoidance,such as handling,heat sealing,and stacking.While Multi-Degree-of-Freedom(MDOF)manipulators offer kinematic redundancy,aiding in the derivation of optimal inverse kinematic solutions to meet position and posture requisites,their path planning entails intricate multiobjective optimization,encompassing path,posture,and joint motion optimization.Achieving satisfactory results in practical scenarios remains challenging.In response,this study introduces a novel Reverse Path Planning(RPP)methodology tailored for industrial manipulators.The approach commences by conceptualizing the manipulator’s end-effector as an agent within a reinforcement learning(RL)framework,wherein the state space,action set,and reward function are precisely defined to expedite the search for an initial collision-free path.To enhance convergence speed,the Q-learning algorithm in RL is augmented with Dyna-Q.Additionally,we formulate the cylindrical bounding box of the manipulator based on its Denavit-Hartenberg(DH)parameters and propose a swift collision detection technique.Furthermore,the motion performance of the end-effector is refined through a bidirectional search,and joint weighting coefficients are introduced to mitigate motion in high-power joints.The efficacy of the proposed RPP methodology is rigorously examined through extensive simulations conducted on a six-degree-of-freedom(6-DOF)manipulator encountering two distinct obstacle configurations and target positions.Experimental results substantiate that the RPP method adeptly orchestrates the computation of the shortest collision-free path while adhering to specific posture constraints at the target point.Moreover,itminimizes both posture angle deviations and joint motion,showcasing its prowess in enhancing the operational performance of MDOF industrial manipulators.

An integrated spatial planning of the mountainous landscapes for ski sports in a case area at the eastern Türkiye

Mountainous regions have disadvantages in economic development because of harsh physical and climatic conditions.However,winter tourism activities are one of the key components for supporting economic development in the highlands.Establishing a ski resort area supports direct and indirect employment in a region,and it stops immigration from mountainous regions to other places.This research aimed to assess the potential ski areas using a multi criteria evaluation technique in the Van region which is located in the eastern part of Türkiye.In this context,snow cover duration,sun effect,slope,slope length,elevation,population density,distance from main roads and lake visibility were used as input factors in the decision making process.Each factor was standardized using a fuzzy technique based on existing well-known ski centers in Türkiye.The weight of inputs was defined by applying a survey to the professional skiers.The most important factors were detected as transportation opportunities and snow covers whereas,the least important factors were elevation and population density.Additionally,lake visibility was very important to make a difference from other existing facilities in the region.Therefore,it was included as constraints and lake visible areas were extracted at the final stage of the research.Potential ski areas were mapped in three levels as professional,intermediate and beginner skiers.One of the suitable areas was selected as a sample projection and for the 3D simulation of the ski investment area.Potential costs and benefits were discussed.It was found that a ski tourism area investment can be amortized in 3 years in the region.

Research on Anthropomorphic Obstacle Avoidance Trajectory Planning for Adaptive Driving Scenarios Based on Inverse Reinforcement Learning Theory

The forward design of trajectory planning strategies requires preset trajectory optimization functions,resulting in poor adaptability of the strategy and an inability to accurately generate obstacle avoidance trajectories that conform to real driver behavior habits.In addition,owing to the strong time-varying dynamic characteristics of obstacle avoidance scenarios,it is necessary to design numerous trajectory optimization functions and adjust the corresponding parameters.Therefore,an anthropomorphic obstacle-avoidance trajectory planning strategy for adaptive driving scenarios is proposed.First,numerous expert-demonstrated trajectories are extracted from the HighD natural driving dataset.Subsequently,a trajectory expectation feature-matching algorithm is proposed that uses maximum entropy inverse reinforcement learning theory to learn the extracted expert-demonstrated trajectories and achieve automatic acquisition of the optimization function of the expert-demonstrated trajectory.Furthermore,a mapping model is constructed by combining the key driving scenario information that affects vehicle obstacle avoidance with the weight of the optimization function,and an anthropomorphic obstacle avoidance trajectory planning strategy for adaptive driving scenarios is proposed.Finally,the proposed strategy is verified based on real driving scenarios.The results show that the strategy can adjust the weight distribution of the trajectory optimization function in real time according to the“emergency degree”of obstacle avoidance and the state of the vehicle.Moreover,this strategy can generate anthropomorphic trajectories that are similar to expert-demonstrated trajectories,effectively improving the adaptability and acceptability of trajectories in driving scenarios.

General Optimal Trajectory Planning:Enabling Autonomous Vehicles with the Principle of Least Action

This study presents a general optimal trajectory planning(GOTP)framework for autonomous vehicles(AVs)that can effectively avoid obstacles and guide AVs to complete driving tasks safely and efficiently.Firstly,we employ the fifth-order Bezier curve to generate and smooth the reference path along the road centerline.Cartesian coordinates are then transformed to achieve the curvature continuity of the generated curve.Considering the road constraints and vehicle dynamics,limited polynomial candidate trajectories are generated and smoothed in a curvilinear coordinate system.Furthermore,in selecting the optimal trajectory,we develop a unified and auto-tune objective function based on the principle of least action by employing AVs to simulate drivers’behavior and summarizing their manipulation characteristics of“seeking benefits and avoiding losses.”Finally,by integrating the idea of receding-horizon optimization,the proposed framework is achieved by considering dynamic multi-performance objectives and selecting trajectories that satisfy feasibility,optimality,and adaptability.Extensive simulations and experiments are performed,and the results demonstrate the framework’s feasibility and effectiveness,which avoids both dynamic and static obstacles and applies to various scenarios with multi-source interactive traffic participants.Moreover,we prove that the proposed method can guarantee real-time planning and safety requirements compared to drivers’manipulation.

A digital twins enabled underwater intelligent internet vehicle path planning system via reinforcement learning and edge computing

The Autonomous Underwater Glider(AUG)is a kind of prevailing underwater intelligent internet vehicle and occupies a dominant position in industrial applications,in which path planning is an essential problem.Due to the complexity and variability of the ocean,accurate environment modeling and flexible path planning algorithms are pivotal challenges.The traditional models mainly utilize mathematical functions,which are not complete and reliable.Most existing path planning algorithms depend on the environment and lack flexibility.To overcome these challenges,we propose a path planning system for underwater intelligent internet vehicles.It applies digital twins and sensor data to map the real ocean environment to a virtual digital space,which provides a comprehensive and reliable environment for path simulation.We design a value-based reinforcement learning path planning algorithm and explore the optimal network structure parameters.The path simulation is controlled by a closed-loop model integrated into the terminal vehicle through edge computing.The integration of state input enriches the learning of neural networks and helps to improve generalization and flexibility.The task-related reward function promotes the rapid convergence of the training.The experimental results prove that our reinforcement learning based path planning algorithm has great flexibility and can effectively adapt to a variety of different ocean conditions.

A Path Planning Algorithm Based on Improved RRT Sampling Region

For the problem of slow search and tortuous paths in the Rapidly Exploring Random Tree(RRT)algorithm,a feedback-biased sampling RRT,called FS-RRT,is proposedbasedon RRT.Firstly,toimprove the samplingefficiency of RRT to shorten the search time,the search area of the randomtree is restricted to improve the sampling efficiency.Secondly,to obtain better information about obstacles to shorten the path length,a feedback-biased sampling strategy is used instead of the traditional random sampling,the collision of the expanding node with an obstacle generates feedback information so that the next expanding node avoids expanding within a specific angle range.Thirdly,this paper proposes using the inverse optimization strategy to remove redundancy points from the initial path,making the path shorter and more accurate.Finally,to satisfy the smooth operation of the robot in practice,auxiliary points are used to optimize the cubic Bezier curve to avoid path-crossing obstacles when using the Bezier curve optimization.The experimental results demonstrate that,compared to the traditional RRT algorithm,the proposed FS-RRT algorithm performs favorably against mainstream algorithms regarding running time,number of search iterations,and path length.Moreover,the improved algorithm also performs well in a narrow obstacle environment,and its effectiveness is further confirmed by experimental verification.

Planning,monitoring and replanning techniques for handling abnormity in HTN-based planning and execution

A framework that integrates planning,monitoring and replanning techniques is proposed.It can devise the best solution based on the current state according to specific objectives and properly deal with the influence of abnormity on the plan execution.The framework consists of three parts:the hierarchical task network(HTN)planner based on Monte Carlo tree search(MCTS),hybrid plan monitoring based on forward and backward and norm-based replanning method selection.The HTN planner based on MCTS selects the optimal method for HTN compound task through pre-exploration.Based on specific objectives,it can identify the best solution to the current problem.The hybrid plan monitoring has the capability to detect the influence of abnormity on the effect of an executed action and the premise of an unexecuted action,thus trigger the replanning.The norm-based replanning selection method can measure the difference between the expected state and the actual state,and then select the best replanning algorithm.The experimental results reveal that our method can effectively deal with the influence of abnormity on the implementation of the plan and achieve the target task in an optimal way.

Multi-UAVs Collaborative Path Planning in the Cramped Environment

Due to its flexibility and complementarity, the multiUAVs system is well adapted to complex and cramped workspaces, with great application potential in the search and rescue(SAR) and indoor goods delivery fields. However, safe and effective path planning of multiple unmanned aerial vehicles(UAVs)in the cramped environment is always challenging: conflicts with each other are frequent because of high-density flight paths, collision probability increases because of space constraints, and the search space increases significantly, including time scale, 3D scale and model scale. Thus, this paper proposes a hierarchical collaborative planning framework with a conflict avoidance module at the high level and a path generation module at the low level. The enhanced conflict-base search(ECBS) in our framework is improved to handle the conflicts in the global path planning and avoid the occurrence of local deadlock. And both the collision and kinematic models of UAVs are considered to improve path smoothness and flight safety. Moreover, we specifically designed and published the cramped environment test set containing various unique obstacles to evaluating our framework performance thoroughly. Experiments are carried out relying on Rviz, with multiple flight missions: random, opposite, and staggered, which showed that the proposed method can generate smooth cooperative paths without conflict for at least 60 UAVs in a few minutes.The benchmark and source code are released in https://github.com/inin-xingtian/multi-UAVs-path-planner.

Efficient Penetration Testing Path Planning Based on Reinforcement Learning with Episodic Memory

Intelligent penetration testing is of great significance for the improvement of the security of information systems,and the critical issue is the planning of penetration test paths.In view of the difficulty for attackers to obtain complete network information in realistic network scenarios,Reinforcement Learning(RL)is a promising solution to discover the optimal penetration path under incomplete information about the target network.Existing RL-based methods are challenged by the sizeable discrete action space,which leads to difficulties in the convergence.Moreover,most methods still rely on experts’knowledge.To address these issues,this paper proposes a penetration path planning method based on reinforcement learning with episodic memory.First,the penetration testing problem is formally described in terms of reinforcement learning.To speed up the training process without specific prior knowledge,the proposed algorithm introduces episodic memory to store experienced advantageous strategies for the first time.Furthermore,the method offers an exploration strategy based on episodic memory to guide the agents in learning.The design makes full use of historical experience to achieve the purpose of reducing blind exploration and improving planning efficiency.Ultimately,comparison experiments are carried out with the existing RL-based methods.The results reveal that the proposed method has better convergence performance.The running time is reduced by more than 20%.

An Improved Iterated Greedy Algorithm for Solving Rescue Robot Path Planning Problem with Limited Survival Time

Effective path planning is crucial for mobile robots to quickly reach rescue destination and complete rescue tasks in a post-disaster scenario.In this study,we investigated the post-disaster rescue path planning problem and modeled this problem as a variant of the travel salesman problem(TSP)with life-strength constraints.To address this problem,we proposed an improved iterated greedy(IIG)algorithm.First,a push-forward insertion heuristic(PFIH)strategy was employed to generate a high-quality initial solution.Second,a greedy-based insertion strategy was designed and used in the destruction-construction stage to increase the algorithm’s exploration ability.Furthermore,three problem-specific swap operators were developed to improve the algorithm’s exploitation ability.Additionally,an improved simulated annealing(SA)strategy was used as an acceptance criterion to effectively prevent the algorithm from falling into local optima.To verify the effectiveness of the proposed algorithm,the Solomon dataset was extended to generate 27 instances for simulation.Finally,the proposed IIG was compared with five state-of-the-art algorithms.The parameter analysiswas conducted using the design of experiments(DOE)Taguchi method,and the effectiveness analysis of each component has been verified one by one.Simulation results indicate that IIGoutperforms the compared algorithms in terms of the number of rescue survivors and convergence speed,proving the effectiveness of the proposed algorithm.