Search

CN-122015872-A - Arbitrary shape object track planning method and system based on space-time combination A star

CN122015872ACN 122015872 ACN122015872 ACN 122015872ACN-122015872-A

Abstract

The invention belongs to the technical field of robot motion planning and navigation, and provides a space-time combined A star-based arbitrary shape object track planning method and system, wherein the technical scheme comprises the steps of generating bounding boxes corresponding to all discrete angles and mask information of a robot contour based on a constructed robot polygonal model; defining a four-dimensional state space, initializing a starting point state and a target state, applying a predefined motion primitive to a node with the minimum cost value in the four-dimensional state space to generate a candidate set of subsequent states, extracting a bounding box corresponding to a discrete angle of a current node and mask information of a robot contour from each candidate node of the subsequent states, executing bit operation in a corresponding area of an environment grid map, judging whether collision occurs according to an operation result, backtracking to generate a discrete space-time path when searching reaches the target state or meets a termination condition, interpolating and smoothing the discrete space-time path, and outputting a final executable track.

Inventors

  • ZHOU LELAI
  • Tian Dujie
  • LI YIBIN

Assignees

  • 山东大学

Dates

Publication Date
20260512
Application Date
20260408

Claims (10)

  1. 1. The space-time combined A star-based arbitrary shape object track planning method is characterized by comprising the following steps of: parameterizing and modeling the irregular robot to obtain a robot polygonal model, and generating bounding boxes corresponding to all discrete angles and mask information of the robot outline based on the robot polygonal model; defining a four-dimensional state space comprising a two-dimensional position, a discrete orientation and a time dimension, and initializing a starting point state and a target state; In the four-dimensional state space, aiming at the node with the minimum cost value, a predefined motion primitive is applied to generate a subsequent state candidate set; Extracting bounding boxes corresponding to discrete angles of the current node and mask information of the robot outline aiming at each candidate node in the subsequent state, performing bit operation on corresponding areas of the environment grid map, and judging whether collision occurs according to operation results; When the search reaches the target state or meets the termination condition, backtracking to generate a discrete space-time path, and interpolating and smoothing the discrete space-time path by utilizing a parameterized curve to output a final executable track.
  2. 2. The method for planning the path of the arbitrary shaped object based on the space-time combination A star of claim 1, wherein the parameterized modeling of the irregular shaped robot to obtain the polygonal model of the robot comprises defining the outer contour and all the inner holes of the robot through the ordered vertex sequence set, wherein the outer contour of the robot is formed by a closed outer polygon Zero or more interior hole polygons And each polygon is represented by a set of ordered vertex lists, and the head and tail vertices are coincident to form a closed polygon.
  3. 3. The space-time joint a star-based arbitrary shape object trajectory planning method according to claim 1, wherein the generating a binary mask image of the robot contour corresponding to all discrete angles based on the robot polygon model comprises: Yaw angle range of robot Evenly dividing the yaw angle into N discrete angle intervals, traversing all the discrete angle indexes, and calculating corresponding discrete yaw angles; Performing rotation transformation on the outer contour of the robot and the vertexes of all the inner holes by combining the discrete yaw angles to obtain rotated coordinates; The method comprises the steps of converting the rotated coordinates into pixel dimensions under the specified map resolution, calculating a local bounding box under the current discrete yaw angle by combining the minimum value of the pixel coordinates, and generating a binary mask image of the robot outline under the discrete angle based on the local bounding box.
  4. 4. The space-time joint A star-based arbitrary shape object trajectory planning method of claim 1, wherein the generating a subsequent state candidate set by applying a predefined motion primitive for a node with the minimum cost value in a four-dimensional state space comprises calculating a subsequent coordinate and a new angle index for a propulsion type motion primitive, wherein the position coordinate is unchanged and the angle index is updated for a rotation type motion primitive, wherein the propulsion type motion primitive comprises straight motion along a current course, left-turning arc propulsion and right-turning arc propulsion, and wherein the rotation type motion primitive comprises in-situ left-turning and in-situ right-turning.
  5. 5. A space-time joint a star-based arbitrary shape object trajectory planning method according to claim 3, wherein the specific collision determination process is as follows: According to the position of the candidate sub-node and the local bounding box information, capturing an image of a corresponding region from the environment grid map as a region of interest (ROI); Performing bitwise and operation on the mask image of the angle corresponding to the candidate sub-node and the ROI; and counting the number of non-zero pixels in the bitwise and result image, if the number is larger than zero, judging that collision occurs, otherwise, judging that no collision exists.
  6. 6. The method for planning a trajectory of an arbitrary shaped object based on spatio-temporal joint a-star according to claim 1, characterized in that said interpolating smoothing said discrete spatio-temporal paths with parameterized curves comprises: Estimating velocity for each pair of adjacent points in the discrete space-time path and constructing a velocity vector for each node to adjacent nodes 、 And its velocity vector 、 And after Hermit curves are obtained, uniformly sampling a plurality of points on the local normalization parameters, calculating corresponding continuous positions, generating a high-resolution smooth track point sequence, and obtaining a continuous parameterized track function.
  7. 7. The space-time joint a star-based arbitrary shape object trajectory planning method of claim 6, wherein Hermit curves have the following expression: , Wherein, the For the connection location corresponding to the sampling point, The local normalization parameters are represented as such, In order to provide for the time interval of time, Representing nodes Is used to determine the velocity vector of (a), Representing nodes Is a velocity vector of (a).
  8. 8. Any shape object track planning system based on space-time combination A star, which is characterized by comprising: The irregular object modeling module is used for carrying out parameterization modeling on the robot with irregular shape to obtain a robot polygonal model, and generating bounding boxes corresponding to all discrete angles and mask information of the robot outline based on the robot polygonal model; The system comprises a state candidate set generation module, a state candidate set generation module and a state candidate set generation module, wherein the state candidate set generation module is used for defining a four-dimensional state space comprising a two-dimensional position, a discrete orientation and a time dimension, and initializing a starting point state and a target state; The collision detection module is used for extracting bounding boxes corresponding to the discrete angles of the current nodes and mask information of the robot contours aiming at each candidate node in the subsequent state, performing bit operation on corresponding areas of the environment grid map, and judging whether collision occurs according to operation results; and the track planning module is used for backtracking to generate a discrete space-time path when the search reaches a target state or meets a termination condition, interpolating and smoothing the discrete space-time path by utilizing a parameterized curve and outputting a final executable track.
  9. 9. A computer readable storage medium, on which a computer program is stored, which program, when being executed by a processor, implements the steps of the space-time joint a star based arbitrary shape object trajectory planning method according to any of claims 1-7.
  10. 10. A computer device comprising a memory, a processor and a computer program stored on the memory and executable on the processor, wherein the processor implements the steps of the space-time joint a star-based arbitrary shape object trajectory planning method according to any one of claims 1-7 when the program is executed.

Description

Arbitrary shape object track planning method and system based on space-time combination A star Technical Field The invention belongs to the technical field of robot motion planning and navigation, and particularly relates to a space-time combined A star-based arbitrary shape object track planning method and system. Background The statements in this section merely provide background information related to the present disclosure and may not necessarily constitute prior art. With the rapid development of robotics, navigation and path planning have become core challenges in the fields of mobile robots, robotic arms, and continuum robots. Conventional path planning algorithms such as sampling-based methods (e.g., PRM,) Search-based methods (e.g、) And optimization-based methods (e.g., DWA, MPC) tend to simplify the robot into a regular shape, such as circular, elliptical, or rectangular, when handling robot motions. This simplification, while simplifying the computation, ignores the actual complex geometry of the robot, resulting in the loss of potentially viable solution space in a narrow or dense environment. For example, for robots with non-convex polygonal contours or internal cavities (e.g., mobile platforms with robotic arms or flexible continuum robots), conventional approaches can significantly reduce the flexibility and efficiency of planning by shrinking the feasible area or approximate shape. Furthermore, conventional algorithms typically consider only the spatial dimension (e.g., two-or three-dimensional position and pose), ignoring the temporal dimension. This is acceptable in static environments, but in dynamic environments (e.g., where there are moving obstructions, multi-robot collaboration, or time window constraints) may result in the planning result being either not feasible or too conservative. For example, in a dynamic obstacle scenario, the path may overlap with the movement track of the obstacle, resulting in collisions, and in multi-machine collaboration, ignoring the time sequence may cause resource conflicts or synchronization problems. Existing space-time planning methods, e.g. variants based on space-time RRT or space-timeAlthough the time dimension is introduced, the method is often limited to objects with simple shapes, and the collision detection efficiency is low, so that complex shapes cannot be processed in real time. Collision detection is a bottleneck in path planning. Traditional methods rely on geometric intersection calculations (such as GJK algorithm or SAT test), which are computationally expensive in real-time applications, especially when the object shape is complex. Although the rasterization-based method is efficient, for any shape rotation and displacement, real-time recalculation is required, resulting in increased delay. Methods of pre-computing masks have been used in some areas (e.g., computer graphics) but have not yet been combined with space-timeAnd (5) deeply integrating the algorithm. Disclosure of Invention In order to solve at least one technical problem in the background art, the invention provides a space-time combined A star-based arbitrary shape object track planning method and system, the generated track not only meets the kinematic constraint of a robot, but also can effectively reduce the abrupt steering of a path and improve the tracking precision and the energy efficiency of an executing mechanism. In order to achieve the above purpose, the present invention adopts the following technical scheme: the first aspect of the invention provides a space-time combination A star-based arbitrary shape object track planning method, which comprises the following steps: parameterizing and modeling the irregular robot to obtain a robot polygonal model, and generating bounding boxes corresponding to all discrete angles and mask information of the robot outline based on the robot polygonal model; defining a four-dimensional state space comprising a two-dimensional position, a discrete orientation and a time dimension, and initializing a starting point state and a target state; In the four-dimensional state space, aiming at the node with the minimum cost value, a predefined motion primitive is applied to generate a subsequent state candidate set; Extracting bounding boxes corresponding to discrete angles of the current node and mask information of the robot outline aiming at each candidate node in the subsequent state, performing bit operation on corresponding areas of the environment grid map, and judging whether collision occurs according to operation results; When the search reaches the target state or meets the termination condition, backtracking to generate a discrete space-time path, and interpolating and smoothing the discrete space-time path by utilizing a parameterized curve to output a final executable track. Further, the parameterized modeling of the irregular robot to obtain the robot polygon model includes defining the outer contour and all the inner h