# US 2020/0391384 A1 · Path planning for an unmanned vehicle

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2020/0391384 A1
- Document ID: US20200391384A1
- Status: Published application
- Kind: A1
- Application number: 16/753,909
- Filed: 2018-10-15
- Published: 2020-12-17
- Earliest claimed: 2017-10-16
- Assignees: Elta Systems Ltd.
- Applicants: Elta Systems Ltd.
- Inventors: Ofir Cohen; Dina Appelman
- Web page: https://patentgrep.com/patent/US20200391384A1

## CPC

- B25J 9/1666: {Avoiding collision or forbidden zones}
- G01C 21/20: Instruments for performing navigational calculations (G01C21/24, G01C21/26 take precedence)
- B25J 13/089: {Determining the position of the robot with reference to its environment}
- G01C 21/30: Map- or contour-matching
- G05D 1/0212: {with means for defining a desired trajectory (involving a plurality of land vehicles G05D1/0287)}
- G05D 1/0214: {in accordance with safety or protection criteria, e.g. avoiding hazardous areas (monitoring the location of vehicles within a certain area, e.g. forbidden or allowed areas, in traffic control systems for road vehicles G08G1/13)}
- G05D 1/024: {in combination with a laser (lasers per se H01S)}
- G05D 1/0274: {using mapping information stored in a memory device (navigation using map-matching G01C21/30)}
- G05D 1/08: Control of attitude, i.e. control of roll, pitch, or yaw
- G08G 1/16: Anti-collision systems (road vehicle drive control systems for predicting or avoiding probable or impending collision otherwise than by control of a particular sub-unit B60W30/08)
- 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)
- G05D: SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
- G08G: TRAFFIC CONTROL SYSTEMS (guiding railway traffic, ensuring the safety of railway traffic B61L; arrangement of road signs or traffic signals E01F9/00; radar or analogous systems, sonar systems, lidar systems specially adapted for traffic control G01S13/91, G01S15/88, G01S17/88; {radar or analogous systems, sonar systems, lidar systems specially adapted for anti-collision purposes G01S13/93, G01S15/93, G01S17/93})

## Abstract

Thus, according to some examples of the presently disclosed subject matter, in order to reduce path planning time, information that has previously been calculated during planning of a path is reused during planning of other subsequent paths. Using the stored indication reduces time required for planning the path and thus enables to evaluate a greater number of optional paths within a given period of time. This can assist in increasing speed and smoothness of vehicle maneuverability.

## Claims

### Claim 1

A method of path planning for an unmanned vehicle (UV) traversing an area, the method comprising:
operating a scanning device for executing scanning operations, comprising scanning a region within the area, to thereby generate respective scanning output data;
obtaining a map based on the scanning output data, the map representing at least a part of the region, the map is divided into cells, each cell is classified to a class selected from at least two classes, comprising traversable and non-traversable;
based on the map, planning one or more paths for the UV, the planning comprising:
upon determining that the UV is to assume a vehicle within a path of the one or more paths:
querying a data structure; the data structure is configured to maintain one or more entries, each of the entries represents a respective vehicle-state characterized by at least a respective position and heading of the UV, and is indicative of whether the vehicle-state is feasible for the UV; if the data structure comprises an indication corresponding to the vehicle-state, using data stored in association with the vehicle-state for planning the path, otherwise computing and storing the data associated with the vehicle-state; and
selecting a path from the one or more paths.

### Claim 2 (depends on 1)

The method of claim 1, wherein planning one or more paths includes planning two or more paths.

### Claim 3

The method of any one of the preceding claims, further comprising steering the UV in accordance with the path that has been selected.

### Claim 4

The method of any one of the preceding claims, wherein feasibility of the vehicle-state requires that position of the UV at the vehicle-state is not mapped to a non-traversable cell.

### Claim 5

The method of any one of the preceding claims, wherein feasibility of the vehicle-state requires that yaw and pitch angles of the UV comply with one or more predefined criteria.

### Claim 6

The method of any one of the preceding claims, wherein the at least one entry further comprises a weight indicating proximity of the UV to an obstacle when the UV assumes the vehicle-state.

### Claim 7

The method of any one of the preceding claims, wherein the at least one entry is maintained for further maps generated upon receiving further scanning output data.

### Claim 8

The method of any one of the preceding claims further comprising operating the processor for generating the map.

### Claim 9

The method of any one of the preceding claims, wherein the unmanned vehicle is an unmanned ground vehicle.

### Claim 10 (depends on 1, 2, 3, 4, 5, 6, 7, 8)

The method of any one of claims 1 to 8, wherein the unmanned vehicle is an unmanned aerial vehicle.

### Claim 11 (depends on 1, 2, 3, 4, 5, 6, 7, 8)

The method of any one of claims 1 to 8, wherein the unmanned vehicle is an unmanned marine vehicle.

### Claim 12

The method of any one of the preceding claims, further comprising receiving data indicative of a destination of the UV, and wherein the one or more paths are determined from the current position of the UV to the destination.

### Claim 13

The method of any one of the preceding claims further comprising: as the UV advances within the area and new scanning output data of new regions within the area is generated, obtaining an updated map generated and based on the new scanning output data and repeating the planning based on the updated map.

### Claim 14 (depends on 13)

The method of claim 13 further comprising: as the UV advances within the area and new scanning output data of new regions within the area is generated, excluding old regions from the map; and deleting from the data structure vehicle-states that correspond to the old regions.

### Claim 15

A system mountable on an unmanned vehicle (UV), comprising:
a processing unit configured and operable to:
receive scanning output data, the scanning output data is a product of scanning operations executed by a scanning device on-board the UV and include scanning a region within the area;
obtain a map based on the scanning output data, the map representing at least a segment of the region, the map is divided into cells, each cell is classified to a class selected from at least two classes, comprising traversable and non-traversable;
based on the map, planning at least one path for the UV, the planning comprising:
upon determining that within one of the at least one path, the UV is to assume a vehicle-state:
query a data structure configured to keep one or more entries, each of the entries indicating whether a respective vehicle-state is feasible for the UV, the vehicle-state being associated with at least a respective position and heading of the UV; if the data structure comprises an indication corresponding to the vehicle-state, using data stored in association with the vehicle-state for planning the path, otherwise computing and storing the data associated with the vehicle-state; and
select a path for the UV.

### Claim 16 (depends on 15)

The system of claim 15, wherein the at least one path is at least two paths.

### Claim 17 (depends on 15, 16)

The system of any one of claims 15 to 16, wherein the processing unit is further configured to generate steering commands for steering the UV in accordance with the path.

### Claim 18 (depends on 15, 16, 17)

The system of any one of claims 15 to 17, wherein feasibility of the vehicle-state requires that position of the UV when assuming the vehicle-state is not mapped to a non-traversable cell.

### Claim 19 (depends on 15, 16, 17, 18)

The system of any one of claims 15 to 18, wherein feasibility of the vehicle-state requires that yaw and pitch angles of the UV when the UV assumes the vehicle-state comply with one or more predefined criteria.

### Claim 20 (depends on 15, 16, 17, 18, 19)

The system of any one of claims 15 to 19, wherein the at least one entry further comprises a weight indicating proximity of the UV to an obstacle when the UV assumes the vehicle-state.

### Claim 21 (depends on 15, 16, 17, 18, 19, 20)

The system of any one of claims 15 to 20, wherein the at least one entry further comprises a weight indicating incline of the UV, when the UV assumes the vehicle-state.

### Claim 22 (depends on 15, 16, 17, 18, 19, 20, 21)

The system of any one of claims 15 to 21, wherein the at least one entry further comprises a weight indicating the UV having presence at an undesired location, when the UV assumes the vehicle-state.

### Claim 23 (depends on 15, 16, 17, 18, 19, 20, 21, 22)

The system of any one of claims 15 to 22, wherein the at least one entry is maintained for further maps generated upon receiving further scanning output data.

### Claim 24 (depends on 15, 16, 17, 18, 19, 20, 21, 22, 23)

The system of any one of claims 15 to 23, wherein the processing unit is further configured and operable to generate the map in real-time based on the scanning output data.

### Claim 25 (depends on 15, 16, 17, 18, 19, 20, 21, 22, 23, 24)

The system of any one of claims 15 to 24, wherein the processing unit is further configured and operable to receive data indicative of a destination of the UV, and wherein the one or more paths are determined from the current position of the UV to the destination.

### Claim 26 (depends on 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25)

The system of any one of claims 15 to 25, wherein, as the UV advances within the area and new scanning output data of new regions within the area is generated, the processing unit is further configured and operable to obtain an updated map generated based on the new scanning output data and repeat the planning based on the updated map.

### Claim 27 (depends on 26)

The system of claim 26, wherein, as the UV advances within the area and new scanning output data of new regions within the area is generated, the processing unit is further configured to exclude old regions from the map; and delete from the data structure vehicle-states that correspond to the old regions.

### Claim 28

An unmanned vehicle (UV), comprising: a scanning device and a processing unit comprising one or more processing circuitries; the scanning device is configured and operable to scan a region surrounding the UV within an area traversed by the UV to thereby provide scanning output data providing information about distances between objects in the region and the UV in a multiplicity of directions; the processing unit is configured and operable to:
generate a map based on the scanning output data, the map representing at least a part of the region, the map is divided into cells, each cell is classified to a class selected from two or more classes, comprising traversable and non-traversable; receiving data indicative of a destination of the UV; and, based on the map, planning one or more paths to a destination for of the UV,
the planning comprising: upon determining that within a path of the one or more paths the UV is to assume a vehicle-state:
querying a data structure, stored in a computer storage device operatively connected to the processing unit, configured to maintain information indicating whether a respective vehicle-state is feasible for the UV, the vehicle-state being associated with at least a respective position and heading of the UV; if the data structure comprises an indication corresponding to the vehicle-state, using data stored in association with the vehicle-state for planning the path, otherwise computing and storing the data associated with the vehicle-state; and selecting a path from the one or more paths.

### Claim 29 (depends on 28)

The UV of claim 28 is an unmanned ground vehicle.

### Claim 30 (depends on 28)

The UV of claim 28 is an unmanned aerial vehicle.

### Claim 31 (depends on 28)

The UV of claim 28 is an unmanned marine vehicle.

### Claim 32

A non-transitory computer readable storage medium retaining a program of instructions, the program of instructions when read by a computer, cause the computer to perform a method of path planning for an unmanned vehicle (UV), comprising:
obtaining a map based on scanning output data; the scanning output data is a product of scanning operations executed by a scanning device on-board the UV, during which a region within an area traversed by the UV is scanned; the map is divided into cells, each cell is classified to a class selected from two or more classes, comprising traversable and non-traversable;
based on the map, planning two or more paths to a destination of the UV, the planning comprising:
upon determining that within a path of the two or more paths, the UV is to assume a vehicle-state: query a data structure configured to maintain information indicating whether a respective vehicle-state is feasible for the UV, the vehicle-state being associated with at least a respective position and heading of the UV; if the data structure comprises an indication corresponding to the vehicle-state, using data stored in association with the vehicle-state for planning the path, otherwise computing and storing the data associated with the vehicle-state; and selecting a path from the two or more paths.