44 results about "Rapidly exploring random tree" patented technology

A path planning apparatus of a robot smoothes a motion path while satisfying a constraint. In a configuration space where a manipulator of a robot performs a task, a Rapidly-exploring Random Tree (RRT) path which extends from a start point and reaches a goal point may be smoothed while satisfying a constraint to generate a stable motion path. Accordingly, path planning performance is improved and an optimal path satisfying a kinematic constraint may be rapidly obtained.

The invention discloses an unmanned aerial vehicle path planning method of an iterative rapidly-exploring random tree IRRT. According to the method disclosed by the invention, heuristic information isintroduced; when a new leaf node Xnew is increased by random sampling, random probability P is introduced; then the new leaf node Xnew is deviated to a target point according to the certain probability; the randomness of the newly-increased leaf node Xnew is weakened; meanwhile, all advantages of an original algorithm are also inherited and a convergence speed is increased; on the basis, a relatively good path is obtained through iteration comparison; a period tree on the relatively good path is stored and the path planning problem in a dynamic environment is solved; the planned path is closeto the relatively good path and the quality of the path is greatly improved.

The invention discloses a UAV path optimization method based on an improved bidirectional rapidly-exploring random-tree algorithm. The method comprises the following steps: 1, establishing a UAV kinematic constraint model and determining a starting point and a target point in a two-dimensional space; 2, based on a backward sector region sampling method, exploring the nodes of the bidirectional random tree; 3, based on a dynamic adaptive step size method, solving the growth limitations near an obstacle; and 4, by connecting the nodes of a bidirectional search tree, forming a complete flight path. Based on a classical B-RRT* algorithm, the method, based on the backward sector region sampling method, restricts random tree sampling points to the backward sector region when the nodes are explored, solves the growth limitations near the obstacle based on the dynamic adaptive step size method, and finally connects respective nodes to generate a flight path that conforms to the real flight ofthe UAV, thereby providing a feasible method for autonomous navigation of the UAV at low altitude.

The invention discloses an RRT (Rapidly exploring Random Tree) algorithm based path planning method. On the basis of the classic algorithm, pruning operation is performed and tiny branches on a tree generated by RRT algorithm are cut off, so that the quantity of nodes travelled through by a finally generated path is reduced and the path bending frequency is reduced. Therefore, the path is more suitable for robot walking. The RRT algorithm is a path planning algorithm disclosed by LaValle in a paper for the first time in 1998 and is a classic algorithm frequently used in MDOF robot motion planning and plan path planning. However, length of paths generated by the RRT algorithm has comparatively large redundancy and the linearity of the paths is poor. Through the improvement implemented through pruning in the invention, path redundancy is reduced and the linearity is improved substantially.

An apparatus for mine avoidance that enables a battle group commander to rapidly detect, classify, and identify mines, and form a tactical picture of mined areas. The system is enabled by a graphical user interface which generates a display of the minefield and an avoidance path which is calculated by a rapidly-explored random trees algorithm interacting with algorithms defining avoidance object spaces inserted by an operator in two or three dimensions and transit vehicle characteristics. The apparatus enables a method which establishes the parameters of an area representing a minefield. The area is then populated with obstacle spaces whose areas are functions of the probability of the existence of a mine and through which an avoidance route through the minefield may not pass. The start and end points of the avoidance route are entered on a graphic display of the minefield and an avoidance path there between is calculated and presented as an avoidance route.

The invention relates to a multi-robot map exploration method based on a rapidly-exploring random tree. The method comprises the following steps of step 1, detecting boundary points by using a boundary detector based on the RRT (Rapidly-Exploring Random Tree) including a global boundary detector and a local boundary detector; step 2, filtering the obtained boundary points, that is, removing the detected boundary points and clustering some dense boundary points, and then storing the filtered boundary points in a boundary point list; step 3, assigning specific boundary points to a robot with thehighest profit by calculating the costs and benefits by using a multi-robot task allocation strategy based on the market economy according to the positions of each boundary point and the robot, so that a local map of the robot is established; and step 4, sharing and integrating map information obtained by each robot through network communication to get a final map. The multi-robot map explorationmethod based on the rapidly-exploring random tree provided by the invention can overcome the defects of the prior art and guide multiple robots to independently explore the unknown environment and establish an environmental map.

The invention discloses a method and a system for planning a sea path of an unmanned ship based on an RRT (rapidly-exploring random tree) algorithm. The method comprises the following steps of obtaining data of a sea map, so as to obtain complete information of the sea map; according to the definition of a polygon of the sea map, displaying the conditions of the sea surface, and rasterizing the original vector data, so as to obtain a complete interface of the sea map; enabling a user to set passing points on the interface of the sea map, and planning the path within the preset time threshold value by an improved RRT algorithm, so as to obtain the final asymptotically optimal effective path; converting the final effective path into the practical longitudinal and altitude information, outputting the longitudinal and altitude information of turning points on the path, and providing for a power control system of the unmanned ship to use. The method has the advantages that the RRT algorithmis further improved, the path passing the multiple preset passing points is planned, and a path compression algorithm is applied so as to effectively reduce the path distance.

The invention relates to a variable probability bidirectional rapidly-exploring random tree improved path planning algorithm. Firstly, when importing a state space map, state space preprocessing needsto be performed according to the setting of the vehicle volume, and the state space edge is extended and protected to prevent the node from excessively approaching the state space edge to cause a collision. Secondly, a variable probability target selection strategy based on the node environment is adopted to accelerate the convergence speed. Finally, the bent part in the generated path is removedwhile the straight part in the generated path is retained, that is, whether connection lines between the first node as the start and the subsequent nodes have an obstacle is judged, the redundant nodes are deleted, the path is optimized, and the number of turns and the total path length during the driving of the trolley are reduced. The variable probability optimization algorithm is achieved based on the original bidirectional RRT algorithm, and the target pointing method is used to improve the search speed and reduce the calculation amount. At the same time, the path length and the number ofnodes are reduced, and the passability is ensured.

The invention relates to an unmanned plane locus planning method based on random sampling in a narrow space, which belongs to the unmanned plane locus planning field. The method comprises the steps of obtaining unmanned plane flight environment information; taking an original state of an unmanned plane, an object state and a 3D model of a flight environment as initial parameters of a locus plan; conducting road sign points sampling based on the 3D model of the flight environment; storing the road sign points in road sign point lists corresponding to a narrow space N and an open area U respectively; employing multiple rapidly-exploring random trees and connecting multiple RRT locus trees in pairs to form a fused RRT locus tree; then connecting the fused RRT locus tree with the original state and the object state of the unmanned plane, thereby generating a complete locus that connects the original state and the object state of the unmanned plane. According to the invention, the calculating efficiency of the unmanned plane locus planning in a narrow space can be effectively raised.

The invention relates to a hybrid path planning method for a mobile robot. A global map is constructed, and on the basis of the global map, hybrid path planning is conducted through a combination of arapid exploring random tree algorithm and a time elastic band algorithm. The hybrid path planning method for the mobile robot combines global path planning and local path planning to achieve mutual compensation under a constraint condition and improve quality and efficiency of a path planning solution; and compared with a single planning method, the hybrid path planning method for the mobile robot has the characteristics that a global path can be quickly planned, dynamic planning and obstacle avoidance functions are realized, and real-time capability and safety of a mobile robot in motion areensured.

The invention provides a three-dimensional automatic wiring method and a three-dimensional automatic wiring device based on a rapidly-exploring random tree. The three-dimensional automatic wiring method comprises the following steps: according to an available space, a starting point and a finishing point of a cable to be arranged to obtain an initial path of the cable to be arranged; detailing the initial path to obtain a middle path; through a cable physical model, modeling the middle path to determine a final path of the cable to be arranged. Through the three-dimensional automatic wiring method and the three-dimensional automatic wiring device, cable arrangement can be achieved easily, rapidly and accurately.

The invention belongs to the technical field of drone operation and discloses a drone real-time path planning method based on an improved RRT (Rapidly-exploring Random Tree). The drone real-time pathplanning method comprises the following steps: constructing a local rolling window; setting local sub-goal points; carrying out random sampling and planning by adopting a local RRT algorithm; and carrying out an algorithm termination principle. According to the drone real-time path planning method, an original algorithm, which is only applicable to global planning, is improved and fused; the window is constructed according to local known environment information; and the sub-goal points are determined through a certain method and a global planning algorithm is used for exploring in the environment. In a process of rolling and frontward moving the window, the environment information in the window is continuously updated and planning mapping and feedback are realized; finally, a goal point isrealized. With regard to the RRT algorithm, the improvement method based on the rolling window does not need to carry out random exploring on a whole space when being compared with global planning; however, planning is limited in numerous windows which are continuously updated; a random exploring range is reduced and the calculation amount is reduced; and online planning can be realized.

The invention discloses an autonomous attitude maneuver control method of a deep space probe, which relates to the autonomous attitude maneuver control method and belongs to the technical field of spacecraft attitude control. The autonomous attitude maneuver control method comprises the following steps of carrying out random sampling on uniformly-distributed nodes of an attitude space with an ORRT (Optimized Rapidly Exploring Random Tree) algorithm as a path planning method, making a balance and choosing the optimum path to expand, carrying out incremental expansion in a safety space in a greedy expansion manner, respectively establishing a probe attitude maneuver dynamic constraint model, an actual engineering constraint model and a probe geometric constraint model under a probe body coordinate system to obtain path nodes which meet the constraint and generate a control moment for the nodes, thereby generating a probe attitude maneuver path and a required control moment, and implementing the purpose that probe maneuvers to a target attitude according to the generated probe attitude maneuver path and the required control moment. According to the autonomous attitude maneuver control method, the path planning time is shortened and the efficiency that the probe maneuvers to the target attitude from the initial attitude is improved under the condition that all kinds of complicated constraint conditions faced by the probe are met.

The invention discloses a rapidly-exploring random tree path smoothing method. The method in the invention is a path smoothing method based on a Douglas-Peucker algorithm and a B spline function. The method comprises the following steps: firstly, extracting a plurality of nodes from a path node generated by a rapidly-exploring random tree algorithm to serve as a key road sign by using the Douglas-Peucker algorithm; then, fitting a key road sign by adopting the B spline function to obtain a smooth path with a continuous curvature, so that smoothing of the planned path is realized, and the problems that excessive redundant points exist in the path generated by the rapidly-exploring random tree algorithm and the turning points of the path are large are solved.

A path planning apparatus of a robot smoothes a motion path while satisfying a constraint. In a configuration space where a manipulator of a robot performs a task, a Rapidly-exploring Random Tree (RRT) path which extends from a start point and reaches a goal point may be smoothed while satisfying a constraint to generate a stable motion path. Accordingly, path planning performance is improved and an optimal path satisfying a kinematic constraint may be rapidly obtained.

The invention belongs to the technical field of application of unmanned aerial vehicles, and discloses an RRT (rapidly-exploring random tree) route optimizing method of an unmanned aerial vehicle based on a greedy algorithm. The RRT route optimizing method comprises the following steps of using qinit as the current point qi, and initializing n to be 0; performing collision detection on a Q focus point qm-n since qi (n is [0,1,2 until to (m-i-1)]), and uniformly selecting points on the connecting line of qi and qm-n at certain intervals; judging whether the existence point is positioned on theobstacle or outside a map; when the existence point exists, turning to step 4; or else, turning to step 5; when the obstacle exists, namely that the connecting line passes through the fly-prohibitingarea, and n is equal to n+1, judging whether qi is qm-n-1 or not; when qi is qm-n-1, enabling i to be equal to i+1; or else, returning back; when the obstacle does not exist, connecting qi and qm-n, enabling qi to be equal to qm-n, and turning to step 6; judging whether i is equal to m or not; when i equal to m, finishing the program. The RRT route optimizing method has the advantages that when the RRT algorithm route of the unmanned aerial vehicle is planned, the route is reduced, the greedy concept is utilized, the result is the current optimum result, the number of route points is reduced,and the route is greatly optimized; the certain engineering value is realized on the application of route planning of the unmanned aerial vehicle or other robots.

The invention belongs to the field of track planning, and relates to a method for planning a track by predicting track uncertainty when a moving body is greatly influenced by movement uncertainty in a complicated environment. A dynamic model of the moving body, a process noise model and an observation noise model are utilized, the deviation of a real track is divided into the sum of the deviation of the real track from an estimated track and the deviation of the estimated track from a planned track, the uncertainty of the real track is predicted in a probability form, and on such a basis, a feasible track is planned by combining a rapidly-exploring random tree method. According to the method, the dynamic constraints of a high-speed moving body and the influence of process noise and observation noise are simultaneously taken into account, and the uncertainty of the planned track is predicted in advance by movement model and error model-based prediction, so that the probability of collision between the moving body and an obstacle at any moment is ensured to be lower than (1-delta1), and the probability of reaching a target region is ensured to be higher than delta2; therefore, the feasibility of the planned track is ensured in terms of probability.

The invention discloses a mobile robot autonomous exploration method fusing path information richness, and the method comprises the following steps of: acquiring environmental information in a sensingrange by a robot and changing an environment from an unknown state to a known state; generating a quick search random tree in an idle area of the known state, clustering boundary points of the quicksearch random tree by adopting a clustering algorithm to obtain centroid points, and meanwhile, detecting a grid state of the boundary points and removing invalid points; combining the information gain, the path cost, the path information richness and the boundary point information richness to construct a revenue function, and calculating a revenue value of the revenue function at each centroid point; selecting the centroid point with the maximum income value as a target point, and guiding the robot to move to the target point; and repeating the above steps until the whole environment is explored to obtain a grid map. According to the method, the path information richness and the boundary point information richness are added when the revenue function is constructed, consideration factors in the boundary point selection process are enriched, the perception uncertainty of the robot is reduced, and the exploration efficiency is improved.

The invention relates to a robot planning algorithm fusing a visibility graph and a rapidly-exploring random tree. The robot planning algorithm comprises the following steps that S1, based on the visibility graph, a topological graph is established to model the environment; S2, a shortest path is obtained through a dijkstra algorithm and serves as a reference path; S3, the reference path is divided, by combining an SST algorithm, average sampling strategies are utilized for random sampling within a certain range of the reference path; S4, the algorithm efficiency is improved through Bias-goal;S5, within the current extension range, a tree node nearest to the range of a current sampling point area is selected according to the Dubins distance; S6, transverse control strategies are adopted to select the controlled quantity to integrate a system model, and optimally dissipated nodes are preferentially expanded; and S7, if no collision occurs in the extension process, whether generated newnodes are optimal in a local neighborhood or not is studied, if yes, the nodes are added into the tree structure, and dominant nodes in the current area are trimmed. A path generated by the visibility graph can be optimized through the stable sparse rapidly-exploring random tree, so that the optimal path conforming to restriction of the nonholonomic restriction robot is obtained.

The invention discloses a path planning method based on a simulated plant growth guiding RRT (rapidly-exploring random tree) algorithm. The method comprises the following steps: initializing map information; calculating the roadblock blocking influences on the growth at a current point in every direction; judging whether a light source point can be directly seen or not; calculating the light attraction borne by the current point; calculating the resultant force borne by the current point; calculating the current growth direction of terminal buds, and growing a step length unit; judging whetherthe coordinates of a new position are outside a boundary or within the roadblock or not; updating the current point to be a new position, and storing the new position as a path point array; judging whether the current point is a target point or not; outputting the path point array; planning a path through the RRT algorithm; judging whether a new path can be found or not; and carrying out cubic Bezier curve fitting. The algorithm provided by the invention greatly improves the tracking effect of the RRT algorithm, and the sampling of the traditional RRT algorithm is random sampling, so tree nodes generated by the improved algorithm cover the entire map area with the rising of the number of iterations.

The invention discloses an unmanned vehicle dynamic path planning method based on a free space and a fast search random tree algorithm. A method for constructing a free space on a barrier-containing map is designed by utilizing a concave polygon convex decomposition graphics method, and an artificial bee colony algorithm is applied to carry out path optimization to find out a global optimal path. The fast path planning method based on the improved fast search random tree algorithm is realized by adjusting the random tree node sampling probability. Finally, global path planning of a dynamic map and local rapid path planning in the unmanned vehicle advancing process are achieved through the free space method and the rapid search random tree algorithm, and the quality and speed of path planning in the dynamic environment are both considered.

A means for mine avoidance that enables a battle group commander to rapidly detect, classify, and identify mines, and form a tactical picture of mined areas. The system is enabled by a graphical user interface which generates a display of the minefield and an avoidance path which is calculated by a rapidly-explored random trees algorithm interacting with algorithms defining avoidance object spaces inserted by an operator in two or three dimensions and transit vehicle characteristics. The apparatus enables a method which establishes the parameters of an area representing a minefield. The area is then populated with obstacle spaces whose areas are functions of the probability of the existence of a mine and through which an avoidance route through the minefield may not pass. The start and end points of the avoidance route are entered on a graphic display of the minefield and an avoidance path there between is calculated and presented as an avoidance route.

The invention aims to provide a path search method and device for a mobile robot. According to the invention, a high-level strategy of efficiency path searching is carried out on a large map by usinga rapidly-exploring random tree (RRT), users can create an RRT during map establishment or create an RRT for a large known map in real time, then the created RRT is applied to a subsequent path searchalgorithm so as to enable the search time to be greatly reduced. The path search method and device can quickly search a path between a set starting point and an end point and provide the path to an upper navigation system of the robot to use. The core advantage of the RRT is that the time is extremely short, thereby being applicable to the use in embedded equipment, and solving the defect of longconsumed time of the traditional path search algorithm.

The invention discloses a parafoil combined type flight path planning method in a complex environment. The method comprises: dividing a parafoil air-drop area into an obstacle area with obstacles andan open and flat circular landing area with a target point as the circle center; quickly searching a feasible track in the obstacle area by adopting a quick search random tree path planning algorithm,and only considering an obstacle avoidance task in the obstacle area under the search termination condition that the horizontal distance between the position to which the path extends and the targetlanding point is less than or equal to the radius of the circular landing area; and taking the termination state of track search in the obstacle area as the initial state of track planning in the circular landing area, and completing parafoil height control and headwind alignment tasks in the circular landing area by adopting the planning design of segmented homing. Obstacle avoidance and other requirements needing to be met by parafoil route planning in a complex environment are divided into two stages to be processed, meanwhile, smooth connection of the two route planning stages can be met,and parafoil route planning in the complex environment is achieved.

The embodiment of the invention provides an improved rapid search random tree path planning method in a large-area environment, and belongs to the technical field of robot path planning. According tothe improved rapid search random tree path planning method in the large-area environment, sampling points are searched in a planning space, and search trees are established between the starting pointand the sampling points, between the sampling points and the starting point, between the sampling points and the target point and between the target point and the sampling points respectively for pathsearch. A path planning problem of a large-area environment is converted into a plurality of path planning problems, the complexity of a path planning algorithm is reduced, and the execution efficiency of the path planning algorithm is improved.

The invention discloses an articulated engineering vehicle path planning method based on a support vector machine, and the method comprises the following steps: 1, searching a proper path in an experiment scene through employing a target-oriented quick search random tree algorithm, and respectively marking real obstacles at two sides of the path as two different classification labels; 2, respectively adding a group of virtual obstacles near the starting point and the ending point of the vehicle, marking the virtual obstacles as two different classification labels, and obtaining a two-dimensional optimal zero potential curve and a maximum interval of the marked real obstacles and virtual obstacles through a support vector machine theory; 3, obtaining a plurality of key inflection points onthe two-dimensional optimal zero potential curve by utilizing a 'farthest reachable distance method '; 4, obtaining a planned path. In consideration of the interference of obstacles in reality and thespecial steering characteristics of the articulated engineering vehicle, a path capable of enabling the articulated engineering vehicle to directly track is designed.

The invention relates to an unmanned ship navigation planning method in a complex water area environment, and the method comprises the steps: 1, obtaining the task content issued by an unmaned snhip control center according to task requirements of an unmanned ship; 2, performing unmanned ship navigation task stage division; 3, enabling the unmanned ship to detect and identify water-surface and underwater obstacles by carrying navigation equipment in a navigation sea area covered by the navigation capability, obtaining unknown environment information, and constructing a more complete water area environment; 4, according to the water area environment constructed in the step 3, taking the current position of the unmanned ship as an initial planning position, dividing the terminal point of the current stage as a navigation arrival area of the unmanned ship in the navigation task stage in the step 2, and performing navigation local path planning of the unmanned ship by using a fast search random tree algorithm; and 5, executing the planned route of the previous stage, which is completely planned, by using a rolling window strategy, and meanwhile, re-planning the navigation route of the next stage until the whole navigation task is finally completed. According to the invention, an effective solution is provided for construction of the unmanned ship in the complex water area environment.

The invention relates to a dynamic feedback route planning method adopting an invariant set. According to the dynamic feedback route planning method disclosed by the invention, states near different balance points are guided to a next balance point until reaching a goal; selection of the balance points adopts an asymptotic optimally RRT (Rapidly-Exploring Random Tree) and combines the invariant set of a local system, and the tree structure can be regulated according to current obstacle restriction; a safe passage is formed through the invariant set, and an intelligent agent is enabled to be located in one safety passage, so that the safety and the reachability of planning are ensured.

The invention discloses a humanoid mechanical arm movement route planning method and system. The method includes the steps that the start position and the target position of the to-be-moved space of ahumanoid mechanical arm are determined according to a D-H model of the humanoid mechanical arm; a sampling point of the to-be-moved space of the humanoid mechanical arm is explored through a rapidlyexploring random tree method, and in the exploring process, a random sampling point is determined through a bias probability sampling algorithm; and new node extension is conducted according to the determined random sampling point, and through combination with a new node, an extension random tree with the start position as a source and the target position as a terminal node is established. Finally, the route with the minimum total weight is found in all routes of the established extension tree, information of all nodes in the route with the minimum total weight is solved into joint angle information of humanoid mechanical arm movement through inverse kinematics, and the humanoid mechanical arm is made to move according to the joint angle information. By means of the humanoid mechanical armmovement route planning method and system, the search time can be saved, and the sampling point searching speed can be increased.

The invention discloses a parafoil combined track planning method in a complex environment, which divides the parafoil airdrop area into an obstacle area with obstacles and an open and flat circular landing area with the target point as the center; In the area, the fast search random tree path planning algorithm is used to quickly search for feasible trajectories. The termination condition of the search is that the horizontal distance between the location where the path extends and the target landing point is less than or equal to the radius of the circular landing area. In the obstacle area, only Obstacle avoidance task: take the termination state of the track search in the obstacle area as the initial state of the track planning in the circular landing area, and use the segmented homing planning and design in the circular landing area to complete parafoil height control and headwind countermeasures. quasi-task. The invention divides the obstacle avoidance and other requirements that need to be met by parafoil track planning in complex environments into two stages, and at the same time can meet the smooth connection of the two track planning stages, and realizes parafoil navigation in complex environments. trail planning.