[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

WO2020057278A1 - 无人设备路径规划方法和装置 - Google Patents

无人设备路径规划方法和装置 Download PDF

Info

Publication number
WO2020057278A1
WO2020057278A1 PCT/CN2019/099326 CN2019099326W WO2020057278A1 WO 2020057278 A1 WO2020057278 A1 WO 2020057278A1 CN 2019099326 W CN2019099326 W CN 2019099326W WO 2020057278 A1 WO2020057278 A1 WO 2020057278A1
Authority
WO
WIPO (PCT)
Prior art keywords
landmark
landmarks
picked
path
unmanned device
Prior art date
Application number
PCT/CN2019/099326
Other languages
English (en)
French (fr)
Inventor
韩松
Original Assignee
北京京东尚科信息技术有限公司
北京京东世纪贸易有限公司
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by 北京京东尚科信息技术有限公司, 北京京东世纪贸易有限公司 filed Critical 北京京东尚科信息技术有限公司
Priority to EP19863834.8A priority Critical patent/EP3828789A4/en
Priority to US17/271,426 priority patent/US12001212B2/en
Publication of WO2020057278A1 publication Critical patent/WO2020057278A1/zh

Links

Images

Classifications

    • G—PHYSICS
    • G05—CONTROLLING; REGULATING
    • G05D—SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
    • G05D1/00—Control of position, course, altitude or attitude of land, water, air or space vehicles, e.g. using automatic pilots
    • G05D1/02—Control of position or course in two dimensions
    • G05D1/021—Control of position or course in two dimensions specially adapted to land vehicles
    • G05D1/0212—Control of position or course in two dimensions specially adapted to land vehicles with means for defining a desired trajectory
    • G05D1/0214—Control of position or course in two dimensions specially adapted to land vehicles with means for defining a desired trajectory in accordance with safety or protection criteria, e.g. avoiding hazardous areas
    • G—PHYSICS
    • G05—CONTROLLING; REGULATING
    • G05D—SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
    • G05D1/00—Control of position, course, altitude or attitude of land, water, air or space vehicles, e.g. using automatic pilots
    • G05D1/02—Control of position or course in two dimensions
    • G05D1/021—Control of position or course in two dimensions specially adapted to land vehicles
    • G05D1/0231—Control of position or course in two dimensions specially adapted to land vehicles using optical position detecting means
    • G05D1/0234—Control of position or course in two dimensions specially adapted to land vehicles using optical position detecting means using optical markers or beacons
    • B—PERFORMING OPERATIONS; TRANSPORTING
    • B60—VEHICLES IN GENERAL
    • 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
    • B60W60/00—Drive control systems specially adapted for autonomous road vehicles
    • B60W60/001—Planning or execution of driving tasks
    • B60W60/0011—Planning or execution of driving tasks involving control alternatives for a single driving scenario, e.g. planning several paths to avoid obstacles
    • G—PHYSICS
    • G05—CONTROLLING; REGULATING
    • G05D—SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
    • G05D1/00—Control of position, course, altitude or attitude of land, water, air or space vehicles, e.g. using automatic pilots
    • G05D1/02—Control of position or course in two dimensions
    • G05D1/021—Control of position or course in two dimensions specially adapted to land vehicles
    • G05D1/0268—Control of position or course in two dimensions specially adapted to land vehicles using internal positioning means
    • G05D1/0272—Control of position or course in two dimensions specially adapted to land vehicles using internal positioning means comprising means for registering the travel distance, e.g. revolutions of wheels
    • G—PHYSICS
    • G05—CONTROLLING; REGULATING
    • G05D—SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
    • G05D1/00—Control of position, course, altitude or attitude of land, water, air or space vehicles, e.g. using automatic pilots
    • G05D1/02—Control of position or course in two dimensions
    • G05D1/021—Control of position or course in two dimensions specially adapted to land vehicles
    • G05D1/0268—Control of position or course in two dimensions specially adapted to land vehicles using internal positioning means
    • G05D1/0274—Control of position or course in two dimensions specially adapted to land vehicles using internal positioning means using mapping information stored in a memory device
    • G—PHYSICS
    • G05—CONTROLLING; REGULATING
    • G05D—SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
    • G05D1/00—Control of position, course, altitude or attitude of land, water, air or space vehicles, e.g. using automatic pilots
    • G05D1/20—Control system inputs
    • G05D1/24—Arrangements for determining position or orientation
    • G05D1/246—Arrangements for determining position or orientation using environment maps, e.g. simultaneous localisation and mapping [SLAM]
    • G—PHYSICS
    • G05—CONTROLLING; REGULATING
    • G05D—SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
    • G05D1/00—Control of position, course, altitude or attitude of land, water, air or space vehicles, e.g. using automatic pilots
    • G05D1/60—Intended control result
    • G05D1/617—Safety or protection, e.g. defining protection zones around obstacles or avoiding hazards
    • G—PHYSICS
    • G05—CONTROLLING; REGULATING
    • G05D—SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
    • G05D1/00—Control of position, course, altitude or attitude of land, water, air or space vehicles, e.g. using automatic pilots
    • G05D1/60—Intended control result
    • G05D1/644—Optimisation of travel parameters, e.g. of energy consumption, journey time or distance
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • 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
    • G06Q10/00—Administration; Management
    • G06Q10/04—Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem"
    • G06Q10/047—Optimisation of routes or paths, e.g. travelling salesman problem
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • 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
    • G06Q10/00—Administration; Management
    • G06Q10/06—Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
    • G06Q10/063—Operations research, analysis or management
    • G06Q10/0631—Resource planning, allocation, distributing or scheduling for enterprises or organisations
    • G06Q10/06315—Needs-based resource requirements planning or analysis
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • 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
    • G06Q10/00—Administration; Management
    • G06Q10/06—Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
    • G06Q10/063—Operations research, analysis or management
    • G06Q10/0631—Resource planning, allocation, distributing or scheduling for enterprises or organisations
    • G06Q10/06316—Sequencing of tasks or work
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • 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
    • G06Q10/00—Administration; Management
    • G06Q10/08—Logistics, e.g. warehousing, loading or distribution; Inventory or stock management
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • 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
    • G06Q10/00—Administration; Management
    • G06Q10/08—Logistics, e.g. warehousing, loading or distribution; Inventory or stock management
    • G06Q10/087—Inventory or stock management, e.g. order filling, procurement or balancing against orders

Definitions

  • the present disclosure relates to the field of unmanned equipment, and in particular, to a method and apparatus for planning an unmanned equipment path.
  • unmanned equipment such as drones and unmanned vehicles are used for picking operations in warehouses.
  • route planning of unmanned equipment in the warehouse is reasonable and whether the route can be planned efficiently has a great impact on the production efficiency in the warehouse.
  • a method for planning an unmanned device path includes: using a current landmark as a current node, acquiring a landmark corresponding to a product to be picked closest to the current node path, and deriving a landmark corresponding to the acquired product to be picked
  • the initial value of the current node is the initial landmark of the unmanned device
  • determine whether the current node is the landmark corresponding to the last product to be picked if so, stop performing the acquisition of the product to be picked closest to the current node path again Corresponding landmarks, and use the acquired landmarks corresponding to the to-be-selected products as the current node step; otherwise, repeat the acquisition of the landmarks corresponding to the to-be-selected products that are closest to the current node path, and use the acquired landmarks corresponding to the to-be-selected products as The steps of the current node; use the initial landmarks of the unmanned device and the lines formed by the landmarks corresponding to the products to be picked in turn as
  • the method further includes: determining the location of each landmark in the warehouse; mapping each landmark in the warehouse into a two-dimensional matrix map; determining coordinate values of the initial landmarks of the unmanned device in the two-dimensional matrix map, And the coordinate values of the landmarks corresponding to the products to be picked in the two-dimensional matrix map; according to the coordinate values, the path distance from the initial landmark of the unmanned device to the landmarks corresponding to the products to be picked and the landmarks corresponding to the products to be picked The distance between the paths.
  • calculating the path distance from the initial landmark of the unmanned device to the landmark corresponding to each product to be picked according to the coordinate value includes: calculating the initial landmark of the unmanned device and the landmark corresponding to any one of the products to be picked, in two dimensions The coordinate distance in the matrix map; if the initial landmark of the unmanned device and the landmark corresponding to any one of the products to be picked are located in different racks and lanes, determine whether the initial landmark of the unmanned device and the corresponding landmark of any one to be picked product are located in the same Between two adjacent main lanes; if the initial landmark of the unmanned device and the landmark corresponding to any one of the items to be picked are located between the same two adjacent main lanes, determine the initial landmark of the unmanned device to two adjacent The number of first landmarks of the first main lane in the main lane, and the number of second landmarks from the initial landmark of the unmanned device to the second main lane of two adjacent main lanes, and determining the corresponding one of the products to be picked The number of landmarks is the
  • the coordinate distance is used as the initial landmark of the unmanned device to each The path distance of the landmark corresponding to the item to be picked.
  • calculating the path distance between the landmarks corresponding to the products to be picked according to the coordinate values includes: calculating the coordinate distance of the landmarks corresponding to any two products to be picked in a two-dimensional matrix map; The landmarks corresponding to the selected goods are located in different shelves and lanes, then it is determined whether the landmarks corresponding to any two goods to be picked are located between the same two adjacent main lanes; if the landmarks corresponding to any two goods to be picked are located in the same two Between adjacent main lanes, determine the number of first landmarks corresponding to the first to-be-picked product in any two to-be-picked products to the first landmark number of the first main-lane in two adjacent main-lanes, and the correspondence of the first to-picked product From the number of landmarks to the number of second landmarks in the second main lane of two adjacent main lanes, and the number of landmarks corresponding to the second to be picked commodity in the two to-be-picked items to the number of third landmarks in the first main lane, and the second
  • the coordinate distance is used as the path distance between the landmarks corresponding to any two items to be picked .
  • the method further includes: if the selected unmanned device has multiple driving paths, selecting an optimal path among the multiple driving paths according to an initial starting point planned in the next step.
  • selecting the optimal route among the multiple driving routes according to the initial starting point planned in the next step includes: selecting among the multiple driving routes, the landmark corresponding to the last commodity to be picked is closest to the initial starting point planned in the next step. Path as the optimal path.
  • next step is to return the unmanned device to the original landmark, a plurality of driving paths is selected, and the driving path closest to the initial landmark corresponding to the last product to be picked is used as the optimal path.
  • an unmanned device path planning device including: a landmark acquisition unit configured to use a current landmark as a current node to acquire a landmark corresponding to a product to be picked closest to the current node path, The landmark corresponding to the acquired to-be-selected product is taken as the current node, where the initial value of the current node is the initial landmark of the unmanned device; it is determined whether the current node is the landmark corresponding to the last to-be-selected product; if so, the acquisition is stopped and executed again.
  • a landmark acquisition unit configured to use a current landmark as a current node to acquire a landmark corresponding to a product to be picked closest to the current node path, The landmark corresponding to the acquired to-be-selected product is taken as the current node, where the initial value of the current node is the initial landmark of the unmanned device; it is determined whether the current node is the landmark corresponding to the last to-be-selected product; if so, the acquisition is stopped and executed again.
  • the landmark corresponding to the product to be picked closest to the current node path, and the acquired landmark corresponding to the product to be picked is the step of the current node; otherwise, repeat the acquisition of the landmark corresponding to the product to be picked closest to the current node path, and The obtained landmark corresponding to the to-be-selected product is taken as a step of the current node; the driving path determination unit is configured to use the initial landmark of the unmanned device and the route corresponding to the landmarks corresponding to the selected to-be-selected product as the unmanned device. path.
  • the device further includes: a landmark position determining unit configured to determine the position of each landmark in the warehouse; a path distance determining unit configured to map each landmark in the warehouse to a two-dimensional matrix map; determining The coordinate values of the initial landmarks of the unmanned device in the two-dimensional matrix map, and the coordinates of the landmarks corresponding to each product to be picked in the two-dimensional matrix map; according to the coordinate values, the initial landmarks of the unmanned device are calculated to each of the products to be picked The path distance of the corresponding landmarks, and the path distance between the landmarks corresponding to the commodities to be picked.
  • the path distance determination unit is configured to calculate a coordinate distance between the initial landmark of the unmanned device and any landmark to be picked in a two-dimensional matrix map; if the initial landmark of the unmanned device and the arbitrary The landmarks corresponding to one to-be-picked product are located in different shelf lanes, then it is determined whether the initial landmarks of the unmanned equipment and the landmarks corresponding to any one of the to-be-picked commodities are located between the same two adjacent main lanes; The landmarks correspond to the landmarks corresponding to any one of the goods to be picked. The landmarks are located between the same two adjacent main lanes. Then, the number of the first landmarks of the unmanned device to the first main lane of the two adjacent main lanes is determined.
  • the number of second landmarks from the initial landmark of the unmanned device to the second main lane of two adjacent main lanes, and determining the number of third landmarks from the first main lane to the landmark corresponding to any one of the items to be picked, and the The number of landmarks corresponding to any one of the products to be picked is the fourth landmark number from the second main lane, and the sum of the first landmark number and the third landmark number is calculated.
  • the sum of the number of the second landmark and the number of the fourth landmark; the value corresponding to the smaller number of the sum of the two landmarks in the two-dimensional matrix map is added to the coordinate distance to obtain no one The path distance from the initial landmark of the device to the landmark corresponding to any one of the commodities to be picked.
  • the path distance determination unit is further configured to use the coordinate distance as the distance of the unmanned device if the initial landmark of the unmanned device and the landmark corresponding to the product to be picked are not located between the same two adjacent main lanes. The path distance from the initial landmark to the landmark corresponding to any one of the commodities to be picked.
  • the path distance determining unit is configured to calculate a coordinate distance in a two-dimensional matrix map of the landmarks corresponding to any two items to be picked; if the landmarks corresponding to any two items to be picked are located in different shelf lanes, Then determine whether the landmarks corresponding to any two items to be picked are located between the same two adjacent main lanes; if the landmarks corresponding to any two items to be picked are located between the same two adjacent main lanes, determine The number of first landmarks corresponding to the first to-be-chosen goods in any two items to be picked to the first main lane of two adjacent main lanes, and the number of landmarks corresponding to the first to-be-chosen goods to two adjacent main goods The number of second landmarks of the second main lane in the lane, the number of landmarks corresponding to the second to-be-picked commodity among the two to-be-picked items to the number of third landmarks of the first main lane, and the landmarks of the second-picked product The number of fourth landmarks to
  • the path distance determining unit is further configured to use the coordinate distance as the any two items to be picked if the landmarks corresponding to the any two items to be picked are not located between the same two adjacent main lanes. Path distance between corresponding landmarks.
  • the apparatus further includes: an optimal path determining unit configured to select a driving path of the plurality of driving paths according to an initial starting point planned for the next step if there are multiple driving paths of the selected unmanned device. Excellent path.
  • the optimal path determining unit is configured to select a plurality of driving paths, and the landmark corresponding to the last commodity to be picked is closest to the initial starting point planned in the next step as the optimal path.
  • the optimal path determining unit is configured to select a plurality of driving paths, and the landmark corresponding to the last product to be picked is the closest driving path to the initial landmark if the unplanned device returns to the original landmark in the next step. As the optimal path.
  • an unmanned device path planning device including: a memory; and a processor coupled to the memory, the processor being configured to execute the unmanned device as described above based on instructions stored in the memory. Path planning method.
  • a computer-readable storage medium is further provided with computer program instructions stored thereon, which are executed by a processor to implement the above-mentioned unmanned device path planning method.
  • FIG. 1 is a schematic flowchart of some embodiments of an unmanned device path planning method according to the present disclosure.
  • FIG. 2 is a schematic diagram of a traveling landmark of an unmanned device of the present disclosure.
  • FIG. 3 is a schematic diagram of a two-dimensional matrix map of an unmanned device of the present disclosure.
  • FIG. 4 is a schematic diagram of a logistics map in some embodiments of the present disclosure.
  • FIG. 5 is a schematic structural diagram of some embodiments of an unmanned device path planning apparatus according to the present disclosure.
  • FIG. 6 is a schematic structural diagram of another embodiment of an unmanned device path planning apparatus according to the present disclosure.
  • FIG. 7 is a schematic structural diagram of still another embodiment of an unmanned device path planning apparatus according to the present disclosure.
  • FIG. 8 is a schematic structural diagram of still another embodiment of an unmanned device path planning apparatus according to the present disclosure.
  • any specific value should be construed as exemplary only and not as a limitation. Therefore, other examples of the exemplary embodiments may have different values.
  • FIG. 1 is a schematic flowchart of some embodiments of an unmanned device path planning method according to the present disclosure.
  • 210 is a shelf and 220 is a landmark.
  • the landmark may include a shelf landmark and a main lane landmark.
  • the unmanned equipment travels along the landmark in the warehouse.
  • the landmark can determine the current position of the unmanned equipment. And from this determine the next direction of travel.
  • the current landmark is used as the current node, a landmark corresponding to the product to be picked closest to the current node path is obtained, and the obtained landmark corresponding to the selected product is used as the current node, where the initial value of the current node is no one.
  • the initial landmark of the device You can map each landmark in the warehouse to a two-dimensional matrix map, as shown in Figure 3.
  • the lines filled with textures are landmarks, and the white boxes are concrete objects or open spaces.
  • the initial landmarks of the unmanned device are determined in the two-dimensional matrix map.
  • the coordinate values of the landmarks corresponding to the products to be picked in the two-dimensional matrix map Based on the coordinate values, the path distance from the initial landmark of the unmanned device to the landmarks corresponding to the products to be picked is calculated, and the products to be picked are Path distance between corresponding landmarks.
  • step 130 it is determined whether the current node is a landmark corresponding to the last product to be picked, and if so, step 140 is performed; otherwise, step 120 is performed. That is, it is determined whether the landmarks corresponding to all the products to be picked have been acquired. If the landmarks corresponding to all the products to be picked have not been acquired, step 120 is continued until the landmarks corresponding to the last product to be selected are acquired.
  • step 140 the initial landmarks of the unmanned equipment and the route formed by the landmarks corresponding to the products to be picked in turn are used as the driving path of the unmanned equipment. Among them, multiple driving paths may be formed.
  • the initial landmarks of the unmanned device are used as the starting point, the landmarks corresponding to the products to be picked are sequentially obtained, and the route formed by the acquired landmarks is used as the driving path of the unmanned device, so that the unmanned device can be quickly planned.
  • the route of travel in the warehouse is used as the starting point, the landmarks corresponding to the products to be picked are sequentially obtained, and the route formed by the acquired landmarks is used as the driving path of the unmanned device, so that the unmanned device can be quickly planned.
  • calculating the path distance from the initial landmark of the unmanned device to the landmark corresponding to each product to be picked may be: calculating the initial landmark of the unmanned device and the landmark corresponding to any one of the products to be picked. The coordinate distance in the dimensional matrix map. If the initial landmark of the unmanned device and the landmark corresponding to any one of the products to be picked are not located between the same two adjacent main lanes, then use this coordinate distance as the initial landmark of the unmanned device.
  • the corresponding number of landmarks is the fourth number of landmarks from the second main lane.
  • the path distance between the landmarks corresponding to the products to be picked is calculated according to the coordinate values, for example, the coordinate distance of the landmarks corresponding to any two products to be picked in the two-dimensional matrix map is calculated; if the two The landmarks corresponding to the two to-be-picked products are not located between the same two adjacent main lanes or the same shelf laneway, then the coordinate distance is used as the path distance between the landmarks corresponding to any two to-be-picked commodities; if The landmarks corresponding to any two to-be-picked products are located between the same two adjacent main lanes, and are located in different shelf lanes.
  • the coordinates of the initial landmarks of the unmanned device and the landmarks corresponding to the products to be picked can be expressed as [X, Y, whether it is a cross lane, landmark KEY, north_landmark KEY, south_ Landmark KEY, west_landmark KEY, east_landmark KEY, upper_landmark number, lower_landmark number].
  • landmark KEY is the identifier of the landmark.
  • the coordinates [X, Y] of the landmark in the two-dimensional matrix map can be queried.
  • the coordinates [X, Y] of the landmarks in the two-dimensional matrix map can also be determined.
  • the number after KEY_ is a unique code, which can be ordered or unordered. Among them, KEY is Null, which means that the corresponding landmark is empty, that is, the physical object or the empty space.
  • the number of landmarks indicates the number of landmarks with coordinates [X, Y] in the positive direction of the Y axis to the nearest main lane, and the number of landmarks indicates the number of landmarks with coordinates [X, Y] in the negative direction of Y to the nearest main lane.
  • This parameter It is used to decide in which direction the unmanned equipment can move to reach the main lane fastest.
  • the formula for calculating the path distance from the initial landmark of the unmanned device to the landmark corresponding to each product to be picked, or the path distance between the landmarks corresponding to each product to be picked can be expressed as
  • the number of landmarks that can be moved up to the main laneway or the number of landmarks that can be moved down to the main laneway must be M. If two points are in two different lanes of the shelf and they are not between the same two adjacent main lanes, M is 0.
  • the coordinates of the initial landmark A of the unmanned device in the two-dimensional matrix map are [13, 2, no, KEY_000012, north_KEY_000032, south_KEY_000075, west_KEY_000045, east_KEY_000047, 0 , 0];
  • the coordinates of the landmark corresponding to product B in the two-dimensional matrix map are [7, 4, No, KEY_000112, North_KEY_000099, South_KEY_000138, West_KEY_000111, East_KEY_000113, 2, 1];
  • Product C The coordinates of the corresponding landmark in the two-dimensional matrix map are [3, 6, No, KEY_000164, North_KEY_000145, South_KEY_000178, West_KEY_000161, East_KEY_000165, 1, 2];
  • the landmark corresponding to product D is in two dimensions
  • the coordinates in the matrix map are [7, 10, No, KEY_000164, North_KEY_000
  • the landmarks corresponding to the products can be selected in turn.
  • the second step is to start from point A and obtain the landmark closest to the path of point A, that is, point B, to form a landmark list [A (0), B (8), ALL (8)], where B (8) represents The path distance between point B and point A is 8.
  • the third step is to obtain the landmarks closest to the path of point B starting from point B. Since the path distance of point C or D from point B is 6, two routes are formed, [A (0), B (8) , C (6), ALL (14)] and [A (0), B (8), D (6), ALL (14)].
  • the two lines select the next closest distance points, namely [A (0), B (8), C (6), E (6), ALL (20)], and [A (0) , B (8), D (6), F (2), ALL (16)].
  • the two lines respectively select the next nearest distance points, and the distances from E to D and F are the same. Therefore, three routes [A (0), B (8), C (6), and E (6) are formed. , D (6), ALL (26)], [A (0), B (8), C (6), E (6), F (6), ALL (26)], and [A (0), B (8), D (6), F (2), E (6), ALL (22)].
  • the sixth step is to obtain the last landmark, [A (0), B (8), C (6), E (6), D (6), F (2), ALL (28)], [A ( 0), B (8), C (6), E (6), F (6), D (2), ALL (28)] and [A (0), B (8), D (6), F (2), E (6), C (6), ALL (28)].
  • the driving path of the unmanned device can be determined. From the sixth step, it can be seen that the length of the three paths formed is the same. Therefore, the optimal one of the multiple driving paths can be selected according to the initial starting point planned in the next step. path. You can select the driving path that is closest to the landmark corresponding to the last product to be picked from the initial starting point of the next planning step, as the optimal path. For example, if the next step is to plan an unmanned device to return to the original landmark, then select the driving path that is closest to the original landmark from the last landmark among the multiple travel paths as the optimal path. If the next task needs to be executed after the picking task is completed, the last point can be used as the starting point of the next task according to the overall layout of the next task.
  • the calculation is directly based on the coordinate values of the two-dimensional matrix map, the calculation logic is simpler, the complexity is lower, and the requirement for hardware computing capabilities is smaller.
  • the entire map can be modified by traversing the modified coordinates.
  • FIG. 5 is a schematic structural diagram of some embodiments of an unmanned device path planning apparatus according to the present disclosure.
  • the device includes a landmark position determination unit 510, a landmark acquisition unit 520, and a travel path determination unit 530.
  • the landmark position determination unit 510 is configured to determine each landmark position in the warehouse.
  • the landmark can include a shelf landmark and a main lane landmark.
  • the unmanned equipment travels along the landmark in the warehouse.
  • the landmark can determine the current position of the unmanned equipment and determine the next direction of travel.
  • the landmark acquiring unit 520 is configured to use the current landmark as the current node, acquire a landmark corresponding to the product to be picked closest to the current node path, and use the acquired landmark corresponding to the product to be picked as the current node, where the initial value of the current node is Is the initial landmark of the unmanned device; determine whether the current node is the landmark corresponding to the last product to be picked; if so, stop re-obtaining the landmark corresponding to the product to be picked closest to the current node's path, and the acquired product to be picked
  • the corresponding landmark is taken as the step of the current node, otherwise, the step of obtaining the landmark corresponding to the product to be picked closest to the current node path is repeatedly performed, and the obtained landmark corresponding to the selected product is used as the current node.
  • the driving path determining unit 530 is configured to use a line composed of an initial landmark of the unmanned device and landmarks corresponding to the products to be picked in order as the driving path of the unmanned device.
  • the initial landmark of the unmanned device is used as the starting point, the landmarks corresponding to the products to be picked are sequentially obtained, and the route formed by the landmarks is used as the driving path of the unmanned device, so that the unmanned device can be quickly planned in the warehouse. Route of travel.
  • FIG. 6 is a schematic structural diagram of another embodiment of an unmanned device path planning apparatus according to the present disclosure.
  • the device includes a path distance determination unit 610, which is configured to map each landmark position in the warehouse to a two-dimensional matrix map; determine the coordinate values of the initial landmarks of the unmanned device in the two-dimensional matrix map, and correspond to each of the products to be picked The coordinate values of the landmarks in the two-dimensional matrix map; according to the coordinate values, calculate the path distance from the initial landmark of the unmanned device to the landmark corresponding to each product to be picked, and the path distance between the landmarks corresponding to each product to be picked.
  • the path distance determining unit 610 is configured to calculate the coordinate distance between the initial landmark of the unmanned device and any landmark to be picked in a two-dimensional matrix map; determine the initial landmark of the unmanned device and the Whether the landmark corresponding to any one of the commodities to be picked is located between the same two adjacent main lanes; if the initial landmark of the unmanned equipment and the landmark corresponding to the one to be picked product are between the same two adjacent main lanes, Then determine the first landmark number of the unmanned device to the first main lane in the same two adjacent main lanes, and the initial landmark of the unmanned device to the second in the same two adjacent main lanes The number of second landmarks of the main lane, and the number of third landmarks that determine the distance from the corresponding landmark of the one to-be-selected commodity to the first main lane, and the number of fourth landmarks of the second main lane from the landmark that corresponds to any of the to-be-selected commodities.
  • the path distance determination unit 610 is configured to calculate a coordinate distance of a landmark corresponding to any two items to be picked in a two-dimensional matrix map; and to determine whether the landmarks corresponding to any two items to be picked are located in the same two Between two adjacent main lanes; if the landmarks corresponding to any two to-be-chosen commodities are located between the same two adjacent main lanes, then it is determined that The number of first landmarks of the first main lane in the same two adjacent main lanes, and the number of landmarks corresponding to the first commodity to be picked to the second landmark of the second main lane in the same two adjacent main lanes, And the number of third landmarks corresponding to the first main aisle from the landmarks corresponding to the second to-be-picked goods among any two items to be picked; and the fourth number of landmarks corresponding to the second main-lane to the second main goods; The sum of the number of landmarks and the number of landmarks of the third and the number of landmarks of the second and fourth landmarks; the sum of the smaller
  • the device further includes an optimal path determining unit 620 configured to select a plurality of driving paths according to an initial starting point planned for the next step if there are multiple driving paths of the selected unmanned device.
  • the best path among the paths For example, among multiple driving routes, the driving route closest to the landmark corresponding to the last commodity to be picked may be selected as the optimal route.
  • the next step is to plan an unmanned device to return to the original landmark, then select a plurality of driving paths.
  • the driving path closest to the initial landmark corresponding to the last landmark to be picked is the optimal path. If the next task needs to be executed after the picking task is completed, the last point can be used as the starting point of the next task according to the overall layout of the next task.
  • the calculation is directly based on the coordinate values of the two-dimensional matrix map, the calculation logic is simpler, the complexity is lower, and the requirement for hardware computing capabilities is smaller.
  • the entire map can be modified by traversing the modified coordinates.
  • FIG. 7 is a schematic structural diagram of still another embodiment of an unmanned device path planning apparatus according to the present disclosure.
  • the device includes a memory 710 and a processor 720, where the memory 710 may be a magnetic disk, a flash memory, or any other non-volatile storage medium.
  • the memory is configured to store instructions in the embodiment corresponding to FIG. 1.
  • the processor 720 is coupled to the memory 710 and may be implemented as one or more integrated circuits, such as a microprocessor or a microcontroller.
  • the processor 720 is configured to execute instructions stored in a memory.
  • the device 800 includes a memory 810 and a processor 820.
  • the processor 820 is coupled to the memory 810 through a BUS bus 830.
  • the device 800 may also be connected to the external storage device 850 through the storage interface 840 to call external data, and may also be connected to the network or another computer system (not shown) through the network interface 860, which will not be described in detail here.
  • data instructions are stored in the memory, and the instructions are processed by the processor.
  • the initial landmarks of the unmanned device are used as the starting point, and the landmarks corresponding to the products to be picked are sequentially obtained, and the route formed by the landmarks is used as the unmanned device. Driving route, so you can quickly plan the route of the drone in the warehouse.
  • a computer-readable storage medium stores computer program instructions, which when executed by a processor, implement the steps of the method in the embodiment corresponding to FIG. 1.
  • the embodiments of the present disclosure may be provided as a method, an apparatus, or a computer program product. Therefore, the present disclosure may take the form of an entirely hardware embodiment, an entirely software embodiment, or an embodiment combining software and hardware aspects.
  • the present disclosure may take the form of a computer program product implemented on one or more computer-usable non-transitory storage media (including but not limited to disk storage, CD-ROM, optical storage, etc.) containing computer-usable program code therein. .
  • These computer program instructions may also be stored in a computer-readable memory capable of directing a computer or other programmable data processing device to work in a particular manner such that the instructions stored in the computer-readable memory produce a manufactured article including an instruction device, the instructions
  • the device implements the functions specified in one or more flowcharts and / or one or more blocks of the block diagram.
  • These computer program instructions can also be loaded on a computer or other programmable data processing device, so that a series of steps can be performed on the computer or other programmable device to produce a computer-implemented process, which can be executed on the computer or other programmable device.
  • the instructions provide steps for implementing the functions specified in one or more flowcharts and / or one or more blocks of the block diagrams.

Landscapes

  • Engineering & Computer Science (AREA)
  • Business, Economics & Management (AREA)
  • Human Resources & Organizations (AREA)
  • Physics & Mathematics (AREA)
  • Economics (AREA)
  • General Physics & Mathematics (AREA)
  • Strategic Management (AREA)
  • Entrepreneurship & Innovation (AREA)
  • Radar, Positioning & Navigation (AREA)
  • Automation & Control Theory (AREA)
  • Operations Research (AREA)
  • Marketing (AREA)
  • Quality & Reliability (AREA)
  • Tourism & Hospitality (AREA)
  • General Business, Economics & Management (AREA)
  • Development Economics (AREA)
  • Theoretical Computer Science (AREA)
  • Aviation & Aerospace Engineering (AREA)
  • Remote Sensing (AREA)
  • Game Theory and Decision Science (AREA)
  • Educational Administration (AREA)
  • Accounting & Taxation (AREA)
  • Finance (AREA)
  • Mechanical Engineering (AREA)
  • Transportation (AREA)
  • Human Computer Interaction (AREA)
  • Electromagnetism (AREA)
  • Warehouses Or Storage Devices (AREA)

Abstract

本公开提供了一种无人设备路径规划方法和装置，涉及无人设备领域。该方法包括：以当前地标作为当前节点，获取与当前节点路径距离最近的待拣选商品对应的地标；判断与当前节点路径距离最近的待拣选商品对应的地标，是否为最后一个待拣选商品对应的地标；若是，则停止执行再次获取与当前节点路径距离最近的待拣选商品对应的地标的步骤，否则，将获取的待拣选商品对应的地标作为当前节点，并重复执行获取与当前节点路径距离最近的待拣选商品对应的地标的步骤；将无人设备的初始地标以及依次选取的待拣选商品对应的地标构成的线路作为无人设备的行驶路径。本发明能够快速规划无人设备在仓内的行进路线。

Description

无人设备路径规划方法和装置
相关申请的交叉引用
本申请是以CN申请号为201811096783.2，申请日为2018年9月20日的申请为基础，并主张其优先权，该CN申请的公开内容在此作为整体引入本申请中。
技术领域
本公开涉及无人设备领域，尤其涉及一种无人设备路径规划方法和装置。
背景技术
现今仓库的生产活动中，已经大规模使用自动化设备，例如利用无人机、无人车等无人设备在仓库进行拣选作业。而无人设备在仓库内的路线规划是否合理以及是否能够高效规划路径，对仓内生产效率有较大影响。
发明内容
根据本公开一方面，提出一种无人设备路径规划方法，包括：以当前地标作为当前节点，获取与当前节点路径距离最近的待拣选商品对应的地标，并将获取的待拣选商品对应的地标作为当前节点，其中，当前节点的初始值为无人设备的初始地标；判断当前节点是否为最后一个待拣选商品对应的地标；若是，则停止再次执行获取与当前节点路径距离最近的待拣选商品对应的地标，并将获取的待拣选商品对应的地标作为当前节点的步骤，否则，重复执行获取与当前节点路径距离最近的待拣选商品对应的地标，并将获取的待拣选商品对应的地标作为当前节点的步骤；将无人设备的初始地标以及依次选取的待拣选商品对应的地标构成的线路，作为无人设备的行驶路径。
在一些实施例中，该方法还包括：确定仓库内的各个地标位置；将仓库内的各个地标映射到二维矩阵地图中；确定无人设备的初始地标在二维矩阵地图中的坐标值，以及各待拣选商品对应的地标在二维矩阵地图中的坐标值；根据坐标值，计算无人设备的初始地标到各待拣选商品对应的地标的路径距离，以及各待拣选商品对应的地标间的路径距离。
在一些实施例中，根据坐标值，计算无人设备的初始地标到各待拣选商品对应的地标的路径距离包括：计算无人设备的初始地标与任意一个待拣选商品对应的地标， 在二维矩阵地图中的坐标距离；若无人设备的初始地标与任意一个待拣选商品对应的地标位于不同的货架巷道，则判断无人设备的初始地标与任意一个待拣选商品对应的地标是否位于相同的两个相邻主巷道之间；若无人设备的初始地标与任意一个待拣选商品对应的地标位于相同的两个相邻主巷道之间，则确定无人设备的初始地标到两个相邻主巷道中的第一主巷道的第一地标数，以及无人设备的初始地标到两个相邻主巷道中的第二主巷道的第二地标数，以及确定该任意一个待拣选商品对应的地标距离第一主巷道的第三地标数，和该任意一个待拣选商品对应的地标距离第二主巷道的第四地标数，计算第一地标数与第三地标数的地标数之和，以及第二地标数与第四地标数的地标数之和；将两个地标数之和中较小的地标数之和在二维矩阵地图中对应的值，与坐标距离相加，得到无人设备的初始地标到该任意一个待拣选商品对应的地标的路径距离。
在一些实施例中，若无人设备的初始地标与该任意一个待拣选商品对应的地标不是位于相同的两个相邻主巷道之间，则将该坐标距离作为无人设备的初始地标到各待拣选商品对应的地标的路径距离。
在一些实施例中，根据坐标值，计算各待拣选商品对应的地标间的路径距离包括：计算任意两个待拣选商品对应的地标在二维矩阵地图中的坐标距离；若任意两个待拣选商品对应的地标位于不同的货架巷道，则判断任意两个待拣选商品对应的地标是否位于相同的两个相邻主巷道之间；若任意两个待拣选商品对应的地标位于相同的两个相邻主巷道之间，则确定任意两个待拣选商品中第一待拣选商品对应的地标到两个相邻主巷道中的第一主巷道的第一地标数，以及第一待拣选商品对应的地标到两个相邻主巷道中的第二主巷道的第二地标数，以及两个待拣选商品中第二待拣选商品对应的地标到第一主巷道的第三地标数，以及第二待拣选商品对应的地标到第二主巷道的第四地标数，计算第一地标数与第三地标数的地标数之和，以及第二地标数与第四地标数的地标数之和；将两个地标数之和中较小的地标数之和在二维矩阵地图中对应的值，与坐标距离相加，得到任意两个待拣选商品对应的地标间的路径距离。
在一些实施例中，若该任意两个待拣选商品对应的地标不是位于相同两个相邻主巷道之间，则将该坐标距离作为该任意两个待拣选商品对应的地标间的路径距离。
在一些实施例中，该方法还包括：若选择出的无人设备的行驶路径有多条，则根据下一步规划的初始起点选择多条行驶路径中的最优路径。
在一些实施例中，根据下一步规划的初始起点选择多条行驶路径中的最优路径包 括：选择多条行驶路径中，最后一个待拣选商品对应的地标距离下一步规划的初始起点最近的行驶路径，作为最优路径。
在一些实施例中，若下一步规划为无人设备回到初始地标，则选择多条行驶路径中，最后一个待拣选商品对应的地标距离初始地标最近的行驶路径，作为最优路径。
根据本公开的另一方面，还提出一种无人设备路径规划装置，包括：地标获取单元，被配置为以当前地标作为当前节点，获取与当前节点路径距离最近的待拣选商品对应的地标，并将获取的待拣选商品对应的地标作为当前节点，其中，当前节点的初始值为无人设备的初始地标；判断当前节点是否为最后一个待拣选商品对应的地标；若是，则停止再次执行获取与当前节点路径距离最近的待拣选商品对应的地标，并将获取的待拣选商品对应的地标作为当前节点的步骤，否则，重复执行获取与当前节点路径距离最近的待拣选商品对应的地标，并将获取的待拣选商品对应的地标作为当前节点的步骤；行驶路径确定单元，被配置为将无人设备的初始地标以及依次选取的待拣选商品对应的地标构成的线路，作为无人设备的行驶路径。
在一些实施例中，该装置还包括：地标位置确定单元，被配置为确定仓库内的各个地标位置；路径距离确定单元，被配置为将仓库内的各个地标映射到二维矩阵地图中；确定无人设备的初始地标在二维矩阵地图中的坐标值，以及各待拣选商品对应的地标在二维矩阵地图中的坐标值；根据坐标值，计算无人设备的初始地标到各待拣选商品对应的地标的路径距离，以及各待拣选商品对应的地标间的路径距离。
在一些实施例中，路径距离确定单元被配置为计算无人设备的初始地标与任意一个待拣选商品对应的地标，在二维矩阵地图中的坐标距离；若无人设备的初始地标与该任意一个待拣选商品对应的地标位于不同的货架巷道，则判断无人设备的初始地标与该任意一个待拣选商品对应的地标是否位于相同的两个相邻主巷道之间；若无人设备的初始地标与该任意一个待拣选商品对应的地标位于相同的两个相邻主巷道之间，则确定无人设备的初始地标到两个相邻主巷道中的第一主巷道的第一地标数，以及无人设备的初始地标到两个相邻主巷道中的第二主巷道的第二地标数，以及确定该任意一个待拣选商品对应的地标距离第一主巷道的第三地标数，和该任意一个待拣选商品对应的地标距离第二主巷道的第四地标数，计算第一地标数与第三地标数的地标数之和，以及第二地标数与第四地标数的地标数之和；将两个地标数之和中较小的地标数之和在二维矩阵地图中对应的值，与坐标距离相加，得到无人设备的初始地标到该任意一个待拣选商品对应的地标的路径距离。
在一些实施例中，路径距离确定单元还被配置为若无人设备的初始地标与待拣选商品对应的地标不是位于相同的两个相邻主巷道之间，则将坐标距离作为无人设备的初始地标到该任意一个待拣选商品对应的地标的路径距离。
在一些实施例中，路径距离确定单元被配置为计算任意两个待拣选商品对应的地标，在二维矩阵地图中的坐标距离；若任意两个待拣选商品对应的地标位于不同的货架巷道，则判断该任意两个待拣选商品对应的地标是否位于相同的两个相邻主巷道之间；若该任意两个待拣选商品对应的地标位于相同的两个相邻主巷道之间，则确定该任意两个待拣选商品中第一待拣选商品对应的地标到两个相邻主巷道中的第一主巷道的第一地标数，以及第一待拣选商品对应的地标到两个相邻主巷道中的第二主巷道的第二地标数，以及该任意两个待拣选商品中第二待拣选商品对应的地标到第一主巷道的第三地标数，以及第二待拣选商品对应的地标到第二主巷道的第四地标数；计算第一地标数与第三地标数的地标数之和，以及第二地标数与第四地标数的地标数之和；将两个地标数之和中较小的地标数之和在二维矩阵地图中对应的值，与坐标距离相加，得到该任意两个待拣选商品对应的地标间的路径距离。
在一些实施例中，路径距离确定单元还被配置为若该任意两个待拣选商品对应的地标不是位于相同的两个相邻主巷道之间，则将坐标距离作为该任意两个待拣选商品对应的地标间的路径距离。
在一些实施例中，该装置还包括：最优路径确定单元，被配置为若选择出的无人设备的行驶路径有多条，则根据下一步规划的初始起点选择多条行驶路径中的最优路径。
在一些实施例中，最优路径确定单元被配置为选择多条行驶路径中，最后一个待拣选商品对应的地标距离下一步规划的初始起点最近的行驶路径，作为最优路径。
在一些实施例中，最优路径确定单元被配置为若下一步规划为无人设备回到初始地标，则选择多条行驶路径中，最后一个待拣选商品对应的地标距离初始地标最近的行驶路径，作为最优路径。
根据本公开的另一方面，还提出一种无人设备路径规划装置，包括：存储器；以及耦接至存储器的处理器，处理器被配置为基于存储在存储器的指令执行如上述的无人设备路径规划方法。
根据本公开的另一方面，还提出一种计算机可读存储介质，其上存储有计算机程序指令，该指令被处理器执行时实现上述的无人设备路径规划方法。
通过以下参照附图对本公开的示例性实施例的详细描述，本公开的其它特征及其优点将会变得清楚。
附图说明
构成说明书的一部分的附图描述了本公开的实施例，并且连同说明书一起用于解释本公开的原理。
参照附图，根据下面的详细描述，可以更加清楚地理解本公开，其中：
图1为本公开无人设备路径规划方法的一些实施例的流程示意图。
图2为本公开无人设备行进地标示意图。
图3为本公开无人设备二维矩阵地图示意图。
图4为本公开一些实施例中物流地图示意图。
图5为本公开无人设备路径规划装置的一些实施例的结构示意图。
图6为本公开无人设备路径规划装置的另一些实施例的结构示意图。
图7为本公开无人设备路径规划装置的再一些实施例的结构示意图。
图8为本公开无人设备路径规划装置的又一些实施例的结构示意图。
具体实施方式
现在将参照附图来详细描述本公开的各种示例性实施例。应注意到：除非另外具体说明，否则在这些实施例中阐述的部件和步骤的相对布置、数字表达式和数值不限制本公开的范围。
同时，应当明白，为了便于描述，附图中所示出的各个部分的尺寸并不是按照实际的比例关系绘制的。
以下对至少一个示例性实施例的描述实际上仅仅是说明性的，决不作为对本公开及其应用或使用的任何限制。
对于相关领域普通技术人员已知的技术、方法和设备可能不作详细讨论，但在适当情况下，所述技术、方法和设备应当被视为授权说明书的一部分。
在这里示出和讨论的所有示例中，任何具体值应被解释为仅仅是示例性的，而不是作为限制。因此，示例性实施例的其它示例可以具有不同的值。
应注意到：相似的标号和字母在下面的附图中表示类似项，因此，一旦某一项在一个附图中被定义，则在随后的附图中不需要对其进行进一步讨论。
为使本公开的目的、技术方案和优点更加清楚明白，以下结合具体实施例，并参照附图，对本公开进一步详细说明。
图1为本公开无人设备路径规划方法的一些实施例的流程示意图。
在步骤110，确定仓库内的各个地标位置。如图2所示，210为货架，220为地标，其中，地标可以包括货架地标和主巷道地标，无人设备在仓库内沿地标行进，通过地标可以判断出无人设备当前所处的位置，并由此决定下一个行进方向。
在步骤120，以当前地标作为当前节点，获取与当前节点路径距离最近的待拣选商品对应的地标，并将获取的待拣选商品对应的地标作为当前节点，其中，当前节点的初始值为无人设备的初始地标。可以如图3所示，将仓库内的各个地标映射到二维矩阵地图中，具有纹路填充的框为地标，白色框为具体实物或空地，确定无人设备的初始地标在二维矩阵地图中的坐标值，以及各待拣选商品对应的地标在二维矩阵地图中的坐标值，根据坐标值，计算无人设备的初始地标到各待拣选商品对应的地标的路径距离，以及各待拣选商品对应的地标间的路径距离。
在步骤130，判断当前节点是否为最后一个待拣选商品对应的地标，若是，则执行步骤140，否则，执行步骤120。即判断是否已获取所有待拣选商品对应的地标，若还没有获取所有待拣选商品对应的地标，则继续执行步骤120，直到获取最后一个待拣选商品对应的地标。
在步骤140，将无人设备的初始地标以及依次选取的待拣选商品对应的地标构成的线路，作为无人设备的行驶路径。其中，可能形成多条行驶路径。
在该实施例中，以无人设备的初始地标为起始点，依次获取待拣选商品对应的地标，将获取的各地标构成的路线，作为无人设备的行驶路径，从而能够快速规划无人设备在仓内的行进路线。
在一些实施例中，根据坐标值，计算无人设备的初始地标到各待拣选商品对应的地标的路径距离可以为：计算无人设备的初始地标与任意一个待拣选商品对应的地标，在二维矩阵地图中的坐标距离，若无人设备的初始地标与该任意一个待拣选商品对应的地标不是位于相同的两个相邻主巷道之间，则将该坐标距离作为无人设备的初始地标到该任意一个待拣选商品对应的地标的路径距离；若无人设备的初始地标与该任意一个待拣选商品对应的地标位于相同的两个相邻主巷道之间，且位于不同的货架巷道，则确定无人设备的初始地标到两个相邻主巷道中的第一主巷道的第一地标数，以及无人设备的初始地标到两个相邻主巷道中的第二主巷道的第二地标数，以及确定 该任意一个待拣选商品对应的地标距离第一主巷道的第三地标数，和该任意一个待拣选商品对应的地标距离第二主巷道的第四地标数，计算第一地标数与第三地标数的地标数之和，以及第二地标数与第四地标数的地标数之和；将两个地标数之和中较小的地标数之和在二维矩阵地图中对应的值，与坐标距离相加，得到无人设备的初始地标到该任意一个待拣选商品对应的地标的路径距离。
在一些实施例中，根据坐标值计算各待拣选商品对应的地标间的路径距离，例如为，计算任意两个待拣选商品对应的地标在二维矩阵地图中的坐标距离；若该任意两个待拣选商品对应的地标不是位于相同的两个相邻主巷道之间，或者位于相同的货架巷道，则将该坐标距离作为该任意两个待拣选商品对应的地标间的路径距离；若该任意两个待拣选商品对应的地标位于相同的两个相邻主巷道之间，且位于不同的货架巷道，则确定该任意两个待拣选商品中第一待拣选商品对应的地标到两个相邻主巷道中的第一主巷道的第一地标数，以及第一待拣选商品对应的地标到两个相邻主巷道中的第二主巷道的第二地标数，以及该任意两个待拣选商品中第二待拣选商品对应的地标到第一主巷道的第三地标数，以及第二待拣选商品对应的地标到第二主巷道的第四地标数，计算第一地标数与第三地标数的地标数之和，以及第二地标数与第四地标数的地标数之和；将两个地标数之和中较小的地标数之和在二维矩阵地图中对应的值，与坐标距离相加，得到两个待拣选商品对应的地标间的路径距离。
在一些实施例中，无人设备的初始地标与各待拣选商品对应的地标，在二维矩阵地图的坐标可以表示为[X，Y，是否十字巷道，地标KEY，北_地标KEY，南_地标KEY，西_地标KEY，东_地标KEY，上_地标数，下_地标数]。其中，若无人设备所在的地标在二维矩阵地图中标为十字巷道，则说明该无人设备可以往任何方向移动。地标KEY为地标的标识，根据地标KEY就可以查询到地标在二维矩阵地图中的坐标[X，Y]。根据[北_地标KEY，南_地标KEY，西_地标KEY，东_地标KEY，上_地标数]，也可以确定地标在二维矩阵地图中的坐标[X，Y]。KEY_后面的号码为唯一编码，可以有序、也可以无序，其中，KEY为Null，则代表对应的地标为空，即为实物或空地。上_地标数表示坐标[X，Y]在Y轴正方向到最近主巷道的地标数，下_地标数表示坐标[X，Y]在Y轴负方向到最近主巷道的地标数，该参数用来决策无人设备向哪一方向移动可以最快到达主巷道。
无人设备的初始地标到各待拣选商品对应的地标的路径距离计算公式，或者各待拣选商品对应的地标间的路径距离可以表示为|X1–X2|+|Y1–Y2|+M，其中，(X1， Y1)和(X2，Y2)为两个地标点，当两个地标点位于不同的货架巷道，且二者在相同的两个相邻主巷道之间时，此时两个点不能直达，无人设备只能通过主巷道路径，才能移动到目标地标点。因此，需要将两地标点移动到同一巷道的地标数量值进行统计，可以按照向上移动到主巷道方向的地标数量统计或者向下移动到主巷道方向的地标数量统计，二者的和为M。如果两个点在不同的两个货架巷道内，且二者不在相同的两个相邻主巷道之间时，M为0。
例如，如图4所示，无人设备的初始地标A在二维矩阵地图中的坐标为[13，2，否，KEY_000012，北_KEY_000032，南_KEY_000075，西_KEY_000045，东_KEY_000047，0，0]；商品B对应的地标在二维矩阵地图中的坐标为[7，4，否，KEY_000112，北_KEY_000099，南_KEY_000138，西_KEY_000111，东_KEY_000113，2，1]；商品C对应的地标在二维矩阵地图中的坐标为[3，6，否，KEY_000164，北_KEY_000145，南_KEY_000178，西_KEY_000161，东_KEY_000165，1，2]；商品D对应的地标在二维矩阵地图中的坐标为[7，10，否，KEY_000164，北_KEY_000145，南_KEY_000178，西_KEY_000161，东_KEY_000165，2，1]；商品E对应的地标在二维矩阵地图中的坐标为[3，12，否，KEY_000197，北_KEY_000173，南_KEY_000219，西_KEY_000196，东_KEY_000198，1，2]；商品F对应的地标在二维矩阵地图中的坐标为[7，12，否，KEY_000210，北_KEY_000199，南_KEY_000225，西_KEY_000207，东_KEY_000212，1，2]。表1中示出无人设备的初始地标到各待拣选商品对应的地标的路径距离，以及各待拣选商品对应的地标间的路径距离。
A[13,2] B[7,4] |13-7|+|2-4|+0＝6+2＝8
A[13,2] C[3,6] |13-3|+|2-6|+0＝10+4＝14
A[13,2] D[7,10] |13-7|+|2-10|+0＝6+8＝14
A[13,2] E[3,12] |13-3|+|2-12|+0＝10+10＝20
A[13,2] F[7,12] |13-7|+|2-12|+0＝6+10＝16
B[7,4] C[3,6] |7-3|+|4-6|+0＝4+2＝6
B[7,4] D[7,10] |7-7|+|4-10|+0＝0+6＝6
B[7,4] E[3,12] |7-3|+|4-12|+0＝4+8＝12
B[7,4] F[7,12] |7-7|+|4-12|+0＝0+8＝8
C[3,6] D[7,10] |3-7|+|6-10|+0＝4+4＝8
C[3,6] E[3,12] |3-3|+|6-12|+0＝0+6＝6
C[3,6] F[7,12] |3-7|+|6-12|+0＝4+6＝10
D[7,10] E[3,12] |7-3|+|10-12|+0＝4+2＝6
D[7,10] F[7,12] |7-7|+|10-12|+0＝0+2＝2
E[3,12] F[7,12] |3-7|+|12-12|+(1+1)＝4+0+2＝6
表1
通过表1计算出的路径距离，可以依次选取商品对应的地标。首先，选取起始点[A(0)，ALL(0)]，其中，ALL()的括号内的数值为路径距离，字母括号中的数值为该地标与前一地标的路径距离值，若地标为初始地标，则字母括号中的值为0。
第二步，从A点开始，获取与A点路径距离最近的地标，即B点，组成地标列表[A(0)，B(8)，ALL(8)]，其中，B(8)表示B点与A点的路径距离为8。
第三步，获取从B点开始，获取与B点路径距离最近的地标，由于C或D距离B点的路径距离都为6，故形成两条路线，[A(0)，B(8)，C(6)，ALL(14)]以及[A(0)，B(8)，D(6)，ALL(14)]。
第四步，两条线路分别选择对应的下一最近距离点，即[A(0)，B(8)，C(6)，E(6)，ALL(20)]以及[A(0)，B(8)，D(6)，F(2)，ALL(16)]。
第五步，两条线路分别选择对应的下一最近距离点，E到D和F距离相同，因此，形成三条路线[A(0)，B(8)，C(6)，E(6)，D(6)，ALL(26)]、[A(0)，B(8)，C(6)，E(6)，F(6)，ALL(26)]以及[A(0)，B(8)，D(6)，F(2)，E(6)，ALL(22)]。
第六步，获取最后一个地标，即[A(0)，B(8)，C(6)，E(6)，D(6)，F(2)，ALL(28)]，[A(0)，B(8)，C(6)，E(6)，F(6)，D(2)，ALL(28)]以及[A(0)，B(8)，D(6)，F(2)，E(6)，C(6)，ALL(28)]。
通过上述步骤，可以确定无人设备的行驶路径，从第六步可以看出，形成的三条路径的长度是一样的，因此，可以根据下一步规划的初始起点选择多条行驶路径中的最优路径。可以选择多条行驶路径中，最后一个待拣选商品对应的地标距离下一步规划的初始起点最近的行驶路径，作为最优路径。例如，若下一步规划为无人设备回到初始地标，则选择多条行驶路径中，最后一个待拣选商品对应的地标距离初始地标最近的行驶路径，作为最优路径。若拣选任务完成后，还需要进行下一任务的执行，则可根据下一任务的整体布局，将最后点作为下一任务的起始点即可。
在上述实施例中，在无人设备进行行进路线规划时，直接基于二维矩阵地图的坐标值进行计算，计算逻辑更简单、复杂度更低，对硬件计算能力的需求更小。在仓内的货架、地标增加、减少时，通过遍历修改坐标即可完成整个地图的修改。
图5为本公开无人设备路径规划装置的一些实施例的结构示意图。该装置包括地标位置确定单元510、地标获取单元520和行驶路径确定单元530。
地标位置确定单元510被配置为确定仓库内的各个地标位置。其中，地标可以包括货架地标和主巷道地标，无人设备在仓库内沿地标行进，通过地标可以判断出无人设备当前所处的位置，并由此决定下一个行进方向。
地标获取单元520被配置为以当前地标作为当前节点，获取与当前节点路径距离最近的待拣选商品对应的地标，并将获取的待拣选商品对应的地标作为当前节点，其中，当前节点的初始值为无人设备的初始地标；判断当前节点是否为最后一个待拣选商品对应的地标；若是，则停止再次执行获取与当前节点路径距离最近的待拣选商品对应的地标，并将获取的待拣选商品对应的地标作为当前节点的步骤，否则，重复执行获取与当前节点路径距离最近的待拣选商品对应的地标，并将获取的待拣选商品对应的地标作为当前节点的步骤。
行驶路径确定单元530被配置为将无人设备的初始地标以及依次选取的待拣选商品对应的地标构成的线路，作为无人设备的行驶路径。
在该实施例中，以无人设备的初始地标为起始点，依次获取待拣选商品对应的地标，将各地标构成的路线作为无人设备的行驶路径，从而能够快速规划无人设备在仓内的行进路线。
图6为本公开无人设备路径规划装置的另一些实施例的结构示意图。该装置包括路径距离确定单元610，被配置为将仓库内的各个地标位置映射到二维矩阵地图中；确定无人设备的初始地标在二维矩阵地图中的坐标值，以及各待拣选商品对应的地标在二维矩阵地图中的坐标值；根据坐标值，计算无人设备的初始地标到各待拣选商品对应的地标的路径距离，以及各待拣选商品对应的地标间的路径距离。
在一些实施例中，路径距离确定单元610被配置为计算无人设备的初始地标与任意一个待拣选商品对应的地标，在二维矩阵地图中的坐标距离；判断无人设备的初始地标与该任意一个待拣选商品对应的地标是否位于相同的两个相邻主巷道之间；若无人设备的初始地标与该任意一个待拣选商品对应的地标位于相同的两个相邻主巷道之间，则确定无人设备的初始地标到该相同的两个相邻主巷道中的第一主巷道的第一 地标数，以及无人设备的初始地标到相同的两个相邻主巷道中的第二主巷道的第二地标数，以及确定该任意一个待拣选商品对应的地标距离第一主巷道的第三地标数，和该任意一个待拣选商品对应的地标距离第二主巷道的第四地标数，计算第一地标数与第三地标数的地标数之和，以及第二地标数与第四地标数的地标数之和；将两个地标数之和中较小的地标数之和在二维矩阵地图中对应的值，与坐标距离相加，得到无人设备的初始地标到该任意一个待拣选商品对应的地标的路径距离。若无人设备的初始地标与待拣选商品对应的地标不是位于相同的两个相邻主巷道之间，则将该坐标距离作为无人设备的初始地标到各待拣选商品对应的地标的路径距离。
在一些实施例中，路径距离确定单元610被配置为计算任意两个待拣选商品对应的地标在二维矩阵地图中的坐标距离；判断该任意两个待拣选商品对应的地标是否位于相同的两个相邻主巷道之间；若该任意两个待拣选商品对应的地标位于相同的两个相邻主巷道之间，则确定该任意两个待拣选商品中第一待拣选商品对应的地标到相同的两个相邻主巷道中的第一主巷道的第一地标数，以及第一待拣选商品对应的地标到相同的两个相邻主巷道中的第二主巷道的第二地标数，以及该任意两个待拣选商品中第二待拣选商品对应的地标到第一主巷道的第三地标数以及第二待拣选商品对应的地标到第二主巷道的第四地标数；计算第一地标数与第三地标数的地标数之和，以及第二地标数与第四地标数的地标数之和；将两个地标数之和中较小的地标数之和在二维矩阵地图中对应的值，与坐标距离相加，得到该任意两个待拣选商品对应的地标间的路径距离。若两个待拣选商品对应的地标不是位于相同的两个相邻主巷道之间，则将该坐标距离作为该任意两个待拣选商品对应的地标间的路径距离。
在本公开的另一些实施例中，该装置还包括最优路径确定单元620，被配置为若选择出的无人设备的行驶路径有多条，则根据下一步规划的初始起点选择多条行驶路径中的最优路径。例如，可以选择多条行驶路径中，最后一个待拣选商品对应的地标距离下一步规划的初始起点最近的行驶路径，作为最优路径。若下一步规划为无人设备回到初始地标，则选择多条行驶路径中，最后一个待拣选商品对应的地标距离初始地标最近的行驶路径，作为最优路径。若拣选任务完成后，还需要进行下一任务的执行，则可根据下一任务的整体布局，将最后点作为下一任务的起始点即可。
在上述实施例中，在无人设备进行行进路线规划时，直接基于二维矩阵地图的坐标值进行计算，计算逻辑更简单、复杂度更低，对硬件计算能力的需求更小。在仓内的货架、地标增加、减少时，通过遍历修改坐标即可完成整个地图的修改。
图7为本公开无人设备路径规划装置的再一些实施例的结构示意图。该装置包括存储器710和处理器720，其中：存储器710可以是磁盘、闪存或其它任何非易失性存储介质。存储器被配置为存储图1所对应实施例中的指令。处理器720耦接至存储器710，可以作为一个或多个集成电路来实施，例如微处理器或微控制器。该处理器720被配置为执行存储器中存储的指令。
在一些实施例中，还可以如图8所示，该装置800包括存储器810和处理器820。处理器820通过BUS总线830耦合至存储器810。该装置800还可以通过存储接口840连接至外部存储装置850以便调用外部数据，还可以通过网络接口860连接至网络或者另外一台计算机系统(未标出)，此处不再进行详细介绍。
在该实施例中，通过存储器存储数据指令，再通过处理器处理上述指令，以无人设备的初始地标为起始点，依次获取待拣选商品对应的地标，将各地标构成的路线作为无人设备的行驶路径，从而能够快速规划无人设备在仓内的行进路线。
在另一些实施例中，一种计算机可读存储介质，其上存储有计算机程序指令，该指令被处理器执行时实现图1所对应实施例中的方法的步骤。本领域内的技术人员应明白，本公开的实施例可提供为方法、装置、或计算机程序产品。因此，本公开可采用完全硬件实施例、完全软件实施例、或结合软件和硬件方面的实施例的形式。而且，本公开可采用在一个或多个其中包含有计算机可用程序代码的计算机可用非瞬时性存储介质(包括但不限于磁盘存储器、CD-ROM、光学存储器等)上实施的计算机程序产品的形式。
本公开是参照根据本公开实施例的方法、设备(系统)和计算机程序产品的流程图和/或方框图来描述的。应理解可由计算机程序指令实现流程图和/或方框图中的每一流程和/或方框以及流程图和/或方框图中的流程和/或方框的结合。可提供这些计算机程序指令到通用计算机、专用计算机、嵌入式处理机或其他可编程数据处理设备的处理器以产生一个机器，使得通过计算机或其他可编程数据处理设备的处理器执行的指令产生用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的装置。
这些计算机程序指令也可存储在能引导计算机或其他可编程数据处理设备以特定方式工作的计算机可读存储器中，使得存储在该计算机可读存储器中的指令产生包括指令装置的制造品，该指令装置实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能。
这些计算机程序指令也可装载到计算机或其他可编程数据处理设备上，使得在计算机或其他可编程设备上执行一系列操作步骤以产生计算机实现的处理，从而在计算机或其他可编程设备上执行的指令提供用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的步骤。
至此，已经详细描述了本公开。为了避免遮蔽本公开的构思，没有描述本领域所公知的一些细节。本领域技术人员根据上面的描述，完全可以明白如何实施这里公开的技术方案。
虽然已经通过示例对本公开的一些特定实施例进行了详细说明，但是本领域的技术人员应该理解，以上示例仅是为了进行说明，而不是为了限制本公开的范围。本领域的技术人员应该理解，可在不脱离本公开的范围和精神的情况下，对以上实施例进行修改。本公开的范围由所附权利要求来限定。

Claims (20)

  1. 一种无人设备路径规划方法，包括：
    以当前地标作为当前节点，获取与所述当前节点路径距离最近的待拣选商品对应的地标，并将获取的待拣选商品对应的地标作为所述当前节点，其中，所述当前节点的初始值为无人设备的初始地标；
    判断所述当前节点是否为最后一个待拣选商品对应的地标；
    若是，则停止再次执行获取与所述当前节点路径距离最近的待拣选商品对应的地标，并将获取的待拣选商品对应的地标作为当前节点的步骤，否则，重复执行获取与所述当前节点路径距离最近的待拣选商品对应的地标，并将获取的待拣选商品对应的地标作为当前节点的步骤；
    将所述无人设备的初始地标以及依次选取的待拣选商品对应的地标构成的线路，作为所述无人设备的行驶路径。
  2. 根据权利要求1所述的无人设备路径规划方法，还包括：
    确定仓库内的各个地标位置；
    将仓库内的各个地标映射到二维矩阵地图中；
    确定所述无人设备的初始地标在所述二维矩阵地图中的坐标值，以及各待拣选商品对应的地标在所述二维矩阵地图中的坐标值；
    根据坐标值，计算所述无人设备的初始地标到各待拣选商品对应的地标的路径距离，以及各待拣选商品对应的地标间的路径距离。
  3. 根据权利要求2所述的无人设备路径规划方法，其中，根据坐标值，计算所述无人设备的初始地标到各待拣选商品对应的地标的路径距离包括：
    计算所述无人设备的初始地标与任意一个待拣选商品对应的地标，在所述二维矩阵地图中的坐标距离；
    若所述无人设备的初始地标与所述任意一个待拣选商品对应的地标位于不同的货架巷道，则判断所述无人设备的初始地标与所述任意一个待拣选商品对应的地标是否位于相同的两个相邻主巷道之间；
    若所述无人设备的初始地标与所述任意一个待拣选商品对应的地标位于相同的 两个相邻主巷道之间，则确定所述无人设备的初始地标到所述两个相邻主巷道中的第一主巷道的第一地标数，以及所述无人设备的初始地标到所述两个相邻主巷道中的第二主巷道的第二地标数，以及确定所述任意一个待拣选商品对应的地标距离所述第一主巷道的第三地标数，和所述任意一个待拣选商品对应的地标距离所述第二主巷道的第四地标数，计算所述第一地标数与所述第三地标数的地标数之和，以及所述第二地标数与第四地标数的地标数之和；
    将两个地标数之和中较小的地标数之和在所述二维矩阵地图中对应的值，与所述坐标距离相加，得到所述无人设备的初始地标到所述任意一个待拣选商品对应的地标的路径距离。
  4. 根据权利要求3所述的无人设备路径规划方法，其中，
    若所述无人设备的初始地标与所述任意一个待拣选商品对应的地标不是位于相同的两个相邻主巷道之间，则将所述坐标距离作为所述无人设备的初始地标到所述任意一个待拣选商品对应的地标的路径距离。
  5. 根据权利要求2所述的无人设备路径规划方法，其中，根据坐标值，计算各待拣选商品对应的地标间的路径距离包括：
    计算任意两个待拣选商品对应的地标，在所述二维矩阵地图中的坐标距离；
    若所述任意两个待拣选商品对应的地标位于不同的货架巷道，则判断所述任意两个待拣选商品对应的地标是否位于相同的两个相邻主巷道之间；
    若所述任意两个待拣选商品对应的地标位于相同的两个相邻主巷道之间，则确定所述任意两个待拣选商品中第一待拣选商品对应的地标到所述两个相邻主巷道中的第一主巷道的第一地标数，以及所述第一待拣选商品对应的地标到所述两个相邻主巷道中的第二主巷道的第二地标数，以及所述任意两个待拣选商品中第二待拣选商品对应的地标到所述第一主巷道的第三地标数，以及所述第二待拣选商品对应的地标到所述第二主巷道的第四地标数，计算所述第一地标数与所述第三地标数的地标数之和，以及所述第二地标数与所述第四地标数的地标数之和；
    将两个地标数之和中较小的地标数之和在所述二维矩阵地图中对应的值，与所述坐标距离相加，得到所述任意两个待拣选商品对应的地标间的路径距离。
  6. 根据权利要求5所述的无人设备路径规划方法，其中，
    若所述任意两个待拣选商品对应的地标不是位于相同的两个相邻主巷道之间，则将所述坐标距离作为所述任意两个待拣选商品对应的地标间的路径距离。
  7. 根据权利要求1-6任一所述的无人设备路径规划方法，还包括：
    若选择出的所述无人设备的行驶路径有多条，则根据下一步规划的初始起点，选择多条行驶路径中的最优路径。
  8. 根据权利要求7所述的无人设备路径规划方法，其中，根据下一步规划的初始起点选择多条行驶路径中的最优路径包括：
    选择多条行驶路径中，最后一个待拣选商品对应的地标距离所述下一步规划的初始起点最近的行驶路径，作为最优路径。
  9. 根据权利要求8所述的无人设备路径规划方法，其中，
    若下一步规划为所述无人设备回到初始地标，则选择多条行驶路径中，最后一个待拣选商品对应的地标距离所述初始地标最近的行驶路径，作为最优路径。
  10. 一种无人设备路径规划装置，包括：
    地标获取单元，被配置为以当前地标作为当前节点，获取与所述当前节点路径距离最近的待拣选商品对应的地标，将获取的待拣选商品对应的地标作为所述当前节点，其中，所述当前节点的初始值为无人设备的初始地标；判断所述当前节点是否为最后一个待拣选商品对应的地标；若是，则停止再次执行获取与所述当前节点路径距离最近的待拣选商品对应的地标，并将获取的待拣选商品对应的地标作为当前节点的步骤，否则，重复执行获取与所述当前节点路径距离最近的待拣选商品对应的地标，并将获取的待拣选商品对应的地标作为当前节点的步骤；
    行驶路径确定单元，被配置为将所述无人设备的初始地标以及依次选取的待拣选商品对应的地标构成的线路，作为所述无人设备的行驶路径。
  11. 根据权利要求10所述的无人设备路径规划装置，还包括：
    地标位置确定单元，被配置为确定仓库内的各个地标位置；
    路径距离确定单元，被配置为将仓库内的各个地标映射到二维矩阵地图中；确定所述无人设备的初始地标在所述二维矩阵地图中的坐标值，以及各待拣选商品对应的地标在所述二维矩阵地图中的坐标值；根据坐标值，计算所述无人设备的初始地标到各待拣选商品对应的地标的路径距离，以及各待拣选商品对应的地标间的路径距离。
  12. 根据权利要求11所述的无人设备路径规划装置，其中，
    所述路径距离确定单元被配置为计算所述无人设备的初始地标与任意一个待拣选商品对应的地标，在所述二维矩阵地图中的坐标距离；若所述无人设备的初始地标与所述任意一个待拣选商品对应的地标位于不同的货架巷道，则判断所述无人设备的初始地标与所述任意一个待拣选商品对应的地标是否位于相同的两个相邻主巷道之间；若所述无人设备的初始地标与所述任意一个待拣选商品对应的地标位于相同的两个相邻主巷道之间，则确定所述无人设备的初始地标到所述两个相邻主巷道中的第一主巷道的第一地标数，以及所述无人设备的初始地标到所述两个相邻主巷道中的第二主巷道的第二地标数，以及确定所述任意一个待拣选商品对应的地标距离所述第一主巷道的第三地标数，和所述任意一个待拣选商品对应的地标距离所述第二主巷道的第四地标数，计算所述第一地标数与所述第三地标数的地标数之和，以及所述第二地标数与所述第四地标数的地标数之和；将两个地标数之和中较小的地标数之和在所述二维矩阵地图中对应的值，与所述坐标距离相加，得到所述无人设备的初始地标到各待拣选商品对应的地标的路径距离。
  13. 根据权利要求12所述的无人设备路径规划装置，其中，
    所述路径距离确定单元还被配置为若所述无人设备的初始地标与所述任意一个待拣选商品对应的地标不是位于相同的两个相邻主巷道之间，则将所述坐标距离作为所述无人设备的初始地标到所述任意一个待拣选商品对应的地标的路径距离。
  14. 根据权利要求11所述的无人设备路径规划装置，其中，
    所述路径距离确定单元被配置为计算任意两个待拣选商品对应的地标，在所述二维矩阵地图中的坐标距离；若所述任意两个待拣选商品对应的地标位于不同的货架巷道，则判断所述任意两个待拣选商品对应的地标是否位于相同的两个相邻主巷道之间；若所述任意两个待拣选商品对应的地标位于相同的两个相邻主巷道之间，则确定 所述任意两个待拣选商品中第一待拣选商品对应的地标到所述两个相邻主巷道中的第一主巷道的第一地标数，以及所述第一待拣选商品对应的地标到所述两个相邻主巷道中的第二主巷道的第二地标数，以及所述任意两个待拣选商品中第二待拣选商品对应的地标到所述第一主巷道的第三地标数，以及所述第二待拣选商品对应的地标到所述第二主巷道的第四地标数；计算所述第一地标数与所述第三地标数的地标数之和，以及所述第二地标数与所述第四地标数的地标数之和；将两个地标数之和中较小的地标数之和，在所述二维矩阵地图中对应的值，与所述坐标距离相加，得到所述任意两个待拣选商品对应的地标间的路径距离。
  15. 根据权利要求14所述的无人设备路径规划装置，其中，
    所述路径距离确定单元还被配置为若所述任意两个待拣选商品对应的地标不是位于相同的两个相邻主巷道之间，则将所述坐标距离作为所述任意两个待拣选商品对应的地标间的路径距离。
  16. 根据权利要求10-15任一所述的无人设备路径规划装置，还包括：
    最优路径确定单元，被配置为若选择出的所述无人设备的行驶路径有多条，则根据下一步规划的初始起点，选择多条行驶路径中的最优路径。
  17. 根据权利要求16所述的无人设备路径规划装置，其中，
    所述最优路径确定单元被配置为选择多条行驶路径中，最后一个待拣选商品对应的地标距离所述下一步规划的初始起点最近的行驶路径，作为最优路径。
  18. 根据权利要求17所述的无人设备路径规划装置，其中，
    所述最优路径确定单元被配置为若下一步规划为所述无人设备回到初始地标，则选择多条行驶路径中，最后一个待拣选商品对应的地标距离所述初始地标最近的行驶路径，作为最优路径。
  19. 一种无人设备路径规划装置，包括：
    存储器；以及
    耦接至所述存储器的处理器，所述处理器被配置为基于存储在所述存储器的指令 执行如权利要求1至9任一项所述的无人设备路径规划方法。
  20. 一种计算机可读存储介质，其上存储有计算机程序指令，该指令被处理器执行时实现权利要求1至9任一项所述的无人设备路径规划方法。
PCT/CN2019/099326 2018-09-20 2019-08-06 无人设备路径规划方法和装置 WO2020057278A1 (zh)

Priority Applications (2)

Application Number Priority Date Filing Date Title
EP19863834.8A EP3828789A4 (en) 2018-09-20 2019-08-06 METHOD AND APPARATUS FOR PATH PLANNING AN UNDRIVEN DEVICE
US17/271,426 US12001212B2 (en) 2018-09-20 2019-08-06 Path planning method and device for unmanned device

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
CN201811096783.2A CN110929911A (zh) 2018-09-20 2018-09-20 无人设备路径规划方法和装置
CN201811096783.2 2018-09-20

Publications (1)

Publication Number Publication Date
WO2020057278A1 true WO2020057278A1 (zh) 2020-03-26

Family

ID=69855268

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/CN2019/099326 WO2020057278A1 (zh) 2018-09-20 2019-08-06 无人设备路径规划方法和装置

Country Status (4)

Country Link
US (1) US12001212B2 (zh)
EP (1) EP3828789A4 (zh)
CN (1) CN110929911A (zh)
WO (1) WO2020057278A1 (zh)

Families Citing this family (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN115456249B (zh) * 2022-08-16 2024-03-22 上海聚水潭网络科技有限公司 一种分拣行走路径优化方法及系统

Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP2442200A2 (en) * 2009-12-17 2012-04-18 Deere & Company System and method for area coverage using sector decomposition
CN102591332A (zh) * 2011-01-13 2012-07-18 同济大学 用于无人驾驶汽车局部路径规划的装置及方法
CN102768537A (zh) * 2012-07-27 2012-11-07 苏州工业园区职业技术学院 自动导引车辆无线控制系统
CN102955476A (zh) * 2012-11-12 2013-03-06 宁波韵升股份有限公司 一种基于无线射频识别技术的agv路径规划方法
CN106168803A (zh) * 2016-04-18 2016-11-30 深圳众为兴技术股份有限公司 一种用于移动机器人的位置感知方法

Family Cites Families (37)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
DE102006025620A1 (de) * 2006-05-24 2007-11-29 SSI Schäfer Noell GmbH Lager- und Systemtechnik Regallager und Kommissionierverfahren
US8948932B2 (en) * 2007-10-30 2015-02-03 Raytheon Company Unmanned vehicle route management system
KR101194603B1 (ko) * 2009-03-12 2012-10-25 한국전자통신연구원 무인 운송 장치 및 그 방법
CN101968860A (zh) * 2010-10-09 2011-02-09 北京物资学院 订单拣选方法及系统
JP5362691B2 (ja) * 2010-11-30 2013-12-11 株式会社小松製作所 無人車両の走行システムにおける走行制御方法および無人車両の走行システム
WO2012141601A2 (en) * 2011-04-11 2012-10-18 Crown Equipment Limited Method and apparatus for efficient scheduling for multiple automated non-holonomic vehicles using a coordinated path planner
US9384668B2 (en) * 2012-05-09 2016-07-05 Singularity University Transportation using network of unmanned aerial vehicles
US8965561B2 (en) * 2013-03-15 2015-02-24 Cybernet Systems Corporation Automated warehousing using robotic forklifts
US9454151B2 (en) * 2014-05-20 2016-09-27 Verizon Patent And Licensing Inc. User interfaces for selecting unmanned aerial vehicles and mission plans for unmanned aerial vehicles
US9671790B2 (en) * 2014-05-20 2017-06-06 Verizon Patent And Licensing Inc. Scheduling of unmanned aerial vehicles for mission performance
CA2975959A1 (en) * 2015-02-05 2016-08-11 Akash Gupta Apparatus and method for handling goods
US9758301B2 (en) * 2015-03-24 2017-09-12 Joseph Porat System and method for overhead warehousing
CN104992241B (zh) * 2015-07-02 2019-09-20 北京京东尚科信息技术有限公司 一种拣货路径生成方法、生成装置及相应仓储管理系统
US9862488B2 (en) * 2015-08-28 2018-01-09 Mcafee, Llc Location verification and secure no-fly logic for unmanned aerial vehicles
JP6970666B2 (ja) * 2015-10-22 2021-11-24 グレイ オレンジ ピーティーイー． リミテッド 倉庫内の資源を管理する方法
US11341858B2 (en) * 2016-06-10 2022-05-24 Metal Raptor, Llc Managing dynamic obstructions in air traffic control systems for passenger drones and unmanned aerial vehicles
US11164149B1 (en) * 2016-08-31 2021-11-02 Corvus Robotics, Inc. Method and system for warehouse inventory management using drones
US10198955B1 (en) * 2016-09-08 2019-02-05 Amazon Technologies, Inc. Drone marker and landing zone verification
US10241516B1 (en) * 2016-09-29 2019-03-26 Amazon Technologies, Inc. Autonomous ground vehicles deployed from facilities
EP3523227A4 (en) * 2016-10-06 2020-06-24 Robert D. Ahmann AUTOMATED WAREHOUSE DESIGNS AND SYSTEM
WO2018094019A1 (en) * 2016-11-16 2018-05-24 Staples, Inc. Autonomous multimodal logistics
KR101931342B1 (ko) * 2016-12-22 2018-12-20 쿠팡 주식회사 상품 분류 장치, 방법, 및 컴퓨터 프로그램
US10308430B1 (en) * 2016-12-23 2019-06-04 Amazon Technologies, Inc. Distribution and retrieval of inventory and materials using autonomous vehicles
US10775792B2 (en) * 2017-06-13 2020-09-15 United Parcel Service Of America, Inc. Autonomously delivering items to corresponding delivery locations proximate a delivery route
US11727812B2 (en) * 2017-07-27 2023-08-15 Beihang University Airplane flight path planning method and device based on the pigeon-inspired optimization
US10860036B2 (en) * 2018-02-09 2020-12-08 Micron Technology, Inc. Repurposing autonomous vehicles for package delivery
US11993396B2 (en) * 2018-04-12 2024-05-28 Laitram, L.L.C. Autonomous package storage and retrieval system using a drone
US10916150B2 (en) * 2018-05-03 2021-02-09 Arkidan Systems Inc. Computer-assisted aerial surveying and navigation
WO2019242652A1 (zh) * 2018-06-21 2019-12-26 北京极智嘉科技有限公司 机器人调度、机器人路径的控制方法、服务器和存储介质
US20200182634A1 (en) * 2018-12-05 2020-06-11 Uxr Llc Providing path directions relating to a shopping cart
US11049339B2 (en) * 2019-03-29 2021-06-29 Wipro Limited Method and system for validating odometer performance in an autonomous vehicle in real-time
CN111947673B (zh) * 2019-05-17 2022-09-06 北京京东振世信息技术有限公司 无人车路径控制方法、装置和系统
US11430341B2 (en) * 2019-05-31 2022-08-30 Cognizant Technology Solutions Sindia Pvt. Ltd. System and method for optimizing unmanned aerial vehicle based warehouse management
US10783599B1 (en) * 2019-06-24 2020-09-22 William Dean Hartman System and method for autonomous package delivery and collection
CN110766444B (zh) * 2019-09-18 2023-09-19 五邑大学 商场自动购物方法、存储介质、电子设备及设备
US11449080B2 (en) * 2019-10-29 2022-09-20 Honeywell International Inc. UAV flight management planner
EP4300244A1 (en) * 2022-06-30 2024-01-03 Tata Consultancy Services Limited Method and system for navigation of robot from one area to another area

Patent Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP2442200A2 (en) * 2009-12-17 2012-04-18 Deere & Company System and method for area coverage using sector decomposition
CN102591332A (zh) * 2011-01-13 2012-07-18 同济大学 用于无人驾驶汽车局部路径规划的装置及方法
CN102768537A (zh) * 2012-07-27 2012-11-07 苏州工业园区职业技术学院 自动导引车辆无线控制系统
CN102955476A (zh) * 2012-11-12 2013-03-06 宁波韵升股份有限公司 一种基于无线射频识别技术的agv路径规划方法
CN106168803A (zh) * 2016-04-18 2016-11-30 深圳众为兴技术股份有限公司 一种用于移动机器人的位置感知方法

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
See also references of EP3828789A4 *

Also Published As

Publication number Publication date
US12001212B2 (en) 2024-06-04
EP3828789A4 (en) 2022-04-20
EP3828789A1 (en) 2021-06-02
US20210311483A1 (en) 2021-10-07
CN110929911A (zh) 2020-03-27

Similar Documents

Publication Publication Date Title
CN108629531B (zh) 货物运输方法和用于货物运输的装置
JP7161040B2 (ja) コンテキスト拡張マップ・レイヤを与えるためのゾーン・エンジン
KR102383800B1 (ko) 계획된 로봇 주행 경로를 이용한 탐색
KR102121132B1 (ko) 시멘틱 매핑을 이용한 로봇 네비게이션
US20170278047A1 (en) Dynamic task interleaving in robot assisted order-fulfillment operations
JP7369779B2 (ja) ロボット渋滞管理
JP2019502613A (ja) 倉庫内の資源を管理する方法
US20150120125A1 (en) Systems, methods, and industrial vehicles for determining the visibility of features
JP2019529279A (ja) ロボット支援の注文履行動作における可動ベース用の品物保管アレイ
CN103782247A (zh) 用于使用预先安置的物体定位工业车辆的方法和装置
CN103582803A (zh) 共享与自动化工业车辆相关联的地图数据的方法和装置
US10078333B1 (en) Efficient mapping of robot environment
CN109784791B (zh) 订单分配方法和装置
CN113960969A (zh) 一种基于大数据的物流仓储的调度方法及系统
CN113191521B (zh) 路径规划方法、装置及计算机可读存储介质
CN109911272B (zh) 一种基于参考线准则的自由码垛装箱方法
CN112633590B (zh) 一种用于四向穿梭车的智能入库方法及系统
WO2020057278A1 (zh) 无人设备路径规划方法和装置
JPWO2017085769A1 (ja) 商品ピッキング・格納作業指示装置
CN110188290B (zh) 一种基于星型拓扑结构的分布式无人仓库位推荐智能算法
WO2021077861A1 (zh) 订单处理方法、装置及存储介质
CN112101834A (zh) 仓库中储位的定位方法、装置、系统及介质
CN111047249A (zh) 一种货架重新定位方法及系统
CN116629734A (zh) 仓储系统物品拣选路径的规划方法、装置、设备及介质
CN115639817A (zh) 一种路径的轨迹修正方法、装置、设备和介质

Legal Events

Date Code Title Description
121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 19863834

Country of ref document: EP

Kind code of ref document: A1

ENP Entry into the national phase

Ref document number: 2019863834

Country of ref document: EP

Effective date: 20210226

NENP Non-entry into the national phase

Ref country code: DE