Method of generating a collision free path of travel and computing system

A computing system of an autonomous vehicle, the computing system comprising:

• a grid module configured to:
• determine an obstacle density of a plurality of portions of a global search area based on a global obstacle map associated therewith;
• divide the global search area into grid cells based on a global start position and a desired global target position, wherein a size of each of the grid cells is based on the obstacle density of a corresponding portion,
• iteratively create local search areas,
• each of the local search areas being associated with a subset of the grid cells, the subset of grid cells including a center grid cell and adjacent grid cells surrounding the center grid cell and each of the adjacent grid cells being associated with an obstacle,
• wherein the center grid cell is determined based on a cost function,
• wherein a current search position is associated with the center grid cell, and
• wherein local target positions are associated with the adjacent grid cells and each local target position corresponds to a centroid of free space of a corresponding adjacent grid cell, and
• wherein the cost function comprises a cumulative travel distance between the global start position and the local target position corresponding to a previous adjacent grid cell and a Euclidean distance between the local target position corresponding to the previous adjacent grid cell and the desired global target position;
• a cropping module configured to create a local obstacle map for each of the local search areas based on the global obstacle map;
• a trajectory module configured to calculate, for each of the local target positions a collision free trajectory between a corresponding current search position and the local target position based on a corresponding local obstacle map,
• wherein the grid module is further configured, for each of the local target positions, to update the current search position for the next iteration when the local target position deviates from the desired global target position;
• and
• a path generation module configured to:
• generate a collision free path of travel for the autonomous vehicle from the global start position to the desired global target position based on a set of selected collision free trajectories when the iteration is finished;
• and
• cause the autonomous vehicle to operate according to the collision free path of travel from the global start position to the desired global target position.

A method of generating a collision free path of travel for an autonomous vehicle, the method comprising:

• defining a global search area encompassing at least a global start position and a global target position and that includes a plurality of portions;
• determining a set of collision free trajectories by iteration, the set of collision free trajectories connecting the global start position to the global target position via a local target position, each iteration comprising:
• determining a local search area within the global search area, wherein the local search area includes a plurality of search grid cells comprising a center search grid cell and a plurality of adjacent search grid cells, the center search grid cell being determined based on a cost function;
• generating, based on a global obstacle map corresponding to the global search area, a local obstacle map associated with the local search area;
• determining an obstacle density of each portion associated with the local search area based on the local obstacle map;
• determining a grid resolution of the local search area based on the obstacle density of each portion associated with the local search area, the grid resolution defining a size of each search grid cell of the plurality of search grid cells;
• defining a local start position and a local target position within the local search area, the local target position corresponding to a centroid of free space in an adjacent search grid cell of the plurality of adjacent search grid cells and the cost function comprises a cumulative travel distance between the global start position and the local target position corresponding to a previous adjacent search grid cell and a Euclidean distance between the local target position corresponding to the previous adjacent search grid cell and the global target position;
• and
• calculating, in the local search area, a collision free trajectory for the autonomous vehicle from the local start position to the local target position considering the plurality of search grid cells and the local obstacle map;
• and
• causing the autonomous vehicle to operate according to the determined set of collision free trajectories from the global start position to the global target position.