Time-critical obstacle avoidance path planning in uncertain environments

A system and method for identifying a safe path in a partially unknown environment in a time critical fashion includes identifying long range paths that avoid known obstacles. Short range paths within a receding horizon are identified corresponding to the long range paths, the short range paths avoiding known obstacles and unknown regions. Each short range path is broken into segments based on subsequent control operations or timing, and abort procedures are identified corresponding to each segment to enforce time critical availability of a safe action. Short range paths are excluded unless abort procedures can be identified for subsequent segments.

BACKGROUND

Autonomous aviation applications need to perform onboard sensor-based autonomous path planning which follows a desired path while also avoiding obstacles. When flying in a constrained and uncertain obstacle environment, this capability may be time-critical. Such path planning and obstacle avoidance requires complex, data-dependent software functions, which makes verification timing requirements intractable.

SUMMARY

In one aspect, embodiments of the inventive concepts disclosed herein are directed to a system and method for identifying a safe path in a partially unknown environment in a time critical fashion. Long range paths are identified that avoid known obstacles. Short range paths within a receding horizon are identified corresponding to the long range paths, the short range paths avoiding known obstacles and unknown regions.

In a further aspect, each short range path is broken into segments based on subsequent control operations or timing, and abort procedures are identified corresponding to each segment. Short range paths are excluded unless abort procedures can be identified for subsequent segments.

DETAILED DESCRIPTION

Broadly, embodiments of the inventive concepts disclosed herein are directed to a system and method for identifying a safe path in a partially unknown environment in a time critical fashion includes identifying long range paths that avoid known obstacles. Short range paths within a receding horizon are identified corresponding to the long range paths, the short range paths avoiding known obstacles and unknown regions. Each short range path is broken into segments based on subsequent control operations or timing, and abort procedures are identified corresponding to each segment. Short range paths are excluded unless abort procedures can be identified for subsequent segments.

Referring toFIG.1, a block diagram of a system100for obstacle avoidance path planning according to an exemplary embodiment is shown. The system100includes a 3D world model manager102that accesses and updates a 3D world model database based on historical 3D world model data and sensors such as 3D sensors in a mobile platform.

A path guide planner112receives a desired path (potentially defined by one or more waypoints) and queries the 3D world model manager102to retrieve a partial world map corresponding to the general area of the flight path. The path guide planner112identifies one or more potential long range paths to each of the waypoints. Long range paths may correspond to time frames on the order of an hour. In at least one embodiment, the path guide planner112receives navigationally relevant data from on-board and/or remote sensors such as a radar system, weather reporting system, etc. The path guide planner112identifies obstacles via the navigationally relevant data such as weather related obstacles, physical obstacles, and obstacles related to nearby traffic, and identifies the potential long range paths that avoid those obstacles. It may be appreciated that the potential long range paths may necessarily include segments of unknown availability. The path guide planner112periodically replans the long range paths according to updated navigationally relevant data. For example, segments of unknown availability may be filled in as they get closer.

A receding horizon module114receives the potential long range paths from the path guide planner112and navigationally relevant data. The navigationally relevant data defines a horizon of available data; the receding horizon module114queries the 3D model world manager102for a partial world map corresponding to the area within that horizon and correlates the navigationally relevant data to that partial world map. The receding horizon module114identifies obstacles within the area based on the navigationally relevant data, and unknown regions for which navigationally relevant data is non-existent or so sparse or old that unknown obstacles could exist there. The receding horizon module114then identifies one or more short range paths or receding horizon trajectories within that area and along the long range paths that avoid any identified obstacles and unknown regions or otherwise modifies the long range paths according to the updated navigationally relevant data and stricter obstacle avoidance criteria. Short range paths may correspond to time frames on the order of a minute.

In at least one embodiment, the receding horizon module114enforces high-fidelity vehicle performance limitations to ensure the receding horizon module114can be tracked by a trajectory-based guidance and autopilot function with smaller flight technical error.

In at least one embodiment, the receding horizon module114operates continuously as navigationally relevant data is received and the horizon of available data changes over time to replan new short range paths to reach the waypoints.

In at least one embodiment, time-critical functions106continuously operate to analyze the short range paths. An abort route module108receives navigationally relevant data and queries the 3D world model manager102for a partial world map and generates potential abort options for each segment of each short range path, including braking to hover, loiter at different turn rates, abort path planning, other canned abort actions, etc. To account for vehicle response time, the abort options may initially follow the active trajectory for some time before transitioning to an abort action. Abort trajectory generation may also consider high-fidelity vehicle dynamic limitations Each of these abort trajectories can be collision-detected against the 3D world model manager102.

A safe to proceed module110analyzes each short range path segment and potential abort options to identify and any short range paths lack a potential abort option. In at least one embodiment, the abort route module108and safe to proceed module110are configured to segment each short range path based on some threshold such as time or distance wherein a potential abort option is associated with each segment to ensure a potential abort option is always available.

The safe to proceed module110selects or prioritizes all short range paths that are completely serviced by potential abort options. In at least one embodiment, short range paths may be selected or prioritized based on path efficiency or a safety metric such as availability of redundant abort options. An autopilot application may then use the short range paths.

In at least one embodiment, the 3D world model manager102, path guide planner112, receding horizon module114, abort route module108, and safe to proceed module110are embodiment in software processes executed by an on-board processor.

Referring toFIG.2, a block diagram of timeline of a path planning processes according to an exemplary embodiment is shown. A safe to proceed module periodically analyzes short range paths to determine if abort options are available for upcoming segments whenever new short range path options are identified, for example whenever a receding horizon module receives new navigationally relevant data. During each call period200,202, the safe to proceed module receives potential abort options corresponding to points204,206,208,210,216,218representing discreet locations or discreet times within the short range path and determines at least one abort option exists for the entire duration between adjacent points204,206,208,210,216,218; for example, during a first call period200, the safe to proceed module determines if at least one abort option exists between a first discreet point204and a subsequent second discreet point206along the same short range path. Furthermore, during a subsequent call period202, the safe to proceed module determines if at least one abort option exists between a third discreet point208and a subsequent fourth discreet point210along the same short range path.

Call periods200,202are defined according to near future segments of a short range path such that the safe to proceed analysis is completed for a segment before the segment is actually entered by the mobile platform performing the analysis. For example, before the mobile platform reaches the first discreet point204, the safe to proceed module determines if an abort option exists between the first point204and the second point206; if so, the safe to proceed module may indicate to an autopilot that it is safe to proceed to the first point204. Furthermore, the safe to proceed module may perform the same analysis for every potential point between the first point204and the third point208, when the second call period202performs the same analysis for subsequent points208,210,216. If the safe to proceed module determines during a call period200,202that an abort option does not exist, an abort option identified during a prior call period is executed. For example, during the second call period202, the safe to proceed module may determine that between some interstitial periods202,214, no safe abort option exists. Because the second call period202is executed before the mobile platform reaches the third point208, and because the second call period202is only executed if abort options were available at all times between the first period204and third period208, an existing abort option from the first call period200is executed.

In at least one embodiment, call periods200,202may be executed at a known, regular schedule. Identifying abort options is time critical for safety; therefore a regular schedule ensures that if no abort option exists for a future point204,206,208,210,216,218, a current abort option will be executed.

Call periods200,202are defined according to safety-critical timing requirements while allows for complex functions. In at least one embodiment, a threshold time period may be defined for completion of each call period; if the safe to proceed analysis cannot be completed within the defined time period, the safe to proceed module determines that no abort action will be guaranteed if the platform proceeds further along the current route and a previously determined abort action is still available to execute.

It is believed that the inventive concepts disclosed herein and many of their attendant advantages will be understood by the foregoing description of embodiments of the inventive concepts disclosed, and it will be apparent that various changes may be made in the form, construction, and arrangement of the components thereof without departing from the broad scope of the inventive concepts disclosed herein or without sacrificing all of their material advantages; and individual features from various embodiments may be combined to arrive at other embodiments. The form herein before described being merely an explanatory embodiment thereof, it is the intention of the following claims to encompass and include such changes. Furthermore, any of the features disclosed in relation to any of the individual embodiments may be incorporated into any other embodiment.