Granted Patent B2

US 11,003,188 · App. 16/189,593 · Granted May 11, 2021

Inventors: Bradley M. Scott (Mississauga, CA); Peter Arandorenko (Mississauga, CA); Harsoveet Singh (Mississauga, CA); Sadegh Tajeddin (Mississauga, CA)

Assignee: Zebra Technologies Corporation

G05D1/0214G05D1/0088G05D1/0238G05D1/0274G06K9/00805G06T7/62G06T7/70G05D2201/0216G06T2207/30261

Abstract

Claims (53)

1. A method of navigational path planning for a mobile automation apparatus, the method comprising:

obtaining (i) a localization of the mobile automation apparatus in a common frame of reference and (ii) a localization confidence level of the mobile automation apparatus;

detecting an obstacle boundary by one or more sensors disposed on the mobile automation apparatus;

obtaining an obstacle map indicating the detected obstacle boundary in the common frame of reference;

generating a dynamic perimeter region of the detected obstacle boundary, the dynamic perimeter region defining, for a set of distances from the detected obstacle boundary, respective obstruction probabilities according to the localization confidence level;

obtaining a predefined environmental map indicating, in the common frame of reference, a predefined obstacle boundary;

generating, for the predefined obstacle boundary, a static perimeter region defining obstructed space;

identifying an obstructed portion of the dynamic perimeter region based on the obstruction probabilities and the localization of the mobile automation apparatus;

generating a decay perimeter region surrounding the dynamic perimeter region by assigning obstruction probabilities below a predetermined value to each of a plurality of decay sub-regions;

generating a navigational path traversing unobstructed space within the common frame of reference, the unobstructed space excluding (i) the obstructed portion of the dynamic perimeter region, and (ii) the static perimeter region; and

controlling the mobile automation apparatus to traverse the generated navigational path.

2. The method of claim 1 , wherein the dynamic perimeter region includes a plurality of sub-regions, and wherein generating the dynamic perimeter region further comprises assigning an obstruction probability to each sub-region.

3. The method of claim 2 , wherein the sub-regions extend a predefined distance from the obstacle boundary.

4. The method of claim 2 , wherein assigning an obstruction probability comprises, for a corresponding sub-region, determining the obstruction probability according to (i) a distance between the sub-region and the detected obstacle boundary and (ii) the localization confidence level.

5. The method of claim 2 , wherein the obstruction probabilities in the dynamic perimeter region are selected from a range extending from an upper value corresponding to certainty of obstruction to an intermediate value.

6. The method of claim 5 , wherein the intermediate value is the predetermined value.

7. The method of claim 2 , wherein identifying the obstructed portion of the dynamic perimeter region comprises:

selecting a sub-region of the dynamic perimeter region;

determining a distance, in the common frame of reference, from the localization to the selected sub-region;

based on the distance, retrieving an obstruction probability threshold from a memory; and

determining whether the obstruction probability corresponding to the sub-region exceeds the obstruction probability threshold.

8. The method of claim 1 , wherein obtaining the predefined environmental map includes retrieving, from a memory, one of a global static map and a local static map; and

wherein the static perimeter region extends a first distance from the predefined obstacle boundary for the global static map, and a second distance from the predefined obstacle boundary for the local static map.

9. The method of claim 8 , wherein the first distance is greater than the second distance.

10. A mobile automation apparatus for navigational path planning, comprising:

one or more navigational sensors disposed on the mobile automation apparatus;

a memory storing a predefined environmental map indicating, in a common frame of reference, a predefined obstacle boundary;

a navigational controller connected to the memory, the navigational controller including:

a path executor configured to:

obtain, via the one or more navigational sensors, (i) a localization of a mobile automation apparatus in a common frame of reference and (ii) a localization confidence level;

obtain, via the one or more navigational sensors, an obstacle map indicating, in the common frame of reference, an obstacle boundary detected via mobile automation apparatus sensor data;

a perimeter generator configured to: generate a dynamic perimeter region of the obstacle boundary, the dynamic perimeter region defining, for a set of distances from the obstacle boundary, respective obstruction probabilities according to the localization confidence level;

the perimeter generator further configured to generate, for the predefined obstacle boundary, a static perimeter region defining obstructed space;

a path generator further configured to:

retrieve the predefined environmental map;

identify an obstructed portion of the dynamic perimeter region based on the obstruction probabilities and the localization of the mobile automation apparatus;

generate a decay perimeter region surrounding the dynamic perimeter region by assigning obstruction probabilities below a predetermined value to each of a plurality of decay sub-regions; and

generate a navigational path traversing unobstructed space within the common frame of reference, the unobstructed space excluding (i) the obstructed portion of the dynamic perimeter region, and (ii) the static perimeter region;

the path executor further configured to control a locomotive mechanism of the mobile automation apparatus to traverse the generated navigational path.

11. The mobile automation apparatus of claim 10 , wherein the dynamic perimeter region includes a plurality of sub-regions, and wherein the navigational controller is configured, to generate the dynamic perimeter region, to assign an obstruction probability to each sub-region.

12. The mobile automation apparatus of claim 11 , wherein the sub-regions extend a predefined distance from the obstacle boundary.

13. The mobile automation apparatus of claim 11 , wherein the navigational controller is configured, to assign an obstruction probability, to:

for a corresponding sub-region, determine the obstruction probability according to (i) a distance between the sub-region and the obstacle boundary and (ii) the localization confidence level.

14. The mobile automation apparatus of claim 11 , wherein the obstruction probabilities in the dynamic perimeter region are selected from a range extending from an upper value corresponding to certainty of obstruction to an intermediate value.

15. The mobile automation apparatus of claim 14 , wherein the intermediate value is the predetermined value.

16. The mobile automation apparatus of claim 11 , wherein the navigational controller is configured, to identify the obstructed portion of the dynamic perimeter region, to:

select a sub-region of the dynamic perimeter region;

determine a distance, in the common frame of reference, from the localization to the selected sub-region;

based on the distance, retrieve an obstruction probability threshold from the memory; and

determine whether the obstruction probability corresponding to the sub-region exceeds the obstruction probability threshold.

17. The mobile automation apparatus of claim 10 , wherein the navigational controller is configured to retrieve, as the predefined environmental map, one of a global static map and a local static map; and

wherein the static perimeter region extends a first distance from the predefined obstacle boundary for the global static map, and a second distance from the predefined obstacle boundary for the local static map.

18. The mobile automation apparatus of claim 17 , wherein the first distance is greater than the second distance.

Assignments (6)