Patent Description:
Many warehouse management systems require workers to scan items manually, which is a time-consuming and error-prone process. Accordingly, some warehouse systems may use unmanned aerial vehicles (UAVs) to perform such inventory validation tasks. In one example, UAVs (e.g., drones) may use optical sensors (e.g., cameras), radio-frequency identification (RFID) scanners, or other near-field communication technologies to locate and identify inventory items in a warehouse and communicate collected information to a warehouse management system. Thus, the warehouse management system may detect individual items and accurately track inventory without requiring a worker to scan items manually.

In one approach, a warehouse management system may generate routes for drones to perform inventory validation tasks using static information (e.g., a warehouse map). For example, the warehouse management system may generate routes by determining the shortest route to desired locations (e.g., through aisles of a warehouse). However, it may be difficult for drones to quickly navigate through a warehouse to a desired location without risking collisions with inventory moving devices (e.g., forklifts) moving inventory throughout the warehouse. In some approaches, in order to avoid collisions between drones and inventory moving devices, the warehouse management system may rely on the drones to employ collision avoidance technology to avoid colliding with inventory moving devices, and, if necessary, to find an alternative route if there are problems reaching a desired location. However, in such an approach, drones are required to fly much slower than they are capable of flying (e.g., in order to avoid detected obstacles). Additionally, drones may waste a significant amount of time trying to determine an alternative route when an assigned route is blocked.

Consequently, what is needed are techniques to determine obstacle-free paths for drones to desired locations in a warehouse based on dynamic information, including, e.g., the predicted locations of inventory moving devices in the warehouse and available shortcuts through storage racks of the warehouse. Additionally, it would be advantageous to generate shortcuts through storage racks in the warehouse to provide additional path segments through the warehouse to regions of the warehouse where there is difficulty in performing inventory validation tasks and no shortcuts to the regions are currently available.

In some embodiments, methods and systems are provided for determining an obstacle-free path of an aerial vehicle to a desired location in a warehouse. Status of inventory moving tasks for the warehouse are received. At least one location of an inventory moving device in the warehouse is predicted based on the status of the inventory moving tasks. The obstacle-free path is determined based on the predicted at least one location of the inventory moving device.

In some embodiments, the inventory moving tasks include a task to move an inventory item from a first location to a second location in the warehouse.

In some embodiments, at least one location of the inventory moving device in the warehouse may be predicted by identifying a task, among the inventory moving tasks, associated with moving an inventory item from a first location to a second location, determining a predicted route from the first location to the second location for the identified task, and predicting the at least one location of the inventory moving device along the predicted route based on the status of the identified task. In some embodiments, the route may be predicted by analyzing past routes taken by inventory moving devices in the warehouse.

In some embodiments, the obstacle-free path is determined by determining a plurality of paths from a current location of the aerial vehicle to the desired location, based on free space around a plurality of storage racks arranged in the warehouse, and selecting one of the determined plurality of paths that does not intersect the predicted at least one location of the inventory moving device as the obstacle-free path of the aerial vehicle, based on estimated travel times or distances of the aerial vehicle from the current location to the desired location along each of the plurality of paths. In some embodiments, the plurality of storage racks may be arranged into a plurality of rows in a storage area of the warehouse, and the free space around the plurality of storage racks may include aisles separating adjacent ones of the plurality of storage racks arranged in the plurality of rows and at least one thruway of the storage area. In some embodiments, the free space around the plurality of storage racks further includes a shortcut through a first one of the plurality of storage racks that is formed by at least one empty storage location of the first one of the plurality of storage racks.

In some embodiments, the obstacle-free path is determined by determining a plurality of path segments along at least one of: the at least one thruway, one or more of the aisles, or the shortcut. In some embodiments, the shortcut may be generated by instructing the inventory moving device to remove an inventory item from the first one of the plurality of storage racks to create the at least one empty storage location.

In some embodiment, the at least one location of the inventory moving device in the warehouse is predicted by determining a two-dimensional path of the inventory moving device on a ground of the warehouse based on the status of the inventory moving tasks. In some embodiments, the obstacle-free path includes an obstacle-free three-dimensional path.

In some embodiments, the warehouse includes a plurality of storage racks arranged in a storage area of the warehouse. In some embodiments, the obstacle-free three-dimensional path is determined by determining, in space above the two-dimensional path, a plurality of three-dimensional paths from a current location of the aerial vehicle to the desired location, determining whether each of the determined plurality of three-dimensional paths intersects with the inventory moving device, and selecting one of the determined plurality of three-dimensional paths determined to not intersect with the inventory moving device as the obstacle-free three-dimensional path, based on estimated travel times of the aerial vehicle along each of the plurality of three-dimensional paths.

In some embodiments, a method is provided for determining an obstacle-free three-dimensional path of an aerial vehicle to a location in a warehouse. Status of ground-based mobile machines that travel in two-dimension paths on a ground of the warehouse is received. The obstacle-free three-dimensional path is determined based on the status of the ground-based mobile machines.

In some embodiments, methods and systems are provided for requesting a shortcut to be generated in a storage rack to provide a path segment for performing an inventory validation task. Inventory validation tasks in a warehouse including a plurality of storage racks are received. The request for the shortcut to be generated in the storage rack among the plurality of storage racks is based on the received inventory validation tasks.

In some embodiments, requesting the shortcut to be generated in the storage rack includes determining a region of the warehouse where there is difficulty in performing inventory validation tasks, identifying the shortcut to be generated to reach the region of warehouse, and requesting the identified shortcut to be generated in the storage rack.

In some embodiments, the region is determined by determining that one or more inventory validation tasks for the region were not completed within a predetermined amount of time, more than a predetermined number of inventory validation tasks for the region are outstanding, or more than a predetermined number of inventory validation tasks for the region have been pending for more than a predetermined amount of time.

In some embodiments, the region is determined by identifying, from the received inventory validation tasks, more than a predetermined number of inventory validation tasks for the region, and determining that the region has limited access paths. In some embodiments, determining that the region has limited access paths includes determining an obstruction in an existing path segment to the region. In some embodiments, determining that the region has limited access paths includes determining that the shortcut would reduce the time taken to perform the inventory validation tasks for the region by more than a predetermined amount. In some embodiments, determining that the region has limited access paths includes determining that the shortcut would reduce energy consumption of one or more aerial vehicles performing the inventory validation tasks for the region by more than a predetermined amount.

In some embodiments, the plurality of storage racks is arranged in a plurality of rows defining aisles separating adjacent ones of the plurality of rows. In some embodiments, the region is located in an aisle among the aisles separating adjacent ones of the plurality of rows. In some embodiments, determining that the region has limited access paths includes determining that one end of the aisle has an obstruction preventing an aerial vehicle from entering the one end of the aisle to perform the inventory validation.

In some embodiments, the inventory validation tasks are received from a warehouse management system. Results of the inventory validation tasks may be transmitted to the warehouse management system.

In some embodiments, the plurality of storage racks is arranged in a plurality of rows defining aisles separating adjacent ones of the plurality of rows. In some embodiments, requesting the shortcut to be generated in the storage rack includes requesting an inventory item to be removed from at least one storage location of the storage rack such that an aerial vehicle is able to travel between adjacent aisles by traversing through the storage rack at the at least one storage location using the path segment.

In some embodiments, a non-transitory computer-readable medium comprising non-transitory computer-readable instructions encoded thereon for managing a warehouse is provided. The instructions include an instruction for receiving inventory validation tasks in a warehouse including a plurality of storage racks. The instructions further include an instruction for requesting, based on the received inventory validation tasks, a shortcut to be generated in a storage rack of the plurality of storage racks to provide a path segment for performing the validation task.

<FIG> shows a block diagram of an illustrative warehouse system <NUM>, in accordance with some embodiments of this disclosure. System <NUM> may be implemented in any suitable warehouse or location that stores and manages goods, materials, or any other types of objects (e.g., inventory items). For example, system <NUM> may be implemented in large distribution facilities. System <NUM> includes a warehouse management system <NUM> and drone management system <NUM>.

Warehouse management system <NUM> controls warehouse operations. As shown, warehouse management system <NUM> is communicatively coupled to drone management system <NUM>, scanner(s) <NUM>, and inventory moving devices 116A, 116B,. , and 116N (collectively referred to as inventory moving devices <NUM>). Depending on the type of warehouse, warehouse management system <NUM> may control warehouse operations starting from when items enter the warehouse until the objects leave the warehouse. Warehouse management system <NUM> can manage warehouse tasks such as the picking of items from shelves for shipping and storing received items on shelves by generating inventory moving tasks that are communicated to inventory moving devices <NUM>. Warehouse management system <NUM> may track the location of items within the warehouse using barcodes. However, this is only one example, and warehouse management system <NUM> may also track the location of items within the warehouse using RFID tags or any other suitable identifiers. When items arrive, the items are scanned using, e.g., scanners <NUM>. In some situations, the items arrive with one or more barcodes already on the items and one or more of these barcodes are used by warehouse management system <NUM> for tracking purposes. In other situations, barcodes are added to the items or pallets associated with the items.

For various reasons, the location information for items in a warehouse may be inaccurate. For example, a worker may move an item to an incorrect location or a worker may forget to scan a location barcode after moving an item, and thus the location information managed by warehouse management system <NUM> may include errors. These errors can impact upstream and downstream operations and the overall efficiency of a warehouse. Accordingly, warehouse management system <NUM> may request inventory validation tasks to be performed to confirm the location of items in the warehouse. In some embodiments, as explained below, the inventory validation tasks can be transmitted to drone management system <NUM> to be performed autonomously or semi-autonomously.

Warehouse management system <NUM> may comprise processing circuitry <NUM> which may comprise hardware, software or any combination thereof, such as, for example, one or more central processing units (CPUs) configured to execute instructions stored in computer-readable media (e.g., memory) to implement operating system(s) and applications of warehouse management system <NUM> and perform and/or control various operations of the warehouse. Warehouse management system <NUM> may further comprise communication circuitry <NUM> configured to transmit and receive communications from inventory moving devices <NUM>, scanners <NUM>, and drone management system <NUM>. Communication circuitry <NUM> may also be configured to transmit and receive communications between components within warehouse management system <NUM>.

The memory of processing circuitry <NUM> may comprise one or more of, for example, Random Access Memory (RAM), Read Only Memory (ROM), EEPROM, ASIC, optical storage, magnetic storage, flash memory, solid state memory, or any combination thereof, or any other suitable medium used to store data. The memory may be configured to store one or more instructions (e.g., in the form of an application) executable by processing circuitry <NUM> to, for example, manage the locations of objects in the warehouse and to request inventory validation tasks. Any suitable programming languages may be employed to implement such instructions and applications, e.g., Java, C, Python, Go, JavaScript (e.g., React library, Node. js), Typescript, Handlebar, React, etc..

Drone management system <NUM> controls drones 140A, 140B,. , and 140N (collectively referred to as drones <NUM>) within the warehouse. As shown, drone management system <NUM> is communicatively coupled to drones <NUM>, and warehouse management system <NUM>. As shown, drone management system <NUM> may comprise a plurality of modules (e.g., drone manager <NUM>, facility map <NUM>, obstacle manager <NUM>, drone coordinator <NUM>, path planner <NUM>, task planner <NUM>, and warehouse object path estimator <NUM>) and processing circuitry <NUM> which may comprise hardware, software or any combination thereof, such as, for example, one or more central processing units (CPUs) configured to execute instructions stored in computer-readable media (e.g., memory) to implement operating system(s) and applications of drone management system <NUM> and manage task for drones <NUM>. In some embodiments, processing circuity <NUM> implements one or more of the plurality of modules (e.g., <NUM>-<NUM>). Drone management system <NUM> may further comprise communication circuitry <NUM> configured to transmit and receive communications from/to drones <NUM> and warehouse management system <NUM>. Communication circuitry <NUM> may also be configured to transmit and receive communications between components within drone management system <NUM>. In some implementation, drone management system <NUM> may retrieve information from warehouse management system <NUM> using an API.

The memory of processing circuitry <NUM> may comprise one or more of, for example, Random Access Memory (RAM), Read Only Memory (ROM), EEPROM, ASIC, optical storage, magnetic storage, flash memory, solid state memory, or any combination thereof, or any other suitable medium used to store data. The memory may be configured to store one or more instructions (e.g., in the form of an application) executable by processing circuitry <NUM> and/or the plurality of modules (e.g., <NUM>-<NUM>) to, for example, manage tasks such as inventory validation tasks. Any suitable programming languages may be employed to implement such instructions and applications, e.g., Java, C, Python, Go, JavaScript (e.g., React library, Node. js), Typescript, Handlebar, React, etc..

Drone management system <NUM> controls drones <NUM> to perform tasks, such as the inventory validation tasks received from warehouse management system <NUM>. For example, drone management system <NUM> may receive inventory validation tasks from warehouse management system <NUM> and store the tasks in a tasks database (e.g., implemented by task planner <NUM>). Drone management system <NUM> may then assign the inventory validation tasks to specific ones of drones <NUM> to perform. When assigning inventory validation tasks, drone management system <NUM> may determine obstacle-free paths to perform the inventory validation tasks, as discussed in further detail below. In some embodiments, drones <NUM> are autonomous aerial vehicles that are capable of navigating through the warehouse to specific locations (e.g., aerial robots). Drones <NUM> may include one or more sensors such as a camera that are used to capture images of locations in the warehouse and identifiers of items in the warehouse. Captured images and/or data, can be used to validate the location information managed by warehouse management system <NUM>.

Drone manager <NUM> may maintain a database of information of drones <NUM>. The information may include properties and current status information of each drone <NUM> (e.g., static and dynamic information). For example, for each drone <NUM>, drone manager <NUM> may store drone properties such as size, maximum velocity and acceleration, communication information, etc. (e.g., static information), as well as current status such as current location (e.g., within the warehouse), current charge level, current available flight time, etc. (e.g., dynamic information). Drone manager <NUM> may periodically (or in real-time) update the current status of each drone <NUM> based on information received from drone coordinator <NUM>.

Drone coordinator <NUM> may coordinate operations of drones <NUM> (e.g., instructing drones <NUM> to fly along obstacle-free paths to desired locations within the warehouse to perform specified operations such as inventory validation tasks). Drone coordinator <NUM> may further receive telemetry about the status of each drone <NUM> (e.g., through communication circuitry <NUM>). Facility map <NUM> may maintain a map of the warehouse environment including information for all static objects present in the warehouse (e.g., the location, size, name, etc. of the objects) and the fixed paths for navigating between the static objects (e.g., aisles and thruways). In one embodiment, facility map <NUM> maintains status information of each storage location in the warehouse (e.g., whether each storage location is empty or is currently storing an item). For example, in a warehouse having a plurality of storage racks each having a plurality of storage locations (e.g., on each of a plurality of shelves), facility map <NUM> may maintain status information for each storage location of each storage rack in order to identify storage locations that are empty that drones <NUM> are able to fly through (e.g., temporary paths). In some embodiments, facility map <NUM> may be populated with information received from warehouse management system <NUM>. In some embodiments, this information may be periodically verified based on images captured by one or more drones <NUM>.

Obstacle manager <NUM> may identify and track dynamic obstacles in the warehouse (e.g., that are not represented by facility map <NUM>). In some embodiments, dynamic obstacles (e.g., an inventory item in an aisle of the warehouse, movable storage racks, etc.) may be detected by one or more drone <NUM>. For example, drones <NUM> may be instructed to capture images of the warehouse when performing inventory validation tasks. In some embodiments, in response to detecting an obstacle, drone <NUM> may communicate information about the obstacle (e.g., an image and location) to obstacle manager <NUM> (e.g., through drone coordinator <NUM>).

Path planner <NUM> may determine a best path (e.g., an obstacle-free path) for drone <NUM> to a desired location in the warehouse (e.g., associated with an inventory verification task specified by warehouse management system <NUM>) based on, e.g., information provided by drone manager <NUM>, facility map <NUM>, obstacles manager <NUM>. In some embodiments, the desired location includes a plurality of locations specified by the inventory verification task (e.g., a plurality of locations in an aisle). In some embodiments, the determined best path (e.g., from among a plurality of possible paths) is associated with the type of tasks. For example, for certain tasks, path planner <NUM> considers all possible constraints (e.g., including obstacles, maximum drone velocity, drone charge level, etc.) that allows drone <NUM> to perform an inventory validation task in the shortest time. For other tasks, path planner <NUM> may minimize energy usage of drone <NUM>. Path planner <NUM> may utilize different algorithms to optimize different variables for different tasks.

Warehouse object path estimator <NUM> may predict paths of inventory moving devices <NUM> using information retrieved from warehouse management system <NUM>. For example, warehouse object path estimator <NUM> may retrieve information regarding inventory moving tasks generated for inventory moving devices <NUM>. Based on this retrieved information, warehouse object path estimator <NUM> may estimate paths that inventory moving devices <NUM> will take based on, e.g., current locations of inventory moving devices <NUM>, one or more locations associated with inventory moving tasks (e.g., pickup and drop-off locations), the types of inventory moving devices <NUM> (e.g., operating heights). In some implementations, inventory moving devices <NUM> may include localization sensors to determine their current location and position. Inventory moving devices <NUM> may communicate this information to warehouse management system <NUM> periodically or in real time. In some implementations, warehouse management system <NUM> may utilize sensors in the warehouse (e.g., cameras) to monitor locations of inventory moving devices <NUM>.

Drone management system <NUM> may be communicatively connected to warehouse management system <NUM> by an integration layer that connects application programming interfaces (APIs) of the two systems. In some embodiments, warehouse management system <NUM> and drone management system <NUM> may be remote systems that communicate with each other over the Internet or other suitable communication interfaces. It will be understood that while warehouse management system <NUM> and drone management system <NUM> are depicted as separate systems, in some embodiments, the functionality can be included in a single system. For example, the functionality performed by drone management system <NUM> may be included in warehouse management system <NUM>. Operation of warehouse system <NUM> is described in greater detail below with reference to <FIG>.

<FIG> shows an illustrative plan view of a warehouse <NUM> and the determination of an obstacle-free path of drone 140A to a desired location <NUM> within warehouse <NUM>, in accordance with some embodiments of this disclosure. Operation of warehouse <NUM> and determination of obstacle-free path <NUM> may be performed by warehouse system <NUM> of <FIG>. For example, as described above, warehouse management system <NUM> may instruct inventory moving devices 116A-116D to perform inventory moving tasks for warehouse <NUM> and drone management system <NUM> may instruct drones 140A and 140B to perform inventory validation tasks for warehouse <NUM>. As shown, drones 140A and 140B may automatically recharge by docking on charging stations 212A and 202B located in warehouse <NUM>.

As shown, warehouse <NUM> includes a plurality of storage racks 202A-202E (collectively referred to as storage racks <NUM>) arranged in a plurality of rows in a storage area of warehouse <NUM>. Ground space around the plurality of storage racks (e.g., navigable by inventory moving devices <NUM>) may include a plurality of aisles 204A-204F and one or more thruways 206A and 206B (e.g., fixed paths). However, it should be understood that <FIG> shows a simplified view of a warehouse and that storage racks <NUM> may be arranged in any suitable manner within warehouse <NUM>. As shown, each storage rack <NUM> includes a plurality of storage locations for each shelf of each storage rack <NUM>. As described above, drone management system <NUM> tracks a current storage status (e.g., empty or occupied) of each storage location in each storage rack <NUM> (e.g., based on information from warehouse management system <NUM>). For example, as shown, drone management system <NUM> may indicate storage location 208A in storage rack 202A, storage locations 208E and 208F in storage rack 202B, storage locations 208B and 208C in storage rack 202C, and storage location 208D in storage rack 202E as storage locations that are not currently occupied by an item. Based on the empty storage locations, drone management system <NUM> may identify shortcuts through storage racks that drones <NUM> are able to pass through (e.g., temporary paths). For example, as shown, drone management system <NUM> may identify a first current shortcut through storage rack 202C (at empty storage locations 208B and 208C) that drones <NUM> may use to travel between aisles 204C and 204D, and a second current shortcut through storage rack 202B (at empty storage locations 208E and 208F) that drones <NUM> may use to travel between aisles 204B and 204C.

Based on an inventory validation task to be executed by drone 140A , warehouse system <NUM> (e.g., drone management system <NUM>) may predict paths of each inventory moving device 116A-116D, based on the status of inventory moving tasks of warehouse management system <NUM> (e.g., based on current locations of each inventory moving device 116A-116D) and the time when the inventory validation task is to be executed (e.g., a current time). For example, as shown, inventory moving device 116A is projected to remain in place, inventory moving device 116B is projected to travel along path 216B to location 217B, inventory moving device 116C is projected to travel along path 216C to location 217C, and inventory moving device 116D is projected to travel along path 216D to location 217D. A traveling speed of each inventory moving device <NUM> may be projected based on the inventory moving tasks and information about each inventory moving device <NUM> (e.g., the type of inventory moving device). In some implementations, travel paths are determined by analyzing past routes taken by inventory moving devices in warehouse <NUM>. In some implementations, warehouse <NUM> may include one or more sensors (e.g., camera <NUM>) that provide information to warehouse system <NUM>. For example, camera <NUM> may identify an obstacle (e.g., obstacle <NUM>) in aisle 204E that is not tracked by warehouse management system <NUM>. In some implementations, warehouse management system <NUM> may monitor locations of inventory moving devices <NUM>.

Drone management system <NUM> may identify a desired location (e.g., desired location <NUM>) associated with an inventory validation task generated by warehouse management system <NUM>. Based on desired location <NUM> and the current status of drones 140A and 140B (e.g., current location, charge level, availability, type, etc.), drone management system <NUM> may assign the inventory validation task to drone 140A. In some implementations, inventory validation tasks may be assigned to drones <NUM> in a predetermined order.

Drone management system <NUM> may identify obstacle-free path segments (e.g., along both fixed paths and temporary paths), based on the current location of drone 140A, desired location <NUM>, and projected paths of inventory moving devices <NUM>. In some instances, by considering both temporary paths (e.g., the first and second shortcuts) as well as the fixed paths (e.g., aisles <NUM> and thruways <NUM>), drone management system <NUM> is able to increase the number of available obstacle-free paths to a desired location. For example, as shown, based on the identified obstacle-free path segments and the first and second shortcuts, drone management system <NUM> may identify a plurality of possible obstacle-free paths 218A and 218B from a current location of drone 140A to desired location <NUM>. For example, drone management system <NUM> may determine that aisle 204C is blocked by inventory moving devices 116B and 116C, but identify obstacle-free path 218A along thruway 206A, down aisle 204A, across thruway 206B, and up aisle 204B. More specifically, drone management system <NUM> may determine that one end of aisle 204B is blocked by inventory moving device 116A, but the opposite end of aisle 204B is free. For example, as shown, although inventory moving device 116C is predicted to travel along path 216C to desired location 217C, drone management system <NUM> may determine that drone 140A will be able to reach the end of aisle 204B either before inventory moving device 116C or that drone 140A will be able to travel above inventory moving device 116C in aisle 204B, based on an operating height of inventory moving device 116C. For example, drone management system <NUM> may retrieve a maximum traveling height (e.g., the maximum height of inventory moving device 116C while inventory moving device 116C is moving) and a maximum operating height (e.g., the maximum height of inventory moving device 116C while inventory moving device 116C is stationary), based on, e.g., the type of inventory moving device 116C In response to determining that drone 140A is able to travel over inventory moving device 116C, drone management system <NUM> may determine a three-dimensional, obstacle-free path of drone 140A to reach desired location <NUM>. For example, available heights along a path may be divided into n number of different possible path heights (e.g., each corresponding to one meter of height). Ceiling obstructions (e.g., beams, lights, etc.) may reduce available heights in certain areas, while inventory moving devices <NUM>, depending on their operating height or height of cargo (e.g., inventory item), may obstruct the lower several path heights. Thus, three-dimensional, obstacle-free paths may be generated in available path heights (e.g., not obstructed by warehouse <NUM> or inventory moving devices <NUM>).

In some implementation, drone management system <NUM> uses an algorithm (e.g., Dijkstra's Algorithm) to find the shortest path about the plurality of possible-obstacle-free paths if multiple obstacle-free paths are identified. For example, drone management system <NUM> may identify path 218B as the best obstacle-free path for drone 140A to travel to desired location <NUM>. Drone management system <NUM> may provide identified path 218B to drone 140A along with instructions to perform the inventory validation task to be executed.

In some implementations, only a single obstacle-free path to a desired location may be identified. In some implementations, drone management system <NUM> may identify potential locations to generate shortcuts in one or more storage racks <NUM>. For example, as shown, drone management system <NUM> may identify potential shortcut <NUM> as a shortcut to be generated, as only a single storage location (storage location <NUM>) needs to be emptied (e.g., thereby creating path <NUM> through empty storage locations 208A and <NUM>). However, this is only one example, and it should be understood that certain storage racks may only include a single row of storage locations (e.g., accessible from either side of the storage rack). Based on the identified potential shortcut <NUM>, drone management system <NUM> may request warehouse management system <NUM> to generate an inventory moving task for inventory moving device <NUM> to remove the item currently stored in the identified potential shortcut (e.g., at <NUM>), if, e.g., generating shortcut <NUM> will save more than a predetermined amount of travel time to desired location <NUM>. Generating shortcuts between storage racks <NUM> is explained in greater detail below with reference to <FIG>.

In some implementations, if a suitable path to a desired location is not immediately identified (e.g., due to the projected paths of inventory moving devices <NUM>), drone management system <NUM> and warehouse management system <NUM> may coordinate the overlapping inventory validation task and inventory moving tasks to a generate an obstacle-free path. For example, if the inventory validation task specified a desired location in aisle 204C, which is currently blocked by inventory moving devices 116B and C, warehouse management system <NUM> and drone management system <NUM> may reschedule at least one of the inventory moving tasks and the inventory validation tasks.

<FIG> shows an illustrative plan view of warehouse <NUM> of <FIG> and the determination of a shortcut to be generated in a storage rack within warehouse <NUM>, in accordance with some embodiments of this disclosure. As shown, drone management system <NUM> may identify a region <NUM> where there is difficulty in performing one or more inventory verification tasks. For example, drone management system <NUM> may identify region <NUM> by determining that inventory validation tasks associated with region <NUM> are not being completed within a predetermined amount of time, that more than a predetermined number of inventory validation tasks for region <NUM> are outstanding, or that more than a predetermined number of inventory validation tasks for the region have been pending for more than a predetermined amount of time, etc. In this case, drone management system <NUM> may further determine whether region <NUM> has limited access paths that make it difficult to complete inventory validation tasks. For example, as shown, drone management system <NUM> may determine that region <NUM> has limited access paths as drone 140B would have to travel down aisle 204D before traveling back up adjacent aisle 204E along determined obstacle-free path <NUM> due to obstacle <NUM> blocking one end of aisle 204E.

Based on identifying region <NUM> where there is difficulty in performing one or more inventory verification tasks and that access to region <NUM> is limited, drone management system <NUM> may identify possible storage locations in storage racks <NUM> for generating a shortcut for drone 140B to access region <NUM>. For example, as shown, drone management system <NUM> may identify storage locations 309A and 309B to be emptied (e.g., to thereby shortcut <NUM> through empty storage locations 309A and 309B, which drone 140B may travel through on path <NUM>). Because storage racks <NUM> require adjacent storage locations from opposite sides of the storage rack to be empty to form a path though the storage rack (e.g., 309A and 309B), drone management system <NUM> may also identify possible shortcuts that are able to be generated by emptying only one storage location. That is, drone management system <NUM> may identify storage locations that are already empty (e.g., 208D) to reduce the amount of work required to generate a shortcut. For example, drone management system <NUM> may identify storage location 309C to be emptied (e.g., to thereby create a path through empty storage locations 309C and 208D). Although a path through the possible shortcut through storage rack 202E may be longer than the possible shortcut through storage rack 202D, drone management system <NUM> may nonetheless determine to generate the possible shortcut through storage rack 202E in order to save time in generating the shortcut (e.g., by only requiring one storage location to be emptied instead of two). However, this is only one example, and drone management system <NUM> may identify one or more possible shortcuts to be generated based on any suitable factors (e.g., drone travel times along different shortcuts, current location and availability of inventory moving devices <NUM>, obstacle free paths to the targeted storage locations to be emptied, etc. ).

In some implementations, if drone management system <NUM> determines that an obstacle blocking one or more of drones 140A and 140B from traveling to/from charging stations 212A or 212B, drone management system <NUM> may determine that the obstacle should be moved to allow the one or more drones 140A and 140B to recharge and or leave the charger to perform one or more inventory verification tasks.

<FIG> is a flowchart of an illustrative process <NUM> for determining an obstacle-free path of a drone to a desired location in a warehouse, in accordance with some embodiments of this disclosure. In various embodiments, the individual steps of process <NUM> may be implemented by one or more components of the devices and systems of <FIG>. Although the present disclosure may describe certain steps of process <NUM> (and of other processes described herein) as being implemented by certain components of the devices and systems of <FIG>, this is for purposes of illustration only, and it should be understood that other components of the devices and systems of <FIG> may implement those steps instead.

At <NUM>, processing circuity (e.g., <NUM> and/or task planner <NUM>) may receive an inventory validation task for a warehouse. In some embodiments, the inventory validation task may be generated by processing circuitry <NUM> of warehouse management system <NUM>. In some embodiments, the receiving is performed by communication circuitry <NUM>. In some embodiments, warehouse management system <NUM> may prioritize certain inventory validation tasks over inventory moving tasks. For example, if the estimated time to complete an inventory validation task may be reduced by more than a predetermined amount (e.g., half) if a currently scheduled inventory moving task is delayed, warehouse management system <NUM> may reschedule the inventory moving task. For example, drone management system <NUM> may provide a message to warehouse management system <NUM> indicating, e.g., that if a certain path or aisle is not occupied by an inventory moving device <NUM> for the next fifteen minutes, the entire area will be able to be scanned immediately. Based on this message, drone management system <NUM> may determine whether scanning the entire area (e.g., performing a scheduled inventory validation task) is more important than retrieving or deposing an item in the same area (e.g., performing a scheduled inventory moving task) and prioritize one of the tasks based on the determination.

At <NUM>, processing circuity (e.g., <NUM> and/or warehouse object path estimator <NUM>) may receive the status of inventory moving tasks for the warehouse. In some embodiments, the received status may include current location information of one or more inventory moving devices <NUM> performing or scheduled to perform one or more of the inventory moving tasks and a current status (e.g., current completion percentage) the one or more inventory moving tasks.

At <NUM>, processing circuity (e.g., <NUM> and/or warehouse object path estimator <NUM>) may predict at least one location of at least one inventory moving device (e.g., inventory moving device <NUM>) in the warehouse based on the status of the inventory moving tasks. For example, warehouse object path estimator <NUM> may predict paths of inventory moving devices <NUM> using information retrieved from warehouse management system <NUM>. For example, warehouse object path estimator <NUM> may retrieve information regarding inventory moving tasks generated for inventory moving devices <NUM>. Based on this retrieved information, warehouse object path estimator <NUM> may estimate paths that inventory moving devices <NUM> will take based on, e.g., current locations of inventory moving devices <NUM>, one or more locations associated with inventory moving tasks (e.g., pickup and drop-off locations), the types of inventory moving devices <NUM> (e.g., operating heights). In some implementations, inventory moving devices <NUM> may include localization sensors to determine their current location and position. Inventory moving devices <NUM> may communicate this information to warehouse management system <NUM> periodically or in real time. In some implementations, warehouse management system <NUM> may utilize sensors in the warehouse (e.g., cameras) to monitor locations of inventory moving devices <NUM>.

At <NUM>, processing circuity (e.g., <NUM> and/or path planner <NUM>) may determine an obstacle-free path of an aerial vehicle (e.g., drone <NUM>) to a desired location in the warehouse based on the predicted at least one location of inventory moving devices <NUM>. For example, processing circuity (e.g., <NUM> and/or path planner <NUM>) may determine if a segment will be free when drone <NUM> reaches a segment by predicting at least one location of inventory moving devices <NUM> when drone <NUM> reaches the segment (e.g., based on the speed of inventory moving devices <NUM> and the speed of drone <NUM>). In some implementations, it may be advantageous to add a buffer to account for slower/faster traveling of drone <NUM> and inventory moving devices <NUM>. For example, as described above with reference to <FIG>, processing circuity (e.g., <NUM> and/or path planner <NUM>) may determine that drone 140A will reach the end of aisle 204B before inventory moving device 116C. In this case, although the predicted paths of drone 140A and inventory moving device 116C appear to overlap, the predicted path of drone 140A will be obstacle free when drone 140A reaches the aisle 204B along path 218A. In some implementations, if multiple paths are identified (e.g., 218A and 218B), processing circuitry <NUM> or path planner <NUM> may select one of the multiple paths 218A and <NUM> by optimizing certain variables (e.g., shortest path, shortest travel time, etc.).

<FIG> is a flowchart of an illustrative process <NUM> for determining a shortcut to be generated in a storage rack in a warehouse, in accordance with some embodiments of this disclosure. In various embodiments, the individual steps of process <NUM> may be implemented by one or more components of the devices and systems of <FIG>. Although the present disclosure may describe certain steps of process <NUM> (and of other processes described herein) as being implemented by certain components of the devices and systems of <FIG>, this is for purposes of illustration only, and it should be understood that other components of the devices and systems of <FIG> may implement those steps instead.

At <NUM>, processing circuity (e.g., <NUM> and/or task planner <NUM>) may receive inventory validation tasks for a warehouse. In some embodiments, the inventory validation tasks may be generated by processing circuitry <NUM> of warehouse management system <NUM>. In some embodiments, the receiving is performed by communication circuitry <NUM>.

At <NUM>, processing circuity (e.g., <NUM> and/or task planner <NUM>) may determine a region of the warehouse (e.g., <NUM>) where there is difficulty in performing one or more inventory validation tasks, based on the received inventory validation tasks. For example, processing circuity <NUM> or task planner <NUM> may determine that there is difficulty in performing one or more validation tasks when one or more inventory validation tasks for the region were not completed within a predetermined amount of time, more than a predetermined number of inventory validation tasks for the region are outstanding, or more than a predetermined number of inventory validation tasks for the region have been pending for more than a predetermined amount of time. In some implementations, processing circuity <NUM> or task planner <NUM> may predict that there will be difficulty in performing one or more inventory validation tasks when a large number of tasks are requested in a short period of time for a region with limited access in order to avoid a situation in which inventory validation tasks are not able to be performed within a desired time.

At <NUM>, processing circuity (e.g., <NUM> and/or task planner <NUM>) may request a shortcut to be generated in a storage rack to provide a path segment that drone <NUM> is able to reach region <NUM> and perform the inventory validation task in the determined region. In some implementations, if multiple possible path segments are identified, processing circuitry <NUM> and/or task planner <NUM> may select one of the path possible path segments to generate the shortcut. In some implementations, processing circuity (e.g., <NUM> and/or task planner <NUM>) may transmit the request to warehouse management system <NUM> to instruct one of inventory moving devices <NUM> to remove items stored that the identified possible path segment.

Claim 1:
A warehouse method, comprising:
receiving status of inventory moving tasks for a warehouse;
predicting at least one location of an inventory moving device (116A-116D) in the warehouse (<NUM>) by:
identifying a task, among the inventory moving tasks, associated with moving an inventory item from a first location (217A-217D) to a second location (217A-217D);
determining a predicted route from the first location (217A-217D) to the second location (217A-217D) for the identified task; and
predicting the at least one location of the inventory moving device along the predicted route based on the status of the identified task; and
determining an obstacle-free path (218A, 218B) of an aerial vehicle (<NUM>) to a desired location (<NUM>) in the warehouse (<NUM>) based on the predicted at least one location of the inventory moving device (116A-116D).