# US 12,001,212 B2 · Path planning method and device for unmanned device

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

- Number: US 12,001,212 B2
- Document ID: US12001212B2
- Status: Granted
- Kind: B2
- Application number: 17/271,426
- Filed: 2019-08-06
- Published: 2021-10-07
- Granted: 2024-06-04
- Earliest claimed: 2018-09-20
- Assignees: Beijing Jingdong Shangke Information Technology Co., Ltd.; Beijing Jingdong Century Trading Co., Ltd.
- Applicants: Beijing Jingdong Shangke Information Technology Co, Ltd.; Beijing Jingdong Century Trading Co., Ltd.
- Inventors: Song Han
- Web page: https://patentgrep.com/patent/US12001212B2

## CPC

- 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/0234: {using optical markers or beacons (optical beacons per se G01S1/70)}
- B60W 60/0011: {involving control alternatives for a single driving scenario, e.g. planning several paths to avoid obstacles}
- G05D 1/0272: {comprising means for registering the travel distance, e.g. revolutions of wheels (measuring distance traversed on the ground by vehicles, e.g. using odometers G01C22/00)}
- G05D 1/0274: {using mapping information stored in a memory device (navigation using map-matching G01C21/30)}
- G05D 1/246: using environment maps, e.g. simultaneous localisation and mapping [SLAM]
- 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
- G06Q 10/047: Optimisation of routes or paths, e.g. travelling salesman problem
- G06Q 10/06315: {Needs-based resource requirements planning or analysis}
- G06Q 10/06316: {Sequencing of tasks or work}
- G06Q 10/08: Logistics, e.g. warehousing, loading or distribution; Inventory or stock management
- G06Q 10/08743: {using optimisation of routes}
- G05D: SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
- B60W: CONJOINT CONTROL OF VEHICLE SUB-UNITS OF DIFFERENT TYPE OR DIFFERENT FUNCTION; CONTROL SYSTEMS SPECIALLY ADAPTED FOR HYBRID VEHICLES; ROAD VEHICLE DRIVE CONTROL SYSTEMS FOR PURPOSES NOT RELATED TO THE CONTROL OF A PARTICULAR SUB-UNIT
- G06Q: INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR

## Abstract

A path planning method for an unmanned device includes taking a current landmark as a current node, obtaining a landmark corresponding to a product to be picked with a route closest to the current node, and taking the obtained landmark as the current node, wherein an initial value of the current node is an initial landmark of the unmanned device; determining whether the current node is a landmark corresponding to the last product to be picked; if no, performing the step of obtaining a landmark corresponding to a product to be picked with a route closest to the current node; and if yes, taking a route composed of the initial landmark of the unmanned device and landmarks corresponding to products to be picked that are selected sequentially as a travel route of the unmanned device.

## Claims

### Claim 1

A path planning method for an unmanned device, comprising:
determining a location of each landmark within a warehouse;
mapping each landmark within the warehouse to a two-dimensional matrix map;
determining a coordinate of an initial landmark of the unmanned device in the two-dimensional matrix map, and coordinates of a landmark corresponding to any one product to be picked in the two-dimensional matrix map;
calculating a route distance from the initial landmark of the unmanned device to the landmark corresponding to the any one product to be picked and a route distance between landmarks corresponding to any two products to be picked according to coordinate values;
taking a current landmark as a current node, obtaining a landmark corresponding to a product to be picked with a route closest to the current node, and taking the obtained landmark corresponding to the product to be picked as the current node, wherein an initial value of the current node is the initial landmark of the unmanned device;
determining whether the current node is a landmark corresponding to a last product to be picked;
if YES, stopping performing a step of obtaining the landmark corresponding to the product to be picked with the route closest to the current node, and taking the obtained landmark corresponding to the product to be picked as the current node again; if NO, performing the step of obtaining the landmark corresponding to the product to be picked with the route closest to the current node, and taking the obtained landmark corresponding to the product to be picked as the current node repeatedly; and
taking a route composed of the initial landmark of the unmanned device and landmarks corresponding to products to be picked that are selected sequentially as a travel path of the unmanned device, wherein the calculating the route distance from the initial landmark of the unmanned device to the landmark corresponding to the any one product to be picked comprises:
calculating a coordinate distance between the initial landmark of the unmanned device and the landmark corresponding to the any one product to be picked in the two-dimensional matrix map;
determining whether the initial landmark of the unmanned device and the landmark corresponding to the any one product to be picked are located between a same two adjacent main lanes if the initial landmark of the unmanned device and the landmark corresponding to the any one product to be picked are located in different shelf lanes;
determining a number of first landmarks from the initial landmark of the unmanned device to a first main lane in the two adjacent main lanes, a number of second landmarks from the initial landmark of the unmanned device to a second main lane in the two adjacent main lanes, a number of third landmarks from the landmark corresponding to the any one product to be picked to the first main lane, and a number of fourth landmarks from the landmark corresponding to the any one product to be picked to the second main lane;
calculating a sum of the number of first landmarks and the number of third landmarks, and a sum of the number of second landmarks and the number of fourth landmarks if the initial landmark of the unmanned device and the landmark corresponding to the any one product to be picked are located between the same two adjacent main lanes; and
adding a value corresponding to a smaller sum of the numbers of landmarks in the two sums of the numbers of landmarks in the two-dimensional matrix map to the coordinate distance to obtain the route distance from the initial landmark of the unmanned device to the landmark corresponding to the any one product to be picked.

### Claim 2 (depends on 1)

The path planning method for the unmanned device according to claim 1, wherein:
the coordinate distance is taken as the route distance from the initial landmark of the unmanned device to the landmark corresponding to the any one product to be picked if the initial landmark of the unmanned device and the landmark corresponding to the any one product to be picked are not located between the same two adjacent main lanes.

### Claim 3 (depends on 1)

The path planning method for the unmanned device according to claim 1, wherein the calculating the route distance between the landmarks corresponding to the any two products to be picked according to the coordinate values comprises:
calculating a coordinate distance between the landmarks corresponding to the any two products to be picked in the two-dimensional matrix map;
determining whether the landmarks corresponding to the any two products to be picked are located between the same two adjacent main lanes if the landmarks corresponding to the any two products to be picked are located in different shelf lanes;
determining a number of first landmarks from the landmark corresponding to a first product to be picked in the any two products to be picked to the first main lane in the two adjacent main lanes, a number of second landmarks from the landmark corresponding to the first product to be picked to the second main lane in the two adjacent main lanes, a number of third landmarks from the landmark corresponding to a second product to be picked in the any two products to be picked to the first main lane, and a number of fourth landmarks from the landmark corresponding to the second product to be picked to the second main lane;
calculating a second sum of the number of first landmarks and the number of third landmarks, and a second sum of the number of second landmarks and the number of fourth landmarks if the landmarks corresponding to the any two products to be picked are located between the same two adjacent main lanes and located in different shelf lanes; and
adding a value corresponding to a smaller second sum of the numbers of landmarks in the two second sums of the numbers of landmarks in the two-dimensional matrix map to the coordinate distance to obtain the route distance between the landmarks corresponding to the any two products to be picked.

### Claim 4 (depends on 3)

The path planning method for the unmanned device according to claim 3, wherein:
the coordinate distance is taken as the route distance between the landmarks corresponding to the any two products to be picked if the landmarks corresponding to the any two products to be picked are not located between the same two adjacent main lanes.

### Claim 5 (depends on 1)

The path planning method for the unmanned device according to claim 1, further comprising:
selecting an optimal path among a plurality of travel paths according to an initial starting point of a next planned path if the plurality of travel paths of the unmanned device are selected.

### Claim 6 (depends on 5)

The path planning method for the unmanned device according to claim 5, wherein the selecting the optimal path among the plurality of travel paths according to the initial starting point of the next planned path comprises:
selecting a travel path among the plurality of travel paths, where the landmark corresponding to the last product to be picked is closest to the initial starting point of the next planned path, as the optimal path.

### Claim 7 (depends on 6)

The path planning method for the unmanned device according to claim 6, further comprising:
selecting a travel path among the plurality of travel paths, where the landmark corresponding to the last product to be picked is closest to the initial landmark, as the optimal path, if a next step is routed for the unmanned device to return to the initial landmark.

### Claim 8

A path planning device for an unmanned device, comprising:
a memory; and
a processor coupled to the memory, wherein the processor is configured to execute a path planning method for the unmanned device, comprising:
determining a location of each landmark within a warehouse;
mapping each landmark within the warehouse to a two-dimensional matrix map;
determining a coordinate of an initial landmark of the unmanned device in the two-dimensional matrix map, and coordinates of a landmark corresponding to any one product to be picked in the two-dimensional matrix map;
calculating a route distance from the initial landmark of the unmanned device to the landmark corresponding to the any one product to be picked and a route distance between landmarks corresponding to any two products to be picked according to coordinate values;
taking a current landmark as a current node, obtaining a landmark corresponding to a product to be picked with a route closest to the current node, and taking the obtained landmark corresponding to the product to be picked as the current node, wherein an initial value of the current node is the initial landmark of the unmanned device;
determining whether the current node is a landmark corresponding to a last product to be picked;
if YES, stopping performing a step of obtaining the landmark corresponding to the product to be picked with the route closest to the current node, and taking the obtained landmark corresponding to the product to be picked as the current node again; if NO, performing the step of obtaining the landmark corresponding to the product to be picked with the route closest to the current node, and taking the obtained landmark corresponding to the product to be picked as the current node repeatedly; and
taking a route composed of the initial landmark of the unmanned device and landmarks corresponding to products to be picked that are selected sequentially as a travel path of the unmanned device, wherein the calculating the route distance from the initial landmark of the unmanned device to the landmark corresponding to the any one product to be picked comprises:
calculating a coordinate distance between the initial landmark of the unmanned device and the landmark corresponding to the any one product to be picked in the two-dimensional matrix map;
determining whether the initial landmark of the unmanned device and the landmark corresponding to the any one product to be picked are located between a same two adjacent main lanes if the initial landmark of the unmanned device and the landmark corresponding to the any one product to be picked are located in different shelf lanes;
determining a number of first landmarks from the initial landmark of the unmanned device to a first main lane in the two adjacent main lanes, a number of second landmarks from the initial landmark of the unmanned device to a second main lane in the two adjacent main lanes, a number of third landmarks from the landmark corresponding to the any one product to be picked to the first main lane, and a number of fourth landmarks from the landmark corresponding to the any one product to be picked to the second main lane;
calculating a sum of the number of first landmarks and the number of third landmarks, and a sum of the number of second landmarks and the number of fourth landmarks if the initial landmark of the unmanned device and the landmark corresponding to the any one product to be picked are located between the same two adjacent main lanes; and
adding a value corresponding to a smaller sum of the numbers of landmarks in the two sums of the numbers of landmarks in the two-dimensional matrix map to the coordinate distance to obtain the route distance from the initial landmark of the unmanned device to the landmark corresponding to the any one product to be picked.

### Claim 9 (depends on 8)

The path planning device for the unmanned device according to claim 8, wherein the calculating the route distance from the initial landmark of the unmanned device to the landmark corresponding to the any one product to be picked further comprises:
taking the coordinate distance as the route distance from the initial landmark of the unmanned device to the landmark corresponding to the any one product to be picked if the initial landmark of the unmanned device and the landmark corresponding to the any one product to be picked are not located between the same two adjacent main lanes.

### Claim 10 (depends on 8)

The path planning device for the unmanned device according to claim 8, wherein the calculating the route distance between the landmarks corresponding to the any two products to be picked according to the coordinate values comprises:
calculating a coordinate distance between the landmarks corresponding to the any two products to be picked in the two-dimensional matrix map;
determining whether the landmarks corresponding to the any two products to be picked are located between the same two adjacent main lanes if the landmarks corresponding to the any two products to be picked are located in different shelf lanes;
determining a number of first landmarks from the landmark corresponding to a first product to be picked in the any two products to be picked to the first main lane in the two adjacent main lanes, a number of second landmarks from the landmark corresponding to the first product to be picked to the second main lane in the two adjacent main lanes, a number of third landmarks from the landmark corresponding to a second product to be picked in the any two products to be picked to the first main lane, and a number of fourth landmarks from the landmark corresponding to the second product to be picked to the second main lane;
calculating a second sum of the number of first landmarks and the number of third landmarks, and a second sum of the number of second landmarks and the number of fourth landmarks if the landmarks corresponding to the any two products to be picked are located between the same two adjacent main lanes and located in different shelf lanes; and
adding a value corresponding to a smaller second sum of the numbers of landmarks in the two second sums of the numbers of landmarks in the two-dimensional matrix map to the coordinate distance to obtain the route distance between the landmarks corresponding to the any two products to be picked.

### Claim 11 (depends on 10)

The path planning device for the unmanned device according to claim 10, wherein the calculating the route distance between the landmarks corresponding to the any two products to be picked according to the coordinate values further comprises:
taking the coordinate distance as the route distance between the landmarks corresponding to the any two products to be picked if the landmarks corresponding to the any two products to be picked are not located between the same two adjacent main lanes.

### Claim 12 (depends on 8)

The path planning device for the unmanned device according to claim 8, wherein the path planning method for the unmanned device further comprises:
selecting an optimal path among a plurality of travel paths according to an initial starting point of a next planned path if the plurality of travel paths of the unmanned device are selected.

### Claim 13 (depends on 12)

The path planning method for the unmanned device according to claim 12, wherein the selecting the optimal path among the plurality of travel paths according to the initial starting point of the next planned path comprises:
selecting a travel path among the plurality of travel paths, where the landmark corresponding to the last product to be picked is closest to the initial starting point of the next planned path, as the optimal path.

### Claim 14 (depends on 13)

The path planning device for the unmanned device according to claim 13, wherein the path planning method for the unmanned device further comprises:
selecting a travel path among the plurality of travel paths, where the landmark corresponding to the last product to be picked is closest to the initial landmark, as the optimal path, if a next step is routed for the unmanned device to return to the initial landmark.

### Claim 15

A non-transitory computer readable storage medium, wherein the non-transitory computer readable storage medium stores computer program instructions which, when executed by a processor, implement a path planning method for an unmanned device, comprising:
determining a location of each landmark within a warehouse;
mapping each landmark within the warehouse to a two-dimensional matrix map;
determining a coordinate of an initial landmark of the unmanned device in the two-dimensional matrix map, and coordinates of a landmark corresponding to any one product to be picked in the two-dimensional matrix map;
calculating a route distance from the initial landmark of the unmanned device to the landmark corresponding to the any one product to be picked and a route distance between landmarks corresponding to any two products to be picked according to coordinate values;
taking a current landmark as a current node, obtaining a landmark corresponding to a product to be picked with a route closest to the current node, and taking the obtained landmark corresponding to the product to be picked as the current node, wherein an initial value of the current node is the initial landmark of the unmanned device;
determining whether the current node is a landmark corresponding to s last product to be picked;
if YES, stopping performing a step of obtaining the landmark corresponding to the product to be picked with the route closest to the current node, and taking the obtained landmark corresponding to the product to be picked as the current node again; if NO, performing the step of obtaining the landmark corresponding to the product to be picked with the route closest to the current node, and taking the obtained landmark corresponding to the product to be picked as the current node repeatedly; and
taking a route composed of the initial landmark of the unmanned device and landmarks corresponding to products to be picked that are selected sequentially as a travel path of the unmanned device, wherein the calculating the route distance from the initial landmark of the unmanned device to the landmark corresponding to the any one product to be picked comprises:
calculating a coordinate distance between the initial landmark of the unmanned device and the landmark corresponding to the any one product to be picked in the two-dimensional matrix map;
determining whether the initial landmark of the unmanned device and the landmark corresponding to the any one product to be picked are located between a same two adjacent main lanes if the initial landmark of the unmanned device and the landmark corresponding to the any one product to be picked are located in different shelf lanes;
determining a number of first landmarks from the initial landmark of the unmanned device to a first main lane in the two adjacent main lanes, a number of second landmarks from the initial landmark of the unmanned device to a second main lane in the two adjacent main lanes, a number of third landmarks from the landmark corresponding to the any one product to be picked to the first main lane, and a number of fourth landmarks from the landmark corresponding to the any one product to be picked to the second main lane;
calculating a sum of the number of first landmarks and the number of third landmarks, and a sum of the number of second landmarks and the number of fourth landmarks if the initial landmark of the unmanned device and the landmark corresponding to the any one product to be picked are located between the same two adjacent main lanes; and
adding a value corresponding to a smaller sum of the numbers of landmarks in the two sums of the numbers of landmarks in the two-dimensional matrix map to the coordinate distance to obtain the route distance from the initial landmark of the unmanned device to the landmark corresponding to the any one product to be picked.