HK1232970B - Methods, systems and apparatus for controlling movement of transporting devices - Google Patents

Description

Method, system and device for controlling movement of transportation equipment

The present invention relates to methods, systems and apparatus for controlling the movement of transport equipment, and more particularly, but not exclusively, to systems and methods for retrieving units from a storage system. The present invention also relates particularly, but not exclusively, to systems and methods for coordinating and controlling the movement of products.

Some commercial and industrial activities require systems that can store and retrieve large quantities of different products.

One known system for storing and retrieving goods from multiple product lines involves placing storage boxes or containers on shelves arranged in rows within aisles. Each box or container contains one or more products of one or more product types. The aisles provide access between the rows of shelves so that the desired products can be retrieved by operators or robots that circulate through the aisles.

However, it should be noted that the need to provide aisle spacing for accessing products means that the storage density of such systems is relatively low. In other words, the amount of space actually used to store products is relatively small compared to the space required for the entire storage system.

For example, online retailers and supermarkets that sell multiple product lines need systems that can store tens or even hundreds of thousands of different product lines. The supply chain and warehouse operations of these companies are highly dependent on their ability to organize, retrieve, and return goods to containers.

In certain embodiments of various warehouse and storage equipment designs, containers can be stacked one on top of the other, and stacks can be placed in rows, with the containers then accessible from above, eliminating the need for aisles between rows of containers and enabling more containers to be stored in a given space or area.

In some of these embodiments, the containers may be accessed by one or more robots or automated tools that navigate through a grid of pathways to access the containers and perform various operations, such as moving the containers from one location to another for processing, performing operations on the containers, returning the containers to a location within a warehouse, and the like.

Coordinating the movement of one or more robots or other automated tools is a key consideration in determining the overall efficiency and scalability of a system for storing and retrieving large numbers of different products.

US6654662 and EP1037828 describe a storage and retrieval system in which "parallelepipedic" containers are stacked and connected vertically in a vertical frame to form several horizontal layers of containers, with the positions of these containers being random at any given time. A computer system continuously monitors and records the positions of the containers, removing the required containers from the top of the frame and moving the unrequired containers one at a time to temporary locations until the required container is retrieved. At this point, the temporarily relocated containers are returned to the original stack in their original relative order, thus (eventually) returning the required container to the top of the original stack.

The systems described in US6654662 and EP1037828 have several horizontally co-ordinated container layers, where the positions of the containers are random at any given time. Furthermore, temporarily relocated containers are returned to the original stack so that their relative order remains unchanged and the required containers are returned to the top of the stack.

Compared to existing systems, it is a great advantage to provide a considered container placement that can be optimized in both horizontal and vertical domains based on different criteria such as traffic flow, access frequency (historical, current and predicted), specific container groupings, access time, fire resistance and/or other environmental zoning.

Therefore, systems and processes to coordinate and control product movement are necessary.

According to some embodiments of the present invention, there is provided a system for controlling the movement of one or more transport devices transporting a plurality of items and operating in a facility having a plurality of lanes, the system comprising:

One or more computers configured to execute computer instructions that, when executed, provide:

One or more utilities that determine and reserve routes for moving the one or more transport devices through the plurality of pathways; and

One or more utilities provide a clearance system for allowing or stopping movement of the one or more transport devices to avoid collision.

In some embodiments, the system further comprises one or more utilities configured to optimize the movement and actions of the one or more transport devices through the plurality of pathways.

In some embodiments, the system further comprises one or more utilities configured to optimize placement of the plurality of items by the one or more transport devices in the facility.

In some embodiments, the system further comprises one or more utilities that control movement or operations performed at one or more workstations.

In some embodiments, the one or more utilities that optimize the movements and actions utilize a routing algorithm.

In some embodiments, the one or more utilities utilize congestion mitigation techniques to optimize the movement and actions.

In some embodiments, the one or more utilities utilize machine learning techniques to optimize the movements and actions.

In some embodiments, the one or more utilities optimize placement of the number of items in the facility and update inventory levels of the facility based on the placement of one or more of the number of items in the facility.

In some embodiments, the one or more utilities control movement of the one or more transporters based at least on a workload of the one or more workstations.

In some embodiments, the one or more utilities provide a gap system configured to tolerate interruptions in communication with at least one of the one or more transport devices.

In some embodiments, the one or more utilities determine and reserve a route and instruct a plurality of transporters to cooperate in transporting one or more of the plurality of items.

In some embodiments, the one or more utilities determine and reserve routes to move idle transport equipment away from optimal routes for use by other transport equipment.

In some embodiments, one or more of the plurality of items are stored in a plurality of containers.

In some embodiments, the facility stores the plurality of containers in stacks.

In some embodiments, the one or more utilities determine and reserve a route to transport one or more of the number of containers.

In some embodiments, the one or more utilities determine and reserve routes to control one or more of the number of transporters to retrieve one or more of the number of containers from one or more of the number of stacks.

In some embodiments, removing the one or more containers from the one or more stacks also requires moving one or more other containers in the stacks prior to removing the one or more containers.

In some embodiments, moving the one or more other containers includes placing each of the one or more other containers in an optimal location in the facility.

In some embodiments, the facility is divided into sub-grids to reduce processing complexity.

In some embodiments, one or more control commands for controlling the movement of the plurality of transporting devices are provided to the plurality of transporting devices before the plurality of transporting devices move.

In various aspects, the present invention provides methods, systems, and corresponding sets of machine-executable coded instructions for coordinating and controlling product movement in at least one semi-automated order fulfillment system including a storage device. In various aspects, the present invention provides improvements in coordinating and controlling the movement of robots that handle various items to fulfill an order, which, in some examples, may include various items of varying size, weight, fragility, and other characteristics.

In various embodiments of the above and other aspects, the storage device may include one or more storage devices. In the same or other embodiments, at least a portion of the storage device may be configured to be dynamically movable.

In the same or other embodiments, the storage device can be shared by two or more workstations.

The present invention will be described below with reference to the accompanying schematic drawings, which are intended to illustrate rather than limit the present invention in any way, wherein the same reference numerals are intended to indicate the same or corresponding parts.

FIG1 is an illustrative diagram of some aspects of a general computer hardware and software embodiment, see the specification for details.

FIG2 is an exemplary block diagram of the system according to some embodiments of the present invention.

FIG3 is a more detailed example block diagram of the robot control system according to some embodiments of the present invention.

FIG4 is a flowchart illustrating an example workflow of an example recursive path-finding algorithm according to some embodiments of the present invention.

Figure 5 is an example heat map according to some embodiments of the present invention.

FIG6a is a table showing how the estimated cost of a search branch changes when different coefficients are used in the path search algorithm. These coefficients can be extracted using machine learning techniques according to some embodiments of the present invention.

FIG. 6b illustrates how the use of different cost coefficients as shown in FIG. 6a changes the branch that will be selected on the next iteration of the search algorithm.

7 is an exemplary perspective view of a warehouse according to some embodiments of the present invention.

FIG. 8 is an exemplary diagram of a robot with a hoist and a container according to some embodiments of the present invention.

Preferred embodiments of methods, systems, and apparatus suitable for implementing the present invention will be described with reference to the accompanying drawings.

Fully automated and semi-automated product storage and retrieval systems may be implemented in various types and forms, and aspects thereof may sometimes be referred to as "order fulfillment" systems, "storage and retrieval" systems, and/or "order picking" systems. A method of providing access to stored products for fully automated and/or semi-automated retrieval may include, for example, placing products of any desired type in boxes or other containers (hereinafter collectively referred to as "containers") and stacking and/or otherwise vertically stratifying the containers in racks to enable fully automated or semi-automated container retrieval systems to access the individual containers.

In some embodiments, the system may include systems other than merchandise storage and retrieval systems, such as systems for processing, repairing, manipulating, assembling, sorting merchandise, etc., which require moving merchandise, products, parts, components, subcomponents within a facility and/or to other facilities, or for shipping.

For the purposes of this specification, a storage facility that stores, retrieves, processes, and/or fulfills orders is referred to as a "hive," wherein fully automated or semi-automated storage and retrieval systems provide access to such items. The "hive" may comprise a grid-like layout of potential pathways for robotic elements or devices ("robots") to move through and perform operations at various locations within the "hive" (referred to as a "grid").

The present description is not limited to systems having "hives," "grids," and/or "robots," but rather contemplates systems that broadly control and/or coordinate the movement and/or actions of a plurality of devices. These devices may be configured to transport various items, such as goods and/or products, and/or containers that may be empty and/or contain such goods and/or products. These devices may also be used to fulfill orders, but may also be used for any other type of action, such as transporting containers to and from workstations, moving items from a home location to a destination, and the like.

As described above, the devices may be robots, and the devices may be configured to move along the hive and/or communicate with a control system to coordinate and receive movement instructions. In some embodiments, the devices may be configured to communicate among themselves and/or coordinate movement among themselves. Thus, the devices may have various transport means, communication means, power means, handling means, processor means, sensor means, monitoring means, onboard workstations, electronic/physical storage means, and/or lifting/transport means (e.g., winches, arms, etc.).

Although the device may be configured to receive instructions from the system, circumstances may arise where the device loses communication with the system, the device's communication path ages, and/or is unable to receive communications from the system within a particular time frame.

In some embodiments, the devices may also be configured to communicate with each other and/or sense each other's presence. These communications and/or sensory inputs may be used, for example, to crowdsource environmental information, provide redundant communication channels, verify instructions, and the like.

Order fulfillment can include various operations, including but not limited to: assembling orders when purchasing and mixing various products for delivery to customers, such as used in chain grocery stores; assembling products that have various sub-components; performing various operations on products (such as welding components together); sorting products, etc.

Orders can also be returned, for example, if they are canceled, if delivery fails, etc. In some cases, even if an order is being fulfilled in the Hive, it can be canceled and the goods may need to be returned. In some cases, the goods may need to be put back into the container, and the container may need to be moved to various locations. In some cases, when an order is returned or canceled, the workstation may need to perform tasks to reject/rework the product.

Furthermore, as described above, individual containers can be placed in vertical layers, and their positions within the "hive" can be plotted using three-dimensional coordinates to represent the robot or container's position and the container's depth (e.g., container (X, Y, Z), depth W). In some embodiments, positions within the "hive" can be plotted using two-dimensional coordinates to represent the robot or container's position and the container's depth (e.g., container (X, Y), depth Z).

The "hive" itself can be a "dynamic" environment, in the sense that robots and workstation locations may be associated with different parts of the hive to participate in activities. For example, a robot may need to access a specific container at a specific location within the hive dimensions (e.g., container (X, Y, Z), depth W) to fulfill a specific order or store products within the hive. This involves the robot moving along various possible paths, such as moving along the top of the grid and then accessing a specific container at a specific depth within the stack.

Accessing a particular container at a given depth in a stack may require moving processes that may hinder access to that particular container (e.g., when containers are stacked, many containers must first be moved before accessing a container that is not at the accessible end of the stack). In some embodiments, it may be advantageous to configure the system to provide an assessment and optimization of the new position for each container that must be moved to access the target container.

Containers that are moved off the stack do not need to be moved back to their original stack.

One potential advantage is the ability to adjust the distribution of containers so that they are placed in a more accessible or convenient location.

This can help maintain an optimal distribution of containers within the facility, for example, by favoring containers expected to have higher demand to be placed in more easily accessible locations, such as near or within a workstation to reduce transport distances.

7 is an exemplary perspective view of a warehouse according to some embodiments of the present invention.

The robots can have various shapes, sizes, and configurations and can be equipped with various communication tools, sensors, and tools. In some embodiments, each robot can communicate with the control system via a set of frequency channels established by a set of base stations and a base station controller. The robots can utilize various tools to move and retrieve containers from a stack, for example, using a winch to carry a container.

FIG. 8 is an exemplary diagram of a robot with a hoist and a container according to some embodiments of the present invention.

The grid is not limited to rectangular grid elements and can include curved tracks, up-down tracks, etc. The grid pathways can have intersections and can be used by more than one robot.

Each grid can be physically or logically divided into one or more subgrids.

The grid may include one or more workstations. A workstation may be manual, semi-automated, or fully automated, and may include locations and areas where operations are performed within the hive or with respect to the hive, containers, or products, such as moving products into or out of the hive, producing products, assembling products, processing products into their components, providing staging locations to support other steps or operations, etc.

Workstations may include, for example, locations where goods are moved from inbound transport vehicles, locations where various operations are performed on products (such as component assembly, painting, sorting, packaging, disassembly, reworking products, repairing packaging, returning products from canceled orders, rejecting returned products, and disposing of products), and locations where products are moved to outbound transport vehicles, locations with refrigeration capabilities, locations for assembling components or items, locations for temporary storage or pre-retrieval of products, locations for repairing and maintaining robots, locations for charging robots, locations where workers pick products to be placed in containers, locations where workers pick products to be taken out of containers to fulfill orders, locations where bags are placed in containers, etc.

If goods/products are returned to the hive, the system can support and/or control the process of retrieving the product, reworking the product, and/or disposing of the product if rejected. In some embodiments, the scenario can include processing the returned container (distribution tote or other item) at a workstation to determine whether it can be accepted back into the system, to determine whether it requires reworking/repackaging, and/or whether the product should be disposed of (e.g., if a perishable product has expired).

A workstation can have one or more workers or robots performing various tasks, such as picking items to fulfill orders.

In some embodiments, a workstation may also be a station having conveyor belts, freezers, various tooling techniques, and/or other techniques for operating, painting, fastening, repairing, freezing, heating, exposing to chemicals, freezing, filtering, assembling, disassembling, sorting, packaging, scanning, testing, transporting, storing, or handling goods and containers.

The workstation may have its own access pathways within the facility, share access pathways with the facility, etc. The workstation may also have various input and output pathways or other types of entry/exit points within the facility.

In some embodiments, the workstation communicates with one or more warehouse management systems to provide information and data related to the workstation, workflow, required containers, problems, and information and data related to the status of stored or operated products (such as subcomponents being assembled together), etc.

After receiving an order from a customer for multiple items in a storage and retrieval system, a fully automated or semi-automated container handling machine can retrieve storage containers containing the corresponding items from storage containers arranged in a grid, shelf or other orderly manner and deliver them to one or more workstations.

At the workstation, items are removed from storage containers and placed in intermediate storage before being picked into delivery containers.

As described herein, it may be advantageous to distribute the containers so that input containers for certain workstations may be placed adjacent to those workstations.

Picking items from containers can be done manually by human pickers, or performed semi-automatically or fully automatically with the assistance of various mechanical or robotic elements.

If individual containers are stacked vertically in layers, accessing a container not located on the top layer requires another set of operations to move containers stored above the desired container before accessing the desired container. For example, if the desired container is located one layer below the top layer, the top container may need to be moved to another location before accessing the desired container. As described herein, it may be advantageous to distribute the containers so that containers storing more in-demand items are more easily accessible. In some embodiments, an optimization module provides optimal locations for these containers to be placed.

In a typical merchandise picking operation adapted to handle a wide variety of items, such as a grocery order processing system, it is sometimes found that during the fulfillment of one or more orders, a variety of items having various sizes, shapes, weights, and other characteristics must be handled or otherwise positioned, and these items may need to be moved to various stations around the facility for various operations. Depending on the size, organization, and layout of the facility, the movement of these items can be advantageously optimized so that the items are moved efficiently, collisions are avoided, and dependencies (e.g., picking and unloading items in the proper sequence) are resolved.

The various actions involved in these workgroups, such as placing goods into different types of containers, storing containers in the hive, and the sorting/delivery described in this specification, may result in various movements of the containers, including placing containers at different locations within the hive. These actions may include hive inbound/outbound activities (such as moving goods into and out of storage), and may also include related sorting/delivery systems, such as managing the movement of products from vehicles for storage/delivery and the movement of products onto vehicles for order fulfillment.

In other embodiments of the present invention, the workstations can be used to provide other types of product or container handling, such as workstations that perform product processing (e.g., assembly, disassembly, modification, sorting, drying, freezing, testing, chemical exposure, physical manipulation, fastening, repair, printing, painting, cutting, packaging, storage, machining, welding, tempering, and reprocessing). These workstations can be manual, semi-automated, or automated and have various parameters associated with their operation or performance, such as workload, required input, required output, load balancing, and required delays (e.g., drying time).

The various movements of the robot, the placement of containers/items, and the control of when to remove products from the containers can be controlled and optimized by one or more control systems. This control includes implementing various strategies, including, for example:

Centrally manage one or more robots;

The management robot not only retrieves containers for processing, but also pre-takes containers to a more convenient location, such as a location adjacent to or within a workstation;

Optimizing paths by applying one or more path-finding algorithms (e.g., branch-and-bound);

Optimizing paths (e.g., estimated minimum cost) by applying one or more heuristic techniques to one or more routing algorithms. In one embodiment of the invention, the cost, when viewed as a whole, may be calculated as a function of the total time to the destination and the total cumulative heat generated to alleviate congestion on the grid.

Arrange/pre-process movement routes in advance;

Conduct simulations to determine optimal depth analysis for scheduling/pre-processing movement paths;

Applying machine learning techniques to optimize exponents and coefficients of cost functions applied to one or more algorithms. In some embodiments, this may include a routing algorithm, a container placement algorithm, and a workstation load balancing algorithm;

Instant robot path conflict resolution system;

Subdivide the robot population into separate control groups, each containing one or more robots;

Optimizing container locations through various tools, such as using a scoring selection algorithm that uses weighted cost coefficients;

Optimize workstation work distribution;

Preprocess tasks and actions to schedule further tasks and actions.

In an example environment where one or more robots are used for fully or semi-automated retrieval, storage, and movement of items, the warehouse may first have to decide how to distribute container loads among different robots or groups of robots.

For example, the distribution of tasks between groups of robots and picking stations can be optimized based on the specific layout of the warehouse, the placement of the goods, the specific characteristics of the goods (such as expiration or potential dangers), and workflow sequencing.

For example, it may be desirable to have a system that intelligently compares potential paths for a robot to its destination, taking into account, among other things, potential congestion along that path, the time required to complete the operation, the likelihood of a collision, the items in a particular robot's inventory, the predicted future operations, and characteristics of the particular robot (e.g., battery level, service issues).

It may further be desirable to have a system that can intelligently adapt to various conditions in the "hive," such as idle robots that may obstruct or block a robot's path, obstacles, or other robots' reserved paths that a particular robot is attempting to traverse.

It may be further desirable to have a system that intelligently places containers based on an algorithm that biases the system toward container allocation that facilitates efficient access to items (e.g., placing containers containing high-demand SKUs near the top floor and near their workstations for easy access).

These are non-limiting examples and any optimization method, arrangement, or consideration may be used.

FIG2 is a schematic diagram of an example system for fully automated and semi-automated storage and retrieval of goods according to some embodiments of the present invention. FIG2 is a high-level diagram illustrating an example embodiment. Various embodiments of system 200 may include more or fewer components, and FIG2 is merely an example.

The system 200 includes a robot control system 202, a maintenance/monitoring system 204, a base station controller 206, one or more base stations 208a and 208b, one or more robots 210a, 210b, and 210c, and one or more charging stations 230. Although only two base stations 208a and 208b and three robots 210a, 210b, and 210c are illustrated, it should be understood that there may be more or fewer robots and base stations in other embodiments of the system.

There may be one or more warehouse management systems (WMS) 232 , order management systems 234 , and one or more information management systems 236 .

The warehouse management system 232 may include information such as the items required for the order, the inventory unit number in the warehouse, expected/forecasted orders, items missing from the order, the expiration date of the items when the order is to be loaded onto the conveyor, the name of the items in each container, whether the items are fragile or bulky, etc.

In some embodiments, the warehouse management system 232 can communicate with the workstation and may also include information related to the workstation, such as the status of the workstation, the product name and/or container name that the workstation is required to receive at a specific time, the product name and/or container name that the workstation will be required to move to another location at a specific time, the expected operational workflow to be performed at the workstation, the number of robots currently waiting to place containers at the workstation, etc.

The robot control system 202 can be configured to control the navigation/routing of the robots, including, but not limited to, moving from one location to another, avoiding collisions, optimizing movement paths, controlling actions to be performed, and the like. The robot control system 202 can also be implemented using one or more servers, each server comprising one or more processors configured based on instructions stored on one or more non-transitory computer-readable storage media. The robot control system 202 can be configured to send control information to one or more robots, receive one or more updates from one or more robots, and communicate with one or more robots using real-time or near-real-time protocols. The robot control system 202 can receive information indicating the location and availability of robots from one or more base stations 208a and 208b. The robot control system 202 can be configured to record the number of available robots, the status of one or more robots, the location of one or more robots, and/or their current command settings. The robot control system 202 can also be configured to process and/or send control information to one or more robots to predict future movements, potentially reduce processor load, and proactively manage communication load on communication links. This embodiment can be advantageous given the complex algorithms used by the robot control system 202 to determine optimal pathways, calculate optimal container locations, and/or determine reservations and/or slots.

In some embodiments, the server may utilize a "cloud computer" type platform for distributed computing. Cloud-based implementations may provide one or more advantages, including: openness, flexibility, and scalability; centralized management; reliability; scalability; optimized use of computing resources; the ability to aggregate information from many users; and the ability to connect to many users and find matching subgroups of interest. While embodiments and implementations of the present invention may be discussed in the context of specific, non-limiting examples using the cloud to implement various aspects of the system platform, a local server, a single remote server, a software-as-a-service platform, or any other computing device may be used in place of the cloud.

In some embodiments, the mobility optimization module can use one or more control groups to divide the robots into one or more groups. Using control groups for large grids can provide certain advantages, such as the ability to maintain operation of a very large grid whenever real-time computation cannot keep up with replanning after a control anomaly, such as when (1) the wireless communication link drops more sequential packets than allowed in the plan; (2) one or more robots fail; or (3) one or more robots operate outside of a certain performance tolerance.

Control stop messages can be broadcast to robots in a specific "control group"; potential benefits of broadcasting messages, as opposed to sending individual messages, can include improved communication through the use of multiple transmission slots and potentially higher signal-to-noise ratios.

In some embodiments, the robot control system 202 may be configured to dynamically assign robots to different "control zones" as they traverse the grid.

The maintenance/monitoring system (MMS) 204 can be configured to provide monitoring functions, including receiving alerts from one or more robots or one or more base stations and establishing connections with querying robots. The MMS 204 can also provide an interface for configuring monitoring functions. The MMS 204 can interact with the robot control system 202 to indicate when certain robots should be recalled.

The base station controller 206 can store master routing information to determine the location of robots, base stations, and the grid. In some embodiments, there may be one base station controller 206 per warehouse, while in other embodiments of the present invention, there may be multiple base station controllers. The base station controller 206 can be designed to provide high availability. The base station controller can be configured to manage dynamic frequency selection and frequency allocation for the one or more base stations 208a and 208b.

The base stations 208a and 208b can be organized into a base station pool, which can then be configured in active mode, standby mode, or to monitor the system. Messages can be routed to and from the robot via various communication tools. The communication tool can be any communication tool, and in some embodiments, the communication tool can be a radio frequency link, such as those that meet the wireless standard 802.11. The base stations 208a and 208b can also include processing units 212a, 212b, digital signal processors 214a, 214b, and radio devices 216a, 216b.

The one or more robots 210a, 210b, and 210c can be configured to move around the grid and perform operations. Operations can include moving a container from one stack to another, charging at a charging station, etc. The one or more robots can be assigned to communicate with the one or more base stations 208a and 208b.

The one or more robots 210a, 210b, and 210c do not all need to be the same type of robot. There may be different robots with various shapes, designs, and uses. For example, there may be robots that occupy a single grid position, robots that hoist containers for internal loading, cantilever robots, bridging robots, and retrieval robots.

In some embodiments, the one or more robots 210a, 210b, and 210c have a winch that can be used to grip a container and move it from one location on the grid to another.

The robots 210a, 210b and 210c may respectively have radio devices 218a, 218b, 218c, digital signal processors 220a, 220b, 220c, processors 222a, 222b, 222c, real-time controllers 224a, 224b, 224c, batteries 226a, 226b, 226c, and motors, sensors, connectors, etc. 228a, 22bb, 228c.

The one or more charging stations 230 can be configured to provide power to charge batteries on the one or more robots 210a, 210b, and 210c. The one or more charging stations 230 can also be configured to provide high-speed, wired data access to the one or more robots, and several charging stations can be placed around the grid for use by the one or more robots 210a, 210b, and 210c.

3 is a block diagram of the control system 202 according to some embodiments of the present invention. This block diagram is used to identify some components of the control system 202 in more detail, but not every identified module or interface may be required. In various embodiments, more or fewer modules may be included.

The control system 202 can be configured to evaluate how to improve work allocation, product movement, and product placement. According to various embodiments of the invention, optimizations can be run in real time, while others are run periodically, for example, during downtime or low activity times.

The control system 202 can be configured to schedule when specific types of movements occur and in what order, based on various business rules, applications that indicate priorities, and the like. The control system 202 can be configured to factor in inbound and outbound factors when making decisions regarding product placement. For example, the control system 202 can operate at the projected delivery location of a product supply and the projected outbound delivery location of the product. The control system can make decisions and send execution signals via automated systems and/or can efficiently assign tasks to human operators (pickers, loaders, etc.).

The control system 202 can determine that one or more robots or one or more pickers should perform one or more actions when fulfilling an order or for any other purpose. The actions of the one or more robots may require the robots to traverse the grid and/or perform actions, such as removing a container.

The control system 202 can be configured to analyze various paths in the grid to determine one or more paths that may be preferred over other paths, taking into account a set of constraints and conditions. These preferred paths can be provided to the robot once, periodically, and/or dynamically to control its movement in the grid.

A path may be preferred for many reasons, including but not limited to: shorter transport distance, higher expected average robot speed, lower likelihood of encountering traffic (congestion), lower total time required, lower likelihood of collisions, lower power usage, ease of switching to alternate paths, and ability to avoid obstacles (e.g., broken robots, fallen items, bumpy paths, parts of the path being repaired).

The control system 202 may use various algorithms to identify, design, and/or control the movements of the various robots to which it is connected. In some embodiments, the control system is implemented using one or more servers, each server comprising one or more processors configured to execute one or more sets of instructions stored on one or more non-transitory computer-readable media. Potential advantages of computer implementation include, but are not limited to, scalability, the ability to handle a large number of processes and computational complexity, accelerated response time, the ability to make decisions quickly, the ability to perform complex statistical analysis, the ability to perform machine learning, and the like.

These algorithms are discussed in depth further in the specification, and examples of path-finding algorithms and heuristic methods are provided according to some embodiments of the present invention.

Constraints may include the current layout of the grid, the physical characteristics of the robot (e.g., maximum speed, turning radius, turning speed, maximum acceleration, maximum deceleration), congestion (e.g., expected traffic load on a path or intersection), established "highways", characteristics of the items being transported by the robot (e.g., large, bulky, or fragile items), the state of the robot and the environment (including battery condition, damage, maintenance issues), and the state of the station (e.g., the destination station is full or temporarily blocked).

The control system 202 may be a real-time or near-real-time control system (controlling the actions of various units, including the robot and optionally other associated units, such as conveyors, pickers, and human labor). The control system 202 may include one or more modules. These modules may include a control interface 302, a movement optimization module 304, a product placement optimization module 306, a robot physical model module 308, a business rules module 310, a gap module 312, a reservation module 314, a command generation and scheduling program module 316, a robot communication module 318, a charging manager module 320, and an alert/notification module 322. These modules may be implemented in various ways; in some embodiments, they may be implemented as applications stored as instructions on one or more computer-readable media for execution by one or more processors.

According to some embodiments of the present invention, the control system 202 can control work allocation, workstation operation, robot movement, and/or container placement in real time or near real time. Work allocation, container movement, and placement can be facilitated by actions related to activities within the warehouse, such as fulfilling orders, reallocating containers to more accessible locations, anticipated scheduling sequences, maintenance operations, workstation operations, anticipation of future orders, etc.

The control interface 302 provides an interface for various external systems to provide operating instructions and information to the control system 202. In various embodiments, the control interface 302 may provide a human user interface and/or an interface with various machines and systems.

The human interface may include, for example, a keyboard, a visual display, a command prompt, etc.

The machine and system interfaces may include application programming interfaces (APIs) implemented using various specifications, including but not limited to Simple Object Access Protocol (SOAP) and Representational State Transfer (REST) services, and/or interfaces written in various programming languages. The control interface 302 may interact with various external databases, including but not limited to various warehouse management systems and order management systems, and may also receive information from various robots (e.g., a robot is malfunctioning, a robot needs to be recharged, a robot is en route to its destination, a robot has encountered an unexpected obstacle, etc.).

The control interface 302 can also receive information from and transmit information to the warehouse management system (WMS) regarding the control and movement of robots and containers. This information can include, but is not limited to, grid locations and sizes, subgrid setup, inventory and order master records, workstation locations, workstation-related parameters, and/or dispatch sequences (e.g., when orders need to be dispatched). After an action is performed, a container is brought to a workstation, workstation operations are completed, or a delivery load is complete, the control interface 302 can provide updates to the WMS. In some embodiments, a confirmation process occurs between the WMS and the control interface 302. These updates to the WMS can include, for example, updating inventory levels associated with a specific stock keeping unit number, updating container locations, updating the locations of items within a container, updating facility conditions, and the like.

In some embodiments of the system, in addition to the warehouse management system, there may be a separate order system that contains and provides information about various orders entering the system, order fulfillment, workstation operations, upcoming orders, and forecasted orders.

The control interface 302 may also receive commands to stop the operation of a specific robot, a group of robots, or all robots (eg, in the event of a malfunction, emergency, etc.).

The movement optimization module 304 can be configured to optimize robot movement by applying various algorithms to determine potentially advantageous routes from one location to another. Potential advantages may include shorter transport distances, lower likelihood of encountering congestion, shorter travel time, lower power consumption, collaboration with other robots, bypassing obstacles such as broken robots or uneven track areas, and coordination with various workstation operators.

The movement optimization module 304 can be configured to provide work allocation, planning, and scheduling functions, including developing a set of tasks and then selecting which picking station or robot to perform each task. For example, this can be based on the location of the robot or picking station, the specific capabilities of the robot or picking station, etc. In addition, the specific arrangement and specific action group required to fulfill a specific order are determined and actions/tasks are developed for one or more robots and/or one or more picking stations. Functionality can include, among other things, delivering empty containers to an inbound port, placing loaded containers around the warehouse, bringing containers to a picking station or other area, moving containers from one location to another in the warehouse, etc.

The movement optimization module 304 can be configured to interact with the product placement optimization module 306 to determine a set of potentially advantageous locations for placing items. For example, given that containers containing a particular SKU number are frequently requested, the product placement optimization module 306 can indicate that they should be placed in a certain location on a stack that is more easily accessible. Conversely, if containers containing a particular SKU number are infrequently requested, the product can be determined to be placed lower in a grid location that is less easily accessible.

In optimizing movement, the movement optimization module 304 can be configured to consider various factors related to both movement and operation performance, such as the expected time required to obtain a specific location, the depth of the container in the stack, the time required to remove the container from the stack, the various operations necessary to move the container above it to another location, etc.

The robot physics model module 308 can provide a set of inputs to the movement optimization module 304, which can convey a set of constraints on the robot's movement based on various factors (e.g., the robot can only move at 50% of its maximum speed when it is currently transporting a fragile item). The movement optimization module 304 can coordinate the movement of boxes into, out of, and within the grid.

In some embodiments, the movement optimization module 304 can dynamically recalculate the preferred path during the robot transport process to potentially determine an updated set of paths as conditions and constraints change over time.

In some embodiments, the mesh may be pre-processed by the movement optimization module 304 to potentially increase processing speed and/or reduce processing load. Other methods of reducing processing load are also contemplated, such as reducing the depth and breadth of the search, dividing the mesh into sub-grids, decentralized processing, caching future routes, computationally simplifying the mesh (e.g., reducing the number of nodes analyzed), reducing path recalculations, etc.

In some embodiments, the movement optimization module 304 can divide the grid into several smaller sub-grids for analysis. This division can reduce the processing power required, which is particularly useful when the grid is very large. For example, a 1000x1000 grid can be divided into 100 100x100 grids, and each grid can be analyzed separately. This is particularly useful when the system is trying to control a large number of robots or consider many conditions.

The movement optimization module 304 may also interact with the gap module 312 and the reservation module 314 to determine whether navigating the proposed path will encounter issues with gaps and reservations with other robots, and to identify pathways that may reduce the likelihood of encountering these issues.

If the required container is located at a different depth in the stack, the movement optimization module 304 is required to control one or more robots to move the container out of the stack in order to access the required container. The movement optimization module 304 can coordinate the movement of one or more robots so that the one or more robots cooperate to move the container out of the stack.

In some embodiments, the movement optimization module 304 may not necessarily or even require that the container be returned to the stack. Rather, the container removed from the stack may have an optimal location determined by the product placement optimization module 306 and may be moved there by the one or more robots. A potential advantage of this embodiment is that increased efficiency is observed when containers are not returned to their original location but are instead placed in a more optimal location.

In some embodiments, the gap module 312, the reservation module 314, and the movement optimization module 304 are used together as a path conflict resolver, where the movement optimization module 304 develops the path, the path is then reserved using the reservation module 314, and finally the gap module 312 provides an instant method to determine priority when the robot encounters potential conflicting paths.

In some embodiments, the movement optimization module 304 is configured to account for situations where a robot attempts to bring a container to a full station. In this case, the movement optimization module 304 is configured to direct the robot to bring the container to a nearby station, where the robot holds it until the station can accept it. When the station can accept the container, the robot drops it off. In these embodiments, the held containers can be dropped off in priority order.

In some embodiments, if the station where the held container is placed becomes empty before it reaches its storage location, the movement optimization module 304 will re-plan to place the container directly without holding it.

In some embodiments, the movement optimization module 304 is further configured to perform a pre-fetch operation, wherein a container is moved to the vicinity of a station before it is needed, and is then ready to be dropped off when needed, thereby reducing the uncertainty of the drop-off time.

In some embodiments, the system may be configured to plan the robot path and establish a reservation of robot paths far into the future to allow for completion of the algorithm.

In some embodiments, the degree of pre-planning required can be calculated through simulation.

The simulation can be used to determine (in a statistical sense) the efficiency gains of distant future plans and the efficiency losses that may occur if the robot fails to maintain its plan and must replan due to various reasons such as short-term communication packet loss and/or the robot operating outside of the allowed tolerance range.

The product placement optimization module 306 can be configured to determine a set of potentially favorable locations for placing a specific container containing a specific product. The product placement optimization module 306 can utilize relevant information, such as the layout of the grid, the frequency with which a specific product is needed, future orders, predicted future orders, workstation locations, charging station locations, and congestion levels in specific areas and path branches, to determine the set of potentially favorable locations for placing a specific container containing a specific product.

The robot may be assigned the task of transporting one or more containers to meet the needs of one or more service picking stations, each of which may contain one or more items. Each container may have an index number associated with a stacking location so that a specific container can be biased to be placed in a specific stacking location.

The distribution and placement of containers in stacks or relative to a grid layout may contribute to the overall operational efficiency of the warehouse.

There are various situations where containers need to be placed at a certain location in a facility, and these situations provide opportunities to re-evaluate and/or optimize the distribution of locations of containers in the facility.

There are various considerations that may indicate one location is better or worse than another, including but not limited to distance to the workstation, the level of congestion in the area, which containers will be blocked by a particular container, logical grouping of containers relative to environmental factors (e.g., containers containing flammable items may require special placement), and intelligent pre-fetching of locations by workstations.

These considerations may be used by the system to compare one location to another, for example, by using a weighting algorithm or any other suitable approach.

For example, when new containers are placed into the facility, when containers are returned to the facility, when a robot moves one or more containers to try to access goods stored deep in a stack, when goods are placed in/out of a container, when a container is marked as damaged, when a container is marked as dirty, etc.

This optimization may be performed multiple times, for example, in some embodiments, the optimization is performed to determine a new position for each container that must be moved, such as those that must be removed to remove a particular container located thereunder.

For example, the number of robot movements and operations can potentially be reduced if frequently ordered items and a certain number of items per given stock keeping unit number are distributed in the most easily accessible areas of the warehouse (such as the locations closest to each picking station and/or the top of the container stack).

The "active window" is defined as the number of order values of containers that are active and determined by the system (inventory at the service station). The product placement optimization module 306 can be configured to assign scores to containers so that the overall honeycomb layout is biased toward active containers at the top, with reserve inventory located below.

This scoring system can be determined by the business rules module 310 and set based on information such as inventory expiration dates. A container's score can be calculated using, among other information, historical orders, and this score can be continuously updated each time the inventory level of a SKU number changes. The scoring system can be used to help influence container location to maintain optimal container placement within a facility.

In some embodiments, the system can be configured to control the movement of the robot to maintain an "active" pool of one or more containers per stock keeping unit number (SKU#) to meet the needs of one or more service stations. When the "active" pool becomes empty, a "reserve" container can be placed in the "active" pool.

In some embodiments of the system, the system may be configured to control the robot movement using a "relinquishment algorithm" to determine a "best fit" stacking location from a pool of available empty locations when placing a container.

In some embodiments, the "active" pool may be configured to support concurrent requests from the one or more service workstations.

In some embodiments, the product placement optimization module 306 may also balance orders between the picking stations.

The robot physics model module 308 can be configured to store a set of variables that simulate specific physical properties of the robot. For example, the model can represent physical characteristics such as the robot's length, weight, height, and width, the robot's maximum load capacity, the robot's rotational speed, the robot's hoist cycle time, the robot's maximum speed and acceleration, and the robot's ability to perform certain actions within a certain battery life. The robot physics module 308 can be connected to the business rules module 310 to determine restrictions on certain characteristics of the robot's movement, including the robot's maximum speed, maximum acceleration, and maximum rotational speed. For example, a robot carrying a number of boxes of eggs may be required to accelerate/decelerate at only 25% of its maximum acceleration/deceleration due to the fragility of eggs when subjected to physical forces.

The business rules module 310 develops and applies a set of business rules based on the specific circumstances of the warehouse, robot, and communication system. For example, the business rules module 310 can provide various constraints that are effective for the robot physical model module 308 for certain categories of goods, potentially reducing the amount of damage to goods during transportation. Examples of situations where business rules can be implemented include high-risk products (such as acids and bleach), containers with aerosols, and containers containing flammable materials, among others. Empty containers can also be handled differently than other containers.

The business rules may include actions such as cleaning a container before reuse, slowing down a robot that contains certain items, etc.

The business rules module 310 can also be configured to develop and apply multiple sets of rules for managing product placement. For example, different rules can be used for high-frequency items, items that may be picked soon due to upcoming orders, etc.

The clearance module 312 can be configured to store and provide clearances for each robot. A clearance system can be used to determine whether a path is clear of obstacles for a robot to traverse. The clearance module 312 can be implemented as a passive collision avoidance system, where the robot is given only the minimum amount of work that does not affect its performance.

After a robot with new instructions is provided, the clearance module 312 checks that it is unlikely to collide with another robot based on, for example, grid size, grid position, planned move commands generated, move command cancellations (generated for events such as controlled stops), the robot's current position and speed, the robot's braking capabilities, and where it is cleared for access.

The clearance module 312 can be configured to issue clearance commands on the fly and can be used to grant permission to the robot to continue moving along its planned path. New clearance commands can be generated (or maintained) based on each robot status report. Thus, the clearance module 312 can function as a path conflict resolver. When clearance is needed, the clearance module 312 can interact with the movement optimization module 304 to dynamically replan the route to resolve or avoid conflicts.

The gap module 312 can provide the control interface 302 with the gap contents of a path, notify when a gap is issued (such as notifying the planning system, as this allows dynamic replanning from the end of the current gap), notify when a gap is retained (to determine error conditions and determine the need for replanning), and notify the alarm system (because there is a potential problem with the robot, robot communication, or the control system 202).

The gap module 312 may be configured to design a gap solution based on a set of tolerances, including missed messages, processing time, clock synchronization, and differences between the robot and the physical model.

The gap module 312 can provide a set of safe entry times for one or more locations on the grid based on the robot position and velocity updates and the given/reserved gaps. The set of safe entry times can be dynamically updated as the grid conditions change.

In some embodiments, the clearance module 312 can be configured to provide clearance to the robot only for a certain period of time (e.g., 3 seconds). The clearance given to the robot can be configured to be sufficient for the robot to stop without risk of collision.

In some embodiments, the gap module 312 can be configured to provide gaps to allow the control system 202 to miss a configurable number of status messages from the robot and still allow the robot to continue operating for a short period of time. This design may make the system more tolerant to missed packets, which may facilitate continued operation even when encountering some communication problems. The configurable number can be set so that there is a high probability that the control system 202 will receive a status message from the robot before the robot automatically decelerates to a stop at the end of its gap.

In some embodiments, if the robot has begun to slow down, it will be allowed to stop and the control system 202 can then cancel its previous reservation and replan its path on the grid.

The reservation module 314 reserves various paths on the grid (e.g., robot A plans to take path X and reserves path X within its expected travel time, while robot B chooses path Y knowing that robot A has reserved path X). The reservation module 314 can be designed to create non-conflicting robot movement plans and can be configured to work in conjunction with the gap module 312 and the movement optimization module 304.

The reservation module 314 can be configured to provide reservations for grid locations for robots over a period of time, wherein no two robots are given overlapping reservations, taking into account tolerance for robots that deviate slightly from the plan, tolerance for lost robot communication messages, tolerance for clock differences, etc.

In some embodiments, the reservation module 314 is used to pre-reserve routes and ensure that robots do not plan to take conflicting paths, especially when a large number of robot actions and tasks are occurring simultaneously. The reservation module 314 can be configured to allow sufficient margin to allow any robot to stop under controlled braking without risk of collision.

The reservation module 314 can be configured to interact with the movement optimization module 304 to establish a robot path reservation in the distant future for advance planning. In some embodiments, the reservation module 314 and the movement optimization module 304 allow for sufficient advance planning to complete the calculation of the movement algorithm.

The command generation and schedule planning module 316 generates a set of instructions to be transmitted to the one or more robots. These instructions may include, for example, instructing robot A to move to location B to pick up container C, bring container C to a workstation, and then return container C to a specific location D. These instructions can be transmitted in near real-time/real-time configuration, just-in-time configuration, and/or provided in advance to allow for planned/scheduled routes. In addition, in some embodiments, the command generation and schedule planning module 316 coordinates booking and execution slots to help robots quickly navigate through the facility.

The command generation and scheduling module 316 can be configured to provide a command set that includes a single path, one or more paths, and/or a number of operations to be performed at various locations. The command generation and scheduling module 316 provides these commands to the robot communication module 318 for provision to individual robots. In some embodiments, the command generation and scheduling module 316 pre-populates instructions for a specific robot—these instructions may then be provided to the robot via the robot communication module 318 for future execution.

The robot communication module 318 can be configured to transmit information back and forth from the robot via the one or more base stations and the base station controller 206. In some embodiments, the robot communication module 318 can communicate using wireless signals. As described above, these instruction sets do not have to be immediate, and instruction sets can be sent for coordinating future movements.

The robot communication module 318 can receive status reports from each robot. The robot communication module 318 can be implemented in various ways, such as using synchronous, asynchronous, polling, push or pull methods. In addition, various embodiments may or may not include the use of a communication "handshake."

In some embodiments without handshaking, the communication system may not guarantee message delivery, and packet loss may occur. Potential advantages of such a system may include reduced bandwidth requirements and best-effort delivery of instructions. Various schemes can be implemented to minimize the impact of packet loss, such as timed replay of instruction packets, sending overlapping instruction packets containing parity information or other verification schemes, or other flow control and retransmission schemes.

In other embodiments of the present invention, a "handshake" may be used to ensure that a packet is received.

A command to the robot may be issued before a start time to perform an operation to be performed by the robot, and the time from the start time to when the command is issued may be a configurable parameter.

In some embodiments, commands are repeated to the robot to ensure delivery, and the robot can provide confirmation that the command has been received.

If the message is not received before the scheduled start time, the robot can be configured to ignore the command and can return a status message indicating that the command was received too late. In this case, the robot control system 202 can be configured to cancel the existing reservation for the robot and reschedule the task assignment for the robot.

In some embodiments, the robot returns a regular status message confirming receipt of the last command (e.g., via a command sequence number). In some embodiments, the robot control system 202 can be configured to not send new commands to a particular robot until the last command issued has been acknowledged by that robot. If the robot does not acknowledge the command after a specified period of time (e.g., a configurable timeout period), the robot control system 202 can be configured to cancel the existing reservation for that robot. Upon reestablishing communication with the robot, the robot control system 202 reschedules operations for the robot.

After receiving each robot status message, the robot control system 202 can be configured to enlarge the robot's current movement gap through the gap module 312 .

The charging management module 320 may be configured to formulate a movement plan to charge the robots. The charging management module 320 may be configured to estimate when the robots will reach a specified minimum charge level and ensure that all robots can be charged at or before that charge level.

The alert/notification module 322 may be configured to provide alerts or notifications to the control interface 302 when a potential problem has occurred or based on certain business rules (eg, a certain number of slots have been reserved due to a conflict).

The present systems and methods can be implemented in various embodiments. A suitably configured computer device and associated communication networks, devices, software, and firmware can provide a platform for implementing one or more of the above-described embodiments. For example, FIG1 illustrates a general-purpose computer device 100 that may include a central processing unit ("CPU") 102 connected to a storage unit 104 and a random access memory 106. The CPU 102 may process an operating system 101, application programs 103, and data 123. The operating system 101, application programs 103, and data 123 may be stored in the storage unit 104 and loaded into the memory 106 as needed. The computing device 100 may also include a graphics processing unit (GPU) 122 operably connected to the CPU 102 and the memory 106 to offload intensive image processing computations from the CPU 102 and run these computations in parallel with the CPU 102. An operator 107 can interact with the computer device 100 using a video display 108 connected via a video interface 105 and various input/output devices such as a keyboard 115, a mouse 112, and a disk drive or solid-state drive 114 connected via an I/O interface 109. In a known manner, the mouse 112 can be configured to control cursor movement within the video display 108 and operate various graphical user interface (GUI) controls that appear within the video display 108 with mouse buttons. The disk drive or solid-state drive 114 can be configured to accept computer-readable media 116. The computer device 100 can be networked via a network interface 111, allowing the computer device 100 to communicate with other appropriately configured data processing systems (not shown). One or more sensors 135 of various types can be used to receive input from various sources.

The present system and method can be implemented on virtually any computer device, including desktop computers, laptop computers, tablet computers, or wireless handheld devices. The present system and method can also be implemented as a computer-readable/usable medium containing computer program code that causes one or more computer devices to perform each of the various steps in a method according to the present invention. If more than one computer device performs the entire operation, the computer devices distribute the individual steps via the Internet. It should be understood that the terms computer-readable medium or computer-usable medium include one or more of any type of physical embodiment of the program code. Specifically, the computer-readable/usable medium can include program code embodied on one or more portable storage articles (e.g., optical disks, magnetic disks, magnetic tapes, etc.), or one or more data storage partitions of a computing device, such as a memory associated with a computer and/or storage system.

The mobile application of the present invention may be implemented as a web service where the mobile device includes a link for accessing the web service instead of a native application.

The described functionality can be implemented on any mobile platform, including iOS™ platform, ANDROID™ platform, WINDOWS™ platform or BLACKBERRY™ platform.

Those skilled in the art will appreciate that other variations of the embodiments described herein may be implemented without departing from the scope of the present invention. Therefore, other modified embodiments are possible.

Many different algorithms and techniques can be used to determine the optimal path for a robot, including but not limited to: branch and bound algorithms, constraint programming, local search, heuristics, graph traversals, dynamic path learning advisors, pruning techniques, and Bayesian graph search techniques, Dijkstra's algorithm, Bellman-Ford algorithm, Floyd's algorithm, Johnson's algorithm, breadth-first recursive search and breadth-first recursive search, weighted paths, A* search algorithm, and A* search algorithm variants (such as D*, domain D*, IDA*, edge, edge-preserving A*, generalized adaptive A*, lifetime planning A*, simplified memory-bounded A*, jump point search, Theta*).

In the following sections, example search algorithms and heuristic algorithms are provided according to some embodiments of the present invention.

Example Search Algorithm

In this section, example simplification algorithms are provided according to some embodiments of the present invention.

For ease of explanation, according to some embodiments of the present invention, the algorithm is provided in a graphical form, such as the workflow diagram shown in Figure 4. It should be understood that this example algorithm is a non-limiting example and is only used for the purpose of illustrating the above concepts.

The algorithm may be an iterative search algorithm that may utilize branch and bound search and apply a "nearest best first" heuristic model that includes a congestion avoidance "heat map." Branches may be selected using a weighted cost function, and the algorithm may be loosely coupled to grid/robot shape/size.

In some embodiments, branches may be stored in a sorted set.

According to one embodiment of the algorithm, the following recursive branch and bound function is applied:

Each iteration:

(a) choose the lowest cost branch b,

(b) Use branches b in all directions to create a new branch B

(c) For each branch b’ in B:

If b' reaches the target:

Return b’

otherwise:

Add b' to search

Cost comparator allows tracking of lowest cost branch for next iteration

In performing the path search, different heuristics can be applied to reduce the required computations, removing entire branches or performing less computationally intensive analysis, depending on the heuristic applied. Example heuristic techniques are described later in this specification.

When a new branch conflicts with a path that another robot might take, or conflicts with an idle robot, the search algorithm can:

changing the branch to escape the conflicting reservation (if the acceleration profile allows);

Change the branch to include a wait anywhere in its path; or

If it is not feasible, discard the branch

In some embodiments, a path may be selected with the robot waiting at its starting point.

In doing so, the search space is never truly exhausted (e.g., if there is currently no acceptable path for a robot to reach its destination, a path can be chosen while the robot waits until a non-conflicting path becomes available).

Example Heuristics

The search algorithm can be configured to prioritize balancing any number of objectives, such as taking the shortest possible time, tending to avoid congested areas, etc.

The following is a simple, non-limiting example of using a heuristic, for illustration purposes only.

In one embodiment of the present invention, each search can track the current lowest-cost branch, and a weighted cost function can be used to bias the order of branch selection based on different heuristics, including: (a) estimated shortest path time and (b) estimated cumulative heat based on a heat map. Other heuristic techniques are contemplated, but for illustrative purposes only, further details will be provided for the two methods specified above.

(a) Estimated shortest path time

For any branch, the control system can determine the shortest possible path time from the current branch to the destination.

The expected time cost can then be determined as the total time of the branch so far (including, for example, any waiting required, etc.) plus the time of the shortest possible unconstrained path to the target.

(b) Estimated minimum heat (based on heat map)

In making a heatmap, you can assign a "heat" value to each coordinate, similar to a congestion model for points on a grid, or to specific areas of the grid.

Figure 5 is an example heat map according to some embodiments of the present invention.

In some embodiments, the distance to the workstation may be used to determine the "heat" value, but in other embodiments of the invention, various other techniques may be used to observe/learn/calculate/predict the "heat", some of which may be dynamic or iterative techniques.

Similar to estimating the shortest path, an unconstrained path can be extended to the destination.

The expected minimum heat can then be determined. In some embodiments, the expected heat cost is the sum of the heats of all visited coordinates in the current branch plus the "coldest" (least hot) heat of the expected path.

Example weighted cost function

In some embodiments, the algorithm used is based on a weighted cost function. Such an algorithm may be suitable for optimizing the associated cost coefficients by studying the results of a large number of parallel simulations in the cloud configured to use different coefficients, and/or applying various machine learning methods and techniques, possibly using a large amount of observational and/or simulated data.

In some embodiments, the search algorithm has two cost coefficients: (a) the expected shortest path time coefficient (Ct), and (b) the expected minimum heat coefficient (Ch).

In some embodiments, the search algorithm may include the following equation:

Branch cost = _Ct *PSP + _Ch *PMH

(PSP refers to the predicted shortest path time, PHM refers to the predicted minimum heat)

In some embodiments, the cost function can be used with configurable or machine learning derived indices that model complex relationships. An example simplified cost function (for illustration purposes only) includes:

Branch cost = C _t *PSP ^x + C _h *PMH ^y , where x and y can also be configurable and/or machine learning exponentials.

FIG6a is a table showing how the estimated cost of a search branch changes when different coefficients are used in the path search algorithm. These coefficients can be extracted using machine learning techniques according to some embodiments of the present invention.

FIG. 6b illustrates how the use of different cost coefficients as shown in FIG. 6a changes the branch that will be selected on the next iteration of the search algorithm.

In some embodiments, the control system 202 can also be configured to develop, adapt, and apply a set of rules over time to refine a set of machine learning coefficients and/or indices. Using machine learning coefficients and/or indices over time can potentially increase the effectiveness of heuristic techniques.

Example branch search

The system can be configured to adjust the robot path to account for the location of idle robots. In some embodiments, there may be idle robots that can be tracked independently of robots with tasks. These idle robots may not have a planned path and associated reservations and may need to be considered separately.

At the end of a mission, a separate "branch search" can be performed. This "branch search" can include finding a path to move the currently idle robot, or a robot that has entered an idle state in the path of a robot currently performing a mission (hereinafter referred to as the master robot), to a position where it can continue to be idle and not block the path of the master robot.

In some embodiments, this "branch search" involves an execution search where, for each robot that is now idle or will enter an idle state in the master robot's path, the execution search may be considered resolved when a position is found that it can remain indefinitely.

The "branch and bound search" can use the same branch and bound search algorithm as the main robot path search, but may have different cost coefficients and solution criteria. If the robot cannot give way in time, a wait can be added to the main robot's path and the main robot's path can be recalculated.

Example Replacement Algorithm

An algorithm may be used to determine the stacking location of containers to be returned. Containers may be returned for a variety of reasons, and the location at which they are returned may be optimized for a variety of advantages, such as improving the distribution of items/containers within the hive.

Each stacking position in the hive can be scored using a configurable weighted cost function:

Average distance to all workstations (measured by robot operation time);

distance to the nearest workstation (measured by robot operation time);

as well as

Approximate mining cost (if depth > 0)

After all operations in the plan have been executed, the system may maintain a "hive plan" of the current end state of the hive.

The "hive plan" can also track "available surfaces" where the robot can place containers. Each container's position has an index in the completely ordered set of containers defined by the product placement optimization module 306.

In the completely ordered set of stacking positions defined by the weighted cost function, each stacking position has an equivalent index.

These indices are remapped to the range 0-1 by dividing by the size of their respective collections, and the stacking locations in the available surface are arranged according to how closely their indices match the indices of the containers.

The final selection is made by a weighted cost function of the differences between these indices and other factors, such as how long the ideal path from the source to the stacking location is and how long the stack remains in the current plan.

Other business rules can be enforced at this stage, such as limiting the total weight of the stack, controlling the location of hazardous or special substances (such as sprayers and flammable materials), etc.

Example return scenario

The following is an example return process supported/controlled by the system. This process can be used when an order is canceled, a load does not leave the hive, an order is returned by the customer, or a shipment cannot be made to the customer. Other scenarios are also contemplated. Returned products (possibly in containers such as totes or other storage devices) can be processed at a workstation that provides product rework or product rejection.

The containers/totes can be scanned so that the controller can place the storage bins it anticipates will be needed near the workstation. Supply bins can be selected based on stock keeping unit (SKU) numbers and expiration dates. Items can be retrieved and scanned one by one by a picker. When the container arrives at the workstation, the picker (automatically or manually) is instructed/controlled to place the items into the container.

The picker may also be required to confirm that no items with that SKU number are missing before the container is released.

Products no longer suitable for return to inventory can be picked into containers that, at various times, such as when full or at the end of the day, can be removed from the workstation and their contents sent to another area, such as a staff store or for appropriate disposal.

While the present invention has been provided and described with respect to certain, presently preferred embodiments, many variations and modifications are possible without departing from the spirit and scope of the present invention. Therefore, the present invention is not limited to the specific components or detailed methods or structures disclosed above. Except for the necessary or inherent order of the process itself, the present invention (including the accompanying drawings) does not illustrate or imply a specific order of the steps and stages of the described methods or processes. In many cases, the order of the process steps can be changed without changing the purpose, effect, or introduction of the method described herein. The scope of the present invention is to be determined solely by the appended claims, with due regard to the doctrine of equivalents and related theories.

Claims (45)

1. A system for controlling the movement of one or more transport devices, the transport devices being configured to transport containers stored in several stacks of a facility having several aisles arranged in a grid structure above the stacks, the one or more transport devices being configured to operate on the grid structure, the system comprising: A control unit is configured to determine and reserve routes for moving one or more transport devices through the plurality of pathways and to determine and reserve routes for moving the one or more transport devices while transporting one or more of the plurality of containers; to determine and control one or more transport devices to remove at least one first container from one or more of the plurality of stacks; wherein The removal of at least one first container is achieved by moving at least one second container in the stack before the at least one first container is removed; Controlling the removal and movement of the at least one first container taken out by the transport equipment; and Instruct one or more of the transport equipment to transport the at least one second container to an alternative location within the facility. The control unit includes a product placement optimization module configured to determine the available alternative locations from empty locations in any stack other than the stack where the at least one second container has been removed. 2. The system of claim 1, wherein the product placement optimization module is further configured to determine alternative locations by scoring using a configurable weighted cost function, wherein the location of each stack is based on the average distance to all workstations, the distance to the nearest workstation, and approximate excavation cost. 3. The system of claim 2, wherein the product placement optimization module is further configured to determine the alternative locations based on the score of a configurable weighted cost function, the path length from the source to the stacking location, and the difference in retention time in the stack. 4. The system according to claim 2 or 3, wherein the product placement optimization module is further configured to determine the alternative locations based on one of the total weight of the stack, the location of the controlled hazard, and the location of the controlled special substance. 5. The system according to any one of claims 1 to 3, wherein the product placement optimization module is further configured to determine the alternative locations based on at least one of the following information: the layout of the grid structure, the frequency of demand for a particular product, future orders, predicted future orders, the location of workstations, the location of charging stations, and the congestion level of specific areas and path branches. 6. The system according to any one of claims 1 to 3, wherein the alternative location may include any location outside the stack but within the facility. 7. The system according to any one of claims 1 to 3, wherein the container or each container contains an article, the article being stored in the container in the stack for later retrieval. 8. The system of claim 1 further includes one or more utilities providing a clearance system for allowing or stopping the movement of the one or more transport devices to avoid collision. 9. The system of claim 1 further includes one or more utilities, said one or more utilities including optimization tools configured to optimize the movement and actions of the one or more transport devices through said plurality of paths. 10. The system of claim 9, wherein the optimization tool includes a placement tool configured to optimize the placement of the plurality of containers via the one or more transport devices in the facility. 11. The system of claim 1, further comprising one or more utilities for controlling movement or operation of one or more of the containers in one or more workstations. 12. The system according to any one of claims 9-11, wherein any one of the utilities for optimizing the movement and action of any of the transport devices utilizes one or more routing algorithms. 13. The system according to any one of claims 9-11, wherein any one of the utilities for optimizing the movement and action of any one of the transport devices utilizes one or more congestion mitigation techniques. 14. The system according to any one of claims 9-11, wherein any one of the utilities for optimizing the movement and actions of any one of the transport devices utilizes one or more machine learning techniques. 15. The system according to any one of claims 9-11, wherein any one of the utilities for optimizing the placement of the plurality of containers in the facility is an update tool for updating the inventory level of the facility based on the depletion of one or more of the plurality of items in the facility. 16. The system of claim 10, wherein any of the utilities further comprises a control tool for controlling the movement of the one or more transport devices based at least on the workload of the one or more workstations. 17. The system according to any one of claims 8-11, wherein any one of the utilities includes a gap system, the system including a configuration tool that enables the system to allow interrupted communication with at least one of the one or more transport devices. 18. The system according to any one of claims 8-11, wherein any one of the utilities includes a route determination and booking tool and instructs several transport devices to cooperate in transporting one or more of the several containers. 19. The system according to any one of claims 8-11, wherein any one of the utilities includes a determining tool for determining and reserving routes to remove idle transport equipment from optimal routes for use by other transport equipment. 20. The system according to any one of claims 1-3, wherein the facility is divided into several subgrids. 21. The system according to any one of claims 1-3, wherein one or more control commands for controlling the movement of the plurality of transport devices are provided to the plurality of transport devices before the plurality of transport devices move. 22. The system according to any one of claims 8-11, wherein any one of the utilities includes an optimization tool for optimizing the container or each container returning to the optimal empty space in the stack within the facility. 23. The system according to any one of claims 8-11, wherein any one of the utilities includes an operating tool for dynamically replacing damaged or lost items with alternative containers in a stack. 24. The system according to any one of claims 8-11, wherein any one of the utilities further comprises an optimization tool for the remaining stacking based on cost function analysis. 25. A method for controlling the movement of one or more transport devices, the transport devices being configured to transport containers stored in a plurality of stacks in a facility having a plurality of aisles arranged in a grid structure above the stacks, the one or more transport devices being configured to operate on the grid structure, the method comprising: Determine and reserve routes for moving the one or more transport devices through the plurality of channels, and determine and reserve routes for moving the one or more transport devices when transporting one or more of the plurality of containers; Determine and control one or more transport devices to remove at least one first container from one or more of the stacks; wherein, The removal of the at least one first container is achieved by moving at least one second container in the stack before removing the at least one second container; the removal and movement of the at least one first container by means of a transport device are controlled; and Instruct one or more of the transport equipment to transport the at least one second container to an alternative location within the facility. The available alternative positions are determined from empty positions in any stack other than the stack where the at least one second container has been removed. 26. The method of claim 25, wherein the alternative locations are determined by scoring using a configurable weighted cost function, the location of each stack being based on the average distance to all workstations, the distance to the nearest workstation, and approximate excavation cost. 27. The method of claim 26, wherein the alternative location is determined based on a score of a configurable weighted cost function, the path length from the source to the stacking location, and the difference in retention time in the stack. 28. The method of claim 26 or 27, wherein the alternative location is determined based on one of the total weight of the stack, the location for controlling hazards, and the location for controlling special substances. 29. The method according to any one of claims 25 to 27, wherein the alternative location is determined based on at least one of the following information: the layout of the grid structure, the frequency of demand for a particular item, future orders, predicted future orders, the location of the workstation, the location of the charging station, and the degree of congestion in a particular area and path branch. 30. The method according to any one of claims 25 to 27, wherein the container comprises articles stored in and taken out of the facility. 31. The method according to any one of claims 25 to 27, further comprising the step of providing a clearance system for permitting or stopping the movement of the one or more transport devices to avoid collision. 32. The method according to any one of claims 25 to 27, further comprising the step of optimizing the movement and operation of the one or more transport devices through the plurality of pathways. 33. The method according to any one of claims 25 to 27, further comprising the step of optimizing the placement of the plurality of containers by means of the one or more transport devices in the facility. 34. The method of claim 33, further comprising the step of controlling movement or operation of each of the containers in one or more workstations. 35. The method of claim 33, wherein optimizing the movement and actions of the transport equipment or each transport equipment comprises using one or more pathfinding algorithms. 36. The method of claim 33, wherein optimizing the movement and actions of the transport equipment or each transport equipment includes using one or more congestion mitigation techniques. 37. The method of claim 33, wherein optimizing the movement and actions of the transport equipment or each transport equipment comprises using one or more machine learning techniques. 38. The method of claim 33, wherein the placement of the plurality of containers in the facility is optimized, and the inventory level of the facility is updated based on the depletion of one or more of the plurality of items in the facility. 39. The method of claim 34, wherein controlling the movement of one or more of the transport equipment is based at least on the workload of the one or more workstations. 40. The method according to any one of claims 25 to 27, further comprising the step of providing a gap that allows for interruption of communication with at least one of the one or more transport devices. 41. The method according to any one of claims 25 to 27, further comprising the step of instructing a plurality of transport devices to cooperate in transporting one or more of the plurality of containers. 42. The method according to any one of claims 25 to 27, further comprising determining and reserving routes to remove idle transport equipment from the optimal route for use by other transport equipment. 43. The method according to any one of claims 25 to 27, wherein the facility is divided into several sub-grids. 44. The method according to any one of claims 25 to 27, wherein one or more control commands for controlling the movement of the plurality of transport devices are provided to the plurality of transport devices before the plurality of transport devices move. 45. The method of any one of claims 25 to 27, wherein one or more utilities are provided to determine further optimizations of the remainder of the stack based on cost function analysis.