Aisle-based roadmap generation

• US 10,260,890 B2
• Filed: 04/21/2017
• Issued: 04/16/2019
• Est. Priority Date: 04/21/2017
• Status: Active Grant

• Current Assignee: Boston Dynamics, Inc. (SoftBank Group Corp.)
• Original Assignee: X Development LLC (Alphabet Inc.)
• Inventors: Jose, Alex, Shaffer, Daniel
• Primary Examiner(s): Zalalee, Sultana M
• Application Number:
  US15/494,316
• Publication Number:
  US 20180306591A1
• Time in Patent Office: 725 Days
• CPC Class Codes: G01C 21/383 Indoor data
• CPC Class Codes: G01C 21/3837 Data obtained from a single source
• CPC Class Codes: G01C 21/3848 Data obtained from both position sensors and additional sensors
• CPC Class Codes: G01C 21/3867 Geometry of map features, e.g. shape points, polygons or for simplified maps
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30
• CPC Class Codes: G05D 1/0289 with means for avoiding collisions between vehicles vehicle fittings for automatically controlling speed including means for detecting potential obstacles B60K31/0008; avoiding obstacles by action on the steering system B62D; radar, sonar, lidar systems designed for anti-collision purposes G01S13/93, G01S15/93, G01S17/93
• CPC Class Codes: G06F 30/00 Computer-aided design [CAD]
• CPC Class Codes: G06Q 10/08 Logistics, e.g. warehousing, loading or distribution; Inventory or stock management
• CPC Class Codes: G06T 11/206 Drawing of charts or graphs
• CPC Class Codes: G06V 20/58 Recognition of moving objects or obstacles, e.g. vehicles or pedestrians; Recognition of traffic objects, e.g. traffic signs, traffic lights or roads
• CPC Class Codes: G06V 20/588 Recognition of the road, e.g. of lane markings; Recognition of the vehicle driving pattern in relation to the road

Abstract

Apparatus and methods related to generating roadmaps are provided. A layout of an environment can be displayed on a display. Input data indicative of a plurality of shapes placed on the layout can be received, where each shape corresponds to an aisle of a plurality of aisles. For each aisle, lanes can be generated based on a width of the aisle, and the lanes extend along the aisle such that a robotic device can traverse each lane. An intersection between a first shape and second shape can be identified, where the first and second shape correspond to a first and second aisle. Responsive to identifying the intersection and based on a swept space of the robotic device, a curve that connects a first lane of the first aisle to a second lane of the second aisle can be generated. Then, a roadmap that comprises the aisles and curve can be generated.

Claims

1. A method comprising:

providing, for display on a display device, a fixed structure layout of an environment;

receiving input data indicative of a plurality of shapes placed on the fixed structure layout of the environment, wherein each shape of the plurality corresponds to an aisle of a plurality of aisles;

generating, for each aisle based on a width of the aisle, a number of lanes along the aisle, wherein each lane is traversable by a robotic device;

identifying an intersection between a first shape and a second shape, wherein the first and second shape correspond to a first and second aisle of the plurality;

responsive to identifying the intersection, selecting, from a plurality of predetermined intersection curve templates that correspond to different combinations of numbers of lanes within each aisle, an intersection curve template to connect a first lane of the first aisle to a second lane of the second aisle;

based on a swept space of the robotic device and a non-traversable area associated with each fixed structure, adjusting a curvature of the intersection curve template;

generating a roadmap that comprises the plurality of aisles and the adjusted intersection curve template; and

providing the roadmap for display on the display device.

2. The method of claim 1, wherein the layout is a two-dimensional (2D) computer-aided drawing (CAD) of the environment.

3. The method of claim 1, wherein each shape is placed over a substantially vacant area in the fixed structure layout, and the method further comprises:

based on the input data, fitting each shape into the substantially vacant area such that the shape does not overlap any fixed structures in the fixed structure layout.

4. The method of claim 1, wherein each shape is placed over a substantially vacant area in the fixed structure layout, and the method further comprises:

based on the input data, fitting each shape into the substantially vacant area such that the shape fills any vacant area extending from the substantially vacant area.

5. The method of claim 1, wherein, for each aisle, the number of lanes extend along the aisle up to a threshold distance from each end of the aisle.

6. The method of claim 1, wherein the number of lanes in each aisle is further based on one or more of:

the swept space of the robotic device, a predetermined minimum distance between any two lanes, and a non-traversable area associated with each fixed structure.

7. The method of claim 1, further comprising positioning the number of lanes in the aisle based on one or more of:

the width of the aisle, a predetermined minimum distance between any two lanes, and a non-traversable area associated with each fixed structure.

8. The method of claim 1, further comprising:

generating, for each fixed structure of a particular type, a secondary aisle that leads from the fixed structure to a proximal lane of the plurality of lanes.

9. The method of claim 1, wherein the intersection comprises a first intersection point between (i) a first segment of the first lane, and (ii) a second segment of the second lane, and wherein the intersection curve connects the first segment of the first lane and the second segment of the second lane.

10. The method of claim 9, wherein the intersection further comprises a second intersection point between (i) a third segment of another lane of the first aisle, and (ii) a fourth segment of another lane of the second aisle, wherein the intersection curve is a first intersection curve, and the method further comprises:

generating a second intersection curve that connects the third segment and the fourth segment.

11. The method of claim 10, wherein the first and third segments are parallel, and wherein the first and second intersection curves are oriented different from each other.

12. The method of claim 1, wherein the first lane and the second lane are perpendicular and non-intersecting lanes.

13. The method of claim 1, wherein the intersection curve is a track transition curve.

14. The method of claim 1, wherein a curvature of the intersection curve is based on one or more of:

a turning radius of a robotic device, a maximum speed of the robotic device, and a maximum acceleration of a robotic device.

15. The method of claim 1, further comprising:

based on the roadmap, generating a path for the robotic device to traverse the environment.

16. The method of claim 1, wherein selecting, from a plurality of predetermined intersection curve templates that correspond to different combinations of numbers of lanes within each aisle, an intersection curve template is further based on whether the intersecting lanes are unidirectional or bidirectional.

17. The method of claim 1, wherein the plurality of predetermined intersection curve templates includes at least:

(i) a template corresponding to two lanes in each aisle, (ii) a template corresponding to one lane in each aisle, and (iii) a template corresponding to one lane in the first aisle and a two lanes in the second aisle.

18. A computing device, comprising:

a display device;

one or more processors; and

a control system configured to;

provide, for display on a display device, a fixed structure layout of an environment;

receive input data indicative of a plurality of shapes placed on the layout of the environment, wherein each shape corresponds to an aisle of a plurality of aisles;

generate, for each aisle based on a width of the aisle, a number of lanes along the aisle such that each lane is traversable by a robotic device;

identify an intersection between a first shape and a second shape, wherein the first and second shape correspond to a first and second aisle of the plurality;

responsive to identifying the intersection select, from a plurality of predetermined intersection curve templates corresponding to different combinations of numbers of lanes within each aisle, an intersection curve template to connect a first lane of the first aisle to a second lane of the second aisle;

based on a swept space of the robotic device and a non-traversable area associated with each fixed structure, adjust a curvature of the intersection curve template;

generate a roadmap that comprises the plurality of aisles and the adjusted intersection curve template; and

provide the roadmap for display on the display device.

19. The computing device of claim 18, wherein each shape is placed over a respective substantially vacant area in the fixed structure layout, and wherein the control system is further configured to:

based on the input data, fit each shape into the substantially vacant area such that;

(i) the shape does not overlap any fixed structures in the fixed structure layout, and (ii) the shape fills any vacant area extending from the respective substantially vacant area.

20. A non-transitory computer readable medium having stored thereon instructions, that when executed by one or more processors of a computing device, cause the computing device to perform functions comprising:

providing, for display on a display device, a fixed structure layout of an environment;

receiving input data indicative of a plurality of shapes placed on the layout of the environment, wherein each shape corresponds to an aisle of a plurality of aisles;

generating, for each aisle based on a width of the aisle, a number of lanes along the aisle such that each lane is traversable by a robotic device;

identifying an intersection between a first shape and a second shape, wherein the first and second shape correspond to a first and second aisle of the plurality;

responsive to identifying the intersection based on a number of lanes in the first and second aisle, selecting, from a plurality of predetermined intersection curve templates that correspond to different combinations of numbers of lanes within each aisle, an intersection curve template to connect a first lane of the first aisle to a second lane of the second aisle;

based on a swept space of the robotic device and a non-traversable area associated with each fixed structure, adjusting a curvature of the intersection curve template;

generating a roadmap that comprises the plurality of aisles and the adjusted intersection curve template; and

providing the roadmap for display on the display device.