# US 12,001,210 B2 · Semantic obstacle recognition for path planning > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,001,210 B2 - Document ID: US12001210B2 - Status: Granted - Kind: B2 - Application number: 17/814,738 - Filed: 2022-07-25 - Published: 2022-11-17 - Granted: 2024-06-04 - Earliest claimed: 2017-12-19 - Assignees: Google Inc. - Applicants: Google LLC - Inventors: David Millard; Mikael Persson - Web page: https://patentgrep.com/patent/US12001210B2 ## CPC - G05D 1/633: Dynamic obstacles - B25J 9/0003: {Home robots, i.e. small robots for domestic use} - B25J 9/1666: {Avoiding collision or forbidden zones} - G01C 21/20: Instruments for performing navigational calculations (G01C21/24, G01C21/26 take precedence) - G01C 21/206: {specially adapted for indoor navigation} - G05D 1/00: Control of position, course, altitude or attitude of land, water, air or space vehicles, e.g. using automatic pilots (drive control systems specially adapted for autonomous road vehicles B60W60/00) - G05D 1/0217: {in accordance with energy consumption, time reduction or distance reduction criteria} - G05D 1/024: {in combination with a laser (lasers per se H01S)} - G05D 1/0246: {using a video camera in combination with image processing means} - G05D 1/0274: {using mapping information stored in a memory device (navigation using map-matching G01C21/30)} - G05D 1/227: Handing over between remote control and on-board control; Handing over between remote control arrangements - G05D 1/246: using environment maps, e.g. simultaneous localisation and mapping [SLAM] - G05D 1/247: using signals provided by artificial sources external to the vehicle, e.g. navigation beacons - G05D 1/249: from positioning sensors located off-board the vehicle, e.g. from cameras - G05D 1/617: Safety or protection, e.g. defining protection zones around obstacles or avoiding hazards (arrangements for controlling the position or course of two or more vehicles for avoiding collisions therebetween G05D1/693; arrangements for reacting to or preventing system or operator failure G05D1/80) - G05D 1/644: Optimisation of travel parameters, e.g. of energy consumption, journey time or distance - G05D 1/65: Following a desired speed profile - G06N 3/08: Learning methods - G06V 20/10: Terrestrial scenes (scenes under surveillance with static cameras G06V20/52; scenes perceived from the exterior of a vehicle G06V20/56; scenes perceived from the interior of a vehicle G06V20/59) - G01C 21/3453: {Special cost functions, i.e. other than distance or default speed limit of road segments} - G05D 2101/15: using machine learning, e.g. neural networks - Y10S 901/01: Mobile robot - Y10S 901/47: Optical - G05D: SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES - B25J: MANIPULATORS; CHAMBERS PROVIDED WITH MANIPULATION DEVICES ({manipulators specially adapted for use in surgery A61B34/70; manipulators used in cleaning hollow articles B08B9/04}; manipulators associated with rolling mills B21B39/20; manipulators associated with forging machines B21J13/10; {manipulators associated with picking-up and placing mechanisms B23P19/007}; means for holding wheels or parts thereof B60B30/00; {vehicles with ground-engaging propulsion means, e.g. walking members B62D57/02, B62D57/032; devices for picking-up and depositing articles or materials between conveyors B65G47/90, B65G47/91; manipulators with gripping or holding means for transferring packages B65H67/065}; cranes B66C; {manipulators used in the protection or supervision of pipe-line installations F17D5/00; walking equipment adapted for nuclear steam-generators F22B37/006}; manipulators specially adapted for, or associated with, nuclear reactors G21C; {apparatus used for handling wafers during manufacture or treatment of semiconductor H10P72/50}) - G01C: MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY (measuring liquid level G01F; radio navigation, determining distance or velocity by use of propagation effects, e.g. Doppler effects, propagation time, of radio waves, analogous arrangements using other waves G01S) - G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS - G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING - Y10S: TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS ## Abstract Systems, methods, devices, and techniques for planning travel of an autonomous robot. A system identifies one or more obstacles that are located in proximity of at least a portion of a planned route for the autonomous robot. For each obstacle, the system: (i) determines a semantic class of the obstacle, including selecting the semantic class from a library that defines a set of multiple possible semantic classes for obstacles, and (ii) selects a planning policy for the obstacle that corresponds to the semantic class of the obstacle. The system can generate a trajectory along the at least the portion of the planned route using the selected planning policies. The robot can then initiate travel according to the trajectory. ## Claims ### Claim 1 A computer-implemented method, comprising: identifying, by a computing system, one or more obstacles that are located in proximity of at least a portion of a planned route for an autonomous robot; for each obstacle: (i) determining a semantic class of the obstacle, including selecting the semantic class from a library that defines a plurality of possible semantic classes for obstacles, wherein the library comprises a hierarchical representation of the plurality of possible semantic classes and wherein the library includes a database that includes increasingly specialized planning policies for classes represented further down the hierarchy, each planning policy describing at least one constraint with respect to travel of the autonomous robot relative to the obstacle, wherein selecting the semantic class of the obstacle comprises traversing the hierarchical representation of the plurality of possible semantic classes to locate a most-specific semantic class for the obstacle, and (ii) selecting a planning policy for the obstacle that corresponds to the semantic class of the obstacle; generating, by the computing system, a trajectory along the at least the portion of the planned route for the autonomous robot, the trajectory being based on the constraints described by the planning policies for the one or more obstacles located in proximity of the at least the portion of the planned route; and initiating travel of the autonomous robot according to the trajectory. ### Claim 2 (depends on 1) The computer-implemented method of claim 1, wherein the most-specific semantic class for the obstacle identifies the obstacle as a particular instance of an object within a higher-level semantic class for the obstacle. ### Claim 3 (depends on 1) The computer-implemented method of claim 1, wherein each semantic class in the hierarchical representation is linked to a corresponding class signature that characterizes one or more features of objects in the semantic class. ### Claim 4 (depends on 1) The computer-implemented method of claim 1, wherein the library identifies a respective planning policy for each semantic class of the plurality of possible semantic classes, and the respective planning policies for at least a subset of the plurality of possible semantic classes describe different constraints from each other. ### Claim 5 (depends on 1) The computer-implemented method of claim 1, wherein generating the trajectory along the at least the portion of the planned route for the autonomous robot comprises determining a trajectory that optimizes a trajectory cost function, the trajectory cost function being based on the respective cost functions for the one or more obstacles located in proximity of the at least the portion of the planned route. ### Claim 6 (depends on 1) The computer-implemented method of claim 1, wherein the semantic class of a first obstacle of the one or more obstacles that are located in proximity of the at least the portion of the planned route for the autonomous robot identifies the first obstacle as a person. ### Claim 7 (depends on 6) The computer-implemented method of claim 6, wherein the semantic class of a second obstacle of the one or more obstacles that are located in proximity of the at least the portion of the planned route for the autonomous robot identifies the second obstacle as an inanimate object. ### Claim 8 (depends on 1) The computer-implemented method of claim 1, further comprising: after initiating travel of the autonomous robot according to the trajectory, but before completing the travel, generating an updated trajectory; and initiating travel of the autonomous robot according to the updated trajectory before completing the travel of the autonomous robot according to the trajectory. ### Claim 9 (depends on 1) The computer-implemented method of claim 1, wherein identifying the one or more obstacles that are located in proximity of the at least the portion of the planned route for the autonomous robot comprises detecting the one or more obstacles in a representation of an environment of the autonomous robot, the representation of the environment generated using sensor data from one or more sensors of the autonomous robot, the one or more sensors including at least one of a camera system or a light detection and ranging (LIDAR) system. ### Claim 10 (depends on 1) The computer-implemented method of claim 1, wherein the at least one constraint comprises a cost function that defines a cost of travel of the autonomous robot as a function of a distance between the autonomous robot and the obstacle. ### Claim 11 (depends on 1) The computer-implemented method of claim 1, wherein the at least one constraint comprises a cost function that defines a cost of travel of the autonomous robot as a function of a speed of the autonomous robot at various distances from the obstacle during the travel of the autonomous robot. ### Claim 12 (depends on 1) The computer-implemented method of claim 1, further comprising selecting a semantic class and a corresponding planning policy that applies to a group of obstacles. ### Claim 13 A computing system, comprising: one or more processors; and one or more computer-readable media having instructions stored thereon that, when executed by the one or more processors, cause the one or more processors to perform operations comprising: identifying one or more obstacles that are located in proximity of at least a portion of a planned route for an autonomous robot; for each obstacle: (i) determining a semantic class of the obstacle, including selecting the semantic class from a library that defines a plurality of possible semantic classes for obstacles, wherein the library comprises a hierarchical representation of the plurality of possible semantic classes and wherein the library includes a database that includes increasingly specialized planning policies for classes represented further down the hierarchy, each planning policy describing at least one constraint with respect to travel of the autonomous robot relative to the obstacle, wherein selecting the semantic class of the obstacle comprises traversing the hierarchical representation of the plurality of possible semantic classes to locate a most-specific semantic class for the obstacle, and (ii) selecting a planning policy for the obstacle that corresponds to the semantic class of the obstacle; generating a trajectory along the at least the portion of the planned route for the autonomous robot, the trajectory being based on the constraints described by the planning policies for the one or more obstacles located in proximity of the at least the portion of the planned route; and initiating travel of the autonomous robot according to the trajectory. ### Claim 14 (depends on 13) The computing system of claim 13, wherein the most-specific semantic class for the obstacle identifies the obstacle as a particular instance of an object within a higher-level semantic class for the obstacle. ### Claim 15 (depends on 13) The computing system of claim 13, wherein each semantic class in the hierarchical representation is linked to a corresponding class signature that characterizes one or more features of objects in the semantic class. ### Claim 16 (depends on 13) The computing system of claim 13, wherein the library identifies a respective planning policy for each semantic class of the plurality of possible semantic classes, and the respective planning policies for at least a subset of the plurality of possible semantic classes describe different constraints from each other. ### Claim 17 (depends on 13) The computing system of claim 13, wherein generating the trajectory along the at least the portion of the planned route for the autonomous robot comprises determining a trajectory that optimizes a trajectory cost function, the trajectory cost function being based on the respective cost functions for the one or more obstacles located in proximity of the at least the portion of the planned route. ### Claim 18 One or more non-transitory computer-readable media having instructions stored thereon that, when executed by one or more processors, cause the one or more processors to perform operations comprising: identifying one or more obstacles that are located in proximity of at least a portion of a planned route for an autonomous robot; for each obstacle: (i) determining a semantic class of the obstacle, including selecting the semantic class from a library that defines a plurality of possible semantic classes for obstacles, wherein the library comprises a hierarchical representation of the plurality of possible semantic classes and wherein the library includes a database that includes increasingly specialized planning policies for classes represented further down the hierarchy, each planning policy describing at least one constraint with respect to travel of the autonomous robot relative to the obstacle, wherein selecting the semantic class of the obstacle comprises traversing the hierarchical representation of the plurality of possible semantic classes to locate a most-specific semantic class for the obstacle, and (ii) selecting a planning policy for the obstacle that corresponds to the semantic class of the obstacle; generating a trajectory along the at least the portion of the planned route for the autonomous robot, the trajectory being based on the constraints described by the planning policies for the one or more obstacles located in proximity of the at least the portion of the planned route; and initiating travel of the autonomous robot according to the trajectory.