Patent Description:
Ordering products over the internet for home delivery is an extremely popular way of shopping. Fulfilling such orders in a timely, accurate and efficient manner is logistically challenging to say the least. Clicking the "check out" button in a virtual shopping cart creates an "order. " The order includes a listing of items that are to be shipped to a particular address. The process of "fulfillment" involves physically taking or "picking" these items from a large warehouse, packing them, and shipping them to the designated address. An important goal of the order-fulfillment process is thus to ship as many items in as short a time as possible.

The order-fulfillment process typically takes place in a large warehouse that contains many products, including those listed in the order. Among the tasks of order fulfillment is therefore that of traversing the warehouse to find and collect the various items listed in an order. In addition, the products that will ultimately be shipped first need to be received in the warehouse and stored or "placed" in storage bins in an orderly fashion throughout the warehouse so they can be readily retrieved for shipping.

In a large warehouse, the goods that are being delivered and ordered can be stored in the warehouse very far apart from each other and dispersed among a great number of other goods. With an order-fulfillment process using only human operators to place and pick the goods requires the operators to do a great deal of walking and can be inefficient and time consuming. Since the efficiency of the fulfillment process is a function of the number of items shipped per unit time, increasing time reduces efficiency.

In order to increase efficiency, robots may be used to perform functions of humans or they may be used to supplement the humans' activities. For example, robots may be assigned to "place" a number of items in various locations dispersed throughout the warehouse or to "pick" items from various locations for packing and shipping. The picking and placing may be done by the robot alone or with the assistance of human operators. For example, in the case of a pick operation, the human operator would pick items from shelves and place them on the robots or, in the case of a place operation, the human operator would pick items from the robot and place them on the shelves.

While using mobile robots and people in a busy warehouse environment increases efficiency it also increases the likelihood of robots colliding with obstacles, such as walls, shelving, people, other robots, among other things. In order for the robots to avoid obstacles they must perceive the obstacles with one or more sensors, such as a laser scanner, and then mark their observations map or grid. From there, the robots generate a plan and execute control trajectories to avoid the obstacles. Problematically, capturing and processing such a large amount of data, while the robot is navigating the environment, may result in a control cycle time for the mobile robot which is not quick enough to generate a control trajectory to avoid the obstacle.

Therefore, a need exists for an improved obstacle prediction and avoidance system and method to increase safety and reduce potential damage to robots and other objects within the environment.

<CIT> provides a method including determining a path to be followed by a vehicle through an environment. <CIT> provides a moving device determining an obstacle virtual existence region of a simple graphic approximating a detected obstacle to detect the obstacle in a real time and determine a smooth avoidance path by calculation, thereby performing collision prediction. <CIT> provides robot platforms, methods, and computer readable media. <CIT> provides materials handling vehicle comprising a path validation tool and a drive unit, steering unit, localization module, and navigation module that cooperate to navigate the vehicle along a warehouse travel path.

An object of this invention is to provide an obstacle prediction and avoidance system to increase safety and reduce potential damage to robots.

The invention provides a method for predicting a collision between a mobile robot and an obstacle in an environment includes obtaining laser scan data for the mobile robot at a current location in the environment and predicting a future location of the mobile robot in the environment. The method also includes producing predicted laser scan data corresponding to the future location of the mobile robot in the environment and assessing the predicted laser scan data relative to the mobile robot at the current location to determine whether a collision with an obstacle is predicted, as defined by independent claim <NUM>.

In the embodiments one or more of the following features may be included. The laser scan data for the mobile robot at a current location may include raw data output from a laser scanner on the mobile robot. The raw data output from the laser scanner for the mobile robot at the current location may include laser scan points indicating points of reflection off of obstacles in the environment. The step of predicting the future location of the mobile robot in the environment may include estimating the future location of the mobile robot moving along an arc path after N seconds of travel from the current location using a commanded velocity of the mobile robot. N may be a number between <NUM> and <NUM>. The predicted laser scan data may include predicted laser scan points indicating predicted points of reflection off of obstacles in the environment from the future location of the mobile robot. The method may further include representing the mobile robot as a polygon. The polygon representing the mobile robot may be an R-sided, convex polygon. The step of assessing the predicted laser scan data relative to the mobile robot at the current location may include connecting each of the laser scan points with a corresponding predicted laser scan point with an arc, thereby forming a plurality of arcs. Each arc of the plurality of arcs may comprise a plurality of line segments, L. The step of assessing the predicted laser scan data relative to the mobile robot at the current location may include determining if any of the plurality of arcs intersect with a point on the polygon representing the mobile robot, which is indicative of a potential collision between the mobile robot and an obstacle. The method may further include adjusting the commanded velocity of the mobile robot using a scaling factor based at least in part on a depth of incursion into the polygon for at least one intersecting arc. The depth of incursion into the polygon for each intersecting arc may be determined based on the length of an arc length approximation for the intersecting arc. For each intersecting arc, a ratio of a straight line distance from the current laser scan point on the obstacle to the point of intersection on the polygon relative to the arc length approximation may be determined and the minimum ratio is used as the scaling factor.

The invention provides an autonomous mobile robot configured to predict a collision with an obstacle in an environment. The robot includes a mobile robot base and a laser scanner mounted on the mobile robot base. There is a computer on the mobile robot base, including a processor and a memory. The computer is operatively coupled to the laser scanner and the processor is configured to execute instructions stored in memory to obtain laser scan data for the mobile robot at a current location in the environment. The processor is also configured to predict a future location of the mobile robot in the environment and to produce predicted laser scan data corresponding to the future location of the mobile robot in the environment. The processor is further configured to assess the predicted laser scan data relative to the mobile robot at the current location to determine whether a collision with an obstacle is predicted, as defined by independent claim <NUM>.

In the emdobiments one or more of the following features may be included. The laser scan data for the mobile robot at a current location may include raw data output from a laser scanner on the mobile robot. The raw data output from the laser scanner for the mobile robot at the current location may include laser scan points indicating points of reflection off of obstacles in the environment. The instruction stored in memory to predict the future location of the mobile robot in the environment may include estimating the future location of the mobile robot moving along an arc path after N seconds of travel from the current location using a commanded velocity of the mobile robot. N may be a number between <NUM> and <NUM>. The predicted laser scan data may include predicted laser scan points indicating predicted points of reflection off of obstacles in the environment from the future location of the mobile robot. The processor may be further configured to execute instructions stored in memory to represent the mobile robot as a polygon. The polygon representing the mobile robot may be an R-sided, convex polygon. When the processor executes instructions stored in memory to assess the predicted laser scan data relative to the mobile robot at the current location, the processor may be further configured to connect each of the laser scan points with a corresponding predicted laser scan point with an arc, thereby forming a plurality of arcs. Each arc of the plurality of arcs may comprise a plurality of line segments, L. When the processor executes instructions stored in memory to assess the predicted laser scan data relative to the mobile robot at the current location, the processor may be further configured to determine if any of the plurality of arcs intersect with a point on the polygon representing the mobile robot, which is indicative of a potential collision between the mobile robot and an obstacle. The processor may further be configured to execute instructions stored in memory to adjust a commanded velocity of the mobile robot using a scaling factor based at least in part on a depth of incursion into the polygon for at least one intersecting arc. The depth of incursion into the polygon for each intersecting arc may be determined based on the length of an arc length approximation for the intersecting arc. The processor may further be configured to execute instructions stored in memory to calculate a ratio for each intersecting arc, wherein the ratio is of a straight line distance from the current laser scan point on the obstacle to the point of intersection on the polygon relative to the arc length approximation and the minimum ratio is used as the scaling factor.

These and other features of the invention will be apparent from the following detailed description and the accompanying figures, in which:.

The disclosure is directed to autonomous mobile robot obstacle collision prediction and avoidance, which may be applied to any autonomous mobile robots or "AMRs" application. In order to provide some context for the invention, one application using AMRs for order fulfillment in a warehouse is described. In addition, a specific AMR implementation is described herein, but it is also only to provide context for the AMR obstacle collision prediction and avoidance according to this invention. For the avoidance of doubt, the invention described herein may be implemented in any AMR for any application.

Referring to <FIG>, a typical order-fulfillment warehouse <NUM> includes shelves <NUM> filled with the various items that could be included in an order. In operation, an incoming stream of orders <NUM> from warehouse management server <NUM> arrive at an order-server <NUM>. The order-server <NUM> may prioritize and group orders, among other things, for assignment to robots <NUM> during an induction process. As the robots are inducted by operators, at a processing station (e.g. station <NUM>), the orders <NUM> are assigned and communicated to robots <NUM> wirelessly for execution. It will be understood by those skilled in the art that order server <NUM> may be a separate server with a discrete software system configured to interoperate with the warehouse management system server <NUM> and warehouse management software or the order server functionality may be integrated into the warehouse management software and run on the warehouse management server <NUM>.

In a preferred embodiment, a robot <NUM>, shown in <FIG>, includes an autonomous wheeled base <NUM> having a laser-radar scanner <NUM>. The base <NUM> also features a transceiver (not shown) that enables the robot <NUM> to receive instructions from and transmit data to the order-server <NUM> and/or other robots, and a pair of digital optical cameras 24a and 24b. The robot base also includes an electrical charging port <NUM> for re-charging the batteries which power autonomous wheeled base <NUM>. The base <NUM> further features a processor (not shown) that receives data from the laser-radar and cameras 24a and 24b to capture information representative of the robot's environment. There is a memory (not shown) that operates with the processor to carry out various tasks associated with navigation within the warehouse <NUM>, as well as to navigate to fiducial marker <NUM> placed on shelves <NUM>, as shown in <FIG>. Fiducial marker <NUM> (e.g. a two-dimensional bar code) corresponds to bin/location of an item ordered. The navigation approach of this invention is described in detail below with respect to <FIG>. Fiducial markers are also used to identify charging stations according to an aspect of this invention and the navigation to such charging station fiducial markers is the same as the navigation to the bin/location of items ordered. Once the robots navigate to a charging station, a more precise navigation approach is used to dock the robot with the charging station and such a navigation approach is described below.

Referring again to <FIG>, base <NUM> includes an upper surface <NUM> where a tote or bin could be stored to carry items. There is also shown a coupling <NUM> that engages any one of a plurality of interchangeable armatures <NUM>, one of which is shown in <FIG>. The particular armature <NUM> in <FIG> features a tote-holder <NUM> (in this case a shelf) for carrying a tote <NUM> that receives items, and a tablet holder <NUM> (or laptop/other user input device) for supporting a tablet <NUM>. In some embodiments, the armature <NUM> supports one or more totes for carrying items. In other embodiments, the base <NUM> supports one or more totes for carrying received items. As used herein, the term "tote" includes, without limitation, cargo holders, bins, cages, shelves, rods from which items can be hung, caddies, crates, racks, stands, trestle, containers, boxes, canisters, vessels, and repositories.

Although a robot <NUM> excels at moving around the warehouse <NUM>, with current robot technology, it is not very good at quickly and efficiently picking items from a shelf and placing them in the tote <NUM> due to the technical difficulties associated with robotic manipulation of objects. A more efficient way of picking items is to use a local operator <NUM>, which is typically human, to carry out the task of physically removing an ordered item from a shelf <NUM> and placing it on robot <NUM>, for example, in tote <NUM>. The robot <NUM> communicates the order to the local operator <NUM> via the tablet <NUM> (or laptop/other user input device), which the local operator <NUM> can read, or by transmitting the order to a handheld device used by the local operator <NUM>.

Upon receiving an order <NUM> from the order server <NUM>, the robot <NUM> proceeds to a first warehouse location, e.g. as shown in <FIG>. It does so based on navigation software stored in the memory and carried out by the processor. The navigation software relies on data concerning the environment, as collected by the laser-radar <NUM>, an internal table in memory that identifies the fiducial identification ("ID") of fiducial marker <NUM> that corresponds to a location in the warehouse <NUM> where a particular item can be found, and the cameras 24a and 24b to navigate.

Upon reaching the correct location (pose), the robot <NUM> parks itself in front of a shelf <NUM> on which the item is stored and waits for a local operator <NUM> to retrieve the item from the shelf <NUM> and place it in tote <NUM>. If robot <NUM> has other items to retrieve it proceeds to those locations. The item(s) retrieved by robot <NUM> are then delivered to a processing station <NUM>, <FIG>, where they are packed and shipped. While processing station <NUM> has been described with regard to this figure as being capable of inducting and unloading/packing robots, it may be configured such that robots are either inducted or unloaded/packed at a station, i.e. they may be restricted to performing a single function.

It will be understood by those skilled in the art that each robot may be fulfilling one or more orders and each order may consist of one or more items. Typically, some form of route optimization software would be included to increase efficiency, but this is beyond the scope of this invention and is therefore not described herein.

In order to simplify the description of the invention, a single robot <NUM> and operator <NUM> are described. However, as is evident from <FIG>, a typical fulfillment operation includes many robots and operators working among each other in the warehouse to fill a continuous stream of orders.

The baseline navigation approach of this invention, as well as the semantic mapping of a SKU of an item to be retrieved to a fiducial ID/pose associated with a fiducial marker in the warehouse where the item is located, is described in detail below with respect to <FIG>.

Using one or more robots <NUM>, a map of the warehouse <NUM> must be created and the location of various fiducial markers dispersed throughout the warehouse must be determined. To do this, one or more of the robots <NUM> as they are navigating the warehouse they are building/updating a map 10a, <FIG>, utilizing its laser-radar <NUM> and simultaneous localization and mapping (SLAM), which is a computational problem of constructing or updating a map of an unknown environment. Popular SLAM approximate solution methods include the particle filter and extended Kalman filter. The SLAM GMapping approach is the preferred approach, but any suitable SLAM approach can be used.

Robot <NUM> utilizes its laser-radar <NUM> to create map 10a of warehouse <NUM> as robot <NUM> travels throughout the space identifying, open space <NUM>, walls <NUM>, objects <NUM>, and other static obstacles, such as shelf <NUM>, in the space, based on the reflections it receives as the laser-radar scans the environment.

While constructing the map 10a (or updating it thereafter), one or more robots <NUM> navigates through warehouse <NUM> using camera <NUM> to scan the environment to locate fiducial markers (two-dimensional bar codes) dispersed throughout the warehouse on shelves proximate bins, such as <NUM> and <NUM>, <FIG>, in which items are stored. Robots <NUM> use a known starting point or origin for reference, such as origin <NUM>. When a fiducial marker, such as fiducial marker <NUM>, <FIG> and <FIG>, is located by robot <NUM> using its camera <NUM>, the location in the warehouse relative to origin <NUM> is determined.

By the use of wheel encoders and heading sensors, vector <NUM>, and the robot's position in the warehouse <NUM> can be determined. Using the captured image of a fiducial marker/two-dimensional barcode and its known size, robot <NUM> can determine the orientation with respect to and distance from the robot of the fiducial marker/two-dimensional barcode, vector <NUM>. With vectors <NUM> and <NUM> known, vector <NUM>, between origin <NUM> and fiducial marker <NUM>, can be determined. From vector <NUM> and the determined orientation of the fiducial marker/two-dimensional barcode relative to robot <NUM>, the pose (position and orientation) defined by a quaternion (x, y, z, ω) for fiducial marker <NUM> can be determined.

Flow chart <NUM>, <FIG>, describing the fiducial marker location process is described. This is performed in an initial mapping mode and as robot <NUM> encounters new fiducial markers in the warehouse while performing picking, placing and/or other tasks. In step <NUM>, robot <NUM> using camera <NUM> captures an image and in step <NUM> searches for fiducial markers within the captured images. In step <NUM>, if a fiducial marker is found in the image (step <NUM>) it is determined if the fiducial marker is already stored in fiducial table <NUM>, <FIG>, which is located in memory <NUM> of robot <NUM>. If the fiducial information is stored in memory already, the flow chart returns to step <NUM> to capture another image. If it is not in memory, the pose is determined according to the process described above and in step <NUM>, it is added to fiducial to pose lookup table <NUM>.

In look-up table <NUM>, which may be stored in the memory of each robot, there are included for each fiducial marker a fiducial identification, <NUM>, <NUM>, <NUM>, etc., and a pose for the fiducial marker/bar code associated with each fiducial identification. The pose consists of the x,y,z coordinates in the warehouse along with the orientation or the quaternion (x,y,z, ω).

In another look-up Table <NUM>, <FIG>, which may also be stored in the memory of each robot, is a listing of bin locations (e.g. 402a-f) within warehouse <NUM>, which are correlated to particular fiducial ID's <NUM>, e.g. number "<NUM>". The bin locations, in this example, consist of seven alpha-numeric characters. The first six characters (e.g. L01001) pertain to the shelf location within the warehouse and the last character (e.g. A-F) identifies the particular bin at the shelf location. In this example, there are six different bin locations associated with fiducial ID "<NUM>". There may be one or more bins associated with each fiducial ID/marker.

The alpha-numeric bin locations are understandable to humans, e.g. operator <NUM>, <FIG>, as corresponding to a physical location in the warehouse <NUM> where items are stored. However, they do not have meaning to robot <NUM>. By mapping the locations to fiducial ID's, Robot <NUM> can determine the pose of the fiducial ID using the information in table <NUM>, <FIG>, and then navigate to the pose, as described herein.

The order fulfillment process according to this invention is depicted in flow chart <NUM>, <FIG>. In step <NUM>, from warehouse management system <NUM>, order server <NUM> obtains an order, which may consist of one or more items to be retrieved. It should be noted that the order assignment process is fairly complex and goes beyond the scope of this disclosure. One such order assignment process is described in commonly owned <CIT>, which is incorporated herein by reference in its entirety. It should also be noted that robots may have tote arrays which allow a single robot to execute multiple orders, one per bin or compartment. Examples of such tote arrays are described in <CIT>.

Continuing to refer to <FIG>, in step <NUM> the SKU number(s) of the items is/are determined by the warehouse management system <NUM>, and from the SKU number(s), the bin location(s) is/are determined in step <NUM>. A list of bin locations for the order is then transmitted to robot <NUM>. In step <NUM>, robot <NUM> correlates the bin locations to fiducial ID's and from the fiducial ID's, the pose of each fiducial ID is obtained in step <NUM>. In step <NUM> the robot <NUM> navigates to the pose as shown in <FIG>, where an operator can pick the item to be retrieved from the appropriate bin and place it on the robot.

Item specific information, such as SKU number and bin location, obtained by the warehouse management system <NUM>/order server <NUM>, can be transmitted to tablet <NUM> on robot <NUM> so that the operator <NUM> can be informed of the particular items to be retrieved when the robot arrives at each fiducial marker location.

With the SLAM map and the pose of the fiducial ID's known, robot <NUM> can readily navigate to any one of the fiducial ID's using various robot navigation techniques. The preferred approach involves setting an initial route to the fiducial marker pose given the knowledge of the open space <NUM> in the warehouse <NUM> and the walls <NUM>, shelves (such as shelf <NUM>) and other obstacles <NUM>. As the robot begins to traverse the warehouse using its laser radar <NUM>, it determines if there are any obstacles in its path, either fixed or dynamic, such as other robots <NUM> and/or operators <NUM>, and iteratively updates its path to the pose of the fiducial marker. The robot re-plans its route about once every <NUM> milliseconds, constantly searching for the most efficient and effective path while avoiding obstacles.

With the product SKU/fiducial ID to fiducial pose mapping technique combined with the SLAM navigation technique both described herein, robots <NUM> are able to very efficiently and effectively navigate the warehouse space without having to use more complex navigation approaches typically used which involve grid lines and intermediate fiducial markers to determine location within the warehouse.

<FIG> illustrates a system view of one embodiment of robot <NUM> for use in the above described order fulfillment warehouse application. Robot system <NUM> comprises data processor <NUM>, data storage <NUM>, processing modules <NUM>, and sensor support modules <NUM>. Processing modules <NUM> may include path planning module <NUM>, drive control module <NUM>, map processing module <NUM>, localization module <NUM>, and state estimation module <NUM>. Sensor support modules <NUM> may include range sensor module <NUM>, drive train/wheel encoder module <NUM>, and inertial sensor module <NUM>.

Data processor <NUM>, processing modules <NUM> and sensor support modules <NUM> are capable of communicating with any of the components, devices or modules herein shown or described for robot system <NUM>. A transceiver module <NUM> may be included to transmit and receive data. Transceiver module <NUM> may transmit and receive data and information to and from a supervisor system or to and from one or other robots. Transmitting and receiving data may include map data, path data, search data, sensor data, location and orientation data, velocity data, and processing module instructions or code, robot parameter and environment settings, and other data necessary to the operation of robot system <NUM>.

In some embodiments, range sensor module <NUM> may comprise one or more of a scanning laser, radar, laser range finder, range finder, ultrasonic obstacle detector, a stereo vision system, a monocular vision system, a camera, and an imaging unit. Range sensor module <NUM> may scan an environment around the robot to determine a location of one or more obstacles with respect to the robot. In a preferred embodiment, drive train/wheel encoders <NUM> comprises one or more sensors for encoding wheel position and an actuator for controlling the position of one or more wheels (e.g., ground engaging wheels). Robot system <NUM> may also include a ground speed sensor comprising a speedometer or radar-based sensor or a rotational velocity sensor. The rotational velocity sensor may comprise the combination of an accelerometer and an integrator. The rotational velocity sensor may provide an observed rotational velocity for the data processor <NUM>, or any module thereof.

In some embodiments, sensor support modules <NUM> may provide translational data, position data, rotation data, level data, inertial data, and heading data, including historical data of instantaneous measures of velocity, translation, position, rotation, level, heading, and inertial data over time. The translational or rotational velocity may be detected with reference to one or more fixed reference points or stationary objects in the robot environment. Translational velocity may be expressed as an absolute speed in a direction or as a first derivative of robot position versus time. Rotational velocity may be expressed as a speed in angular units or as the first derivative of the angular position versus time. Translational and rotational velocity may be expressed with respect to an origin <NUM>,<NUM> (e.g. <FIG>, <NUM>) and bearing of <NUM>-degrees relative to an absolute or relative coordinate system. Processing modules <NUM> may use the observed translational velocity (or position versus time measurements) combined with detected rotational velocity to estimate observed rotational velocity of the robot.

In other embodiments, modules not shown in <FIG> may comprise a steering system, braking system, and propulsion system. The braking system may comprise a hydraulic braking system, an electro-hydraulic braking system, an electro-mechanical braking system, an electromechanical actuator, an electrical braking system, a brake-by-wire braking system, or another braking system in communication with drive control <NUM>. The propulsion system may comprise an electric motor, a drive motor, an alternating current motor, an induction motor, a permanent magnet motor, a direct current motor, or another suitable motor for propelling a robot.

The propulsion system may comprise a motor controller (e.g., an inverter, chopper, wave generator, a multiphase controller, variable frequency oscillator, variable current supply, or variable voltage supply) for controlling at least one of the velocity, torque, and direction of rotation of the motor shaft of the electric motor. Preferably, drive control <NUM> and propulsion system (not shown) is a differential drive (DD) control and propulsion system. In a DD control system robot control is non-holonomic (NH), characterized by constraints on the achievable incremental path given a desired translational and angular velocity. Drive control <NUM> in communication with propulsion system may actuate incremental movement of the robot by converting one or more instantaneous velocities determined by path planning module <NUM> or data processor <NUM>.

One skilled in the art would recognize other systems and techniques for robot processing, data storage, sensing, control and propulsion may be employed without loss of applicability of the present invention described herein.

Navigation by an autonomous or semi-autonomous robot requires some form of spatial model of the robot's environment. Spatial models may be represented by bitmaps, object maps, landmark maps, and other forms of two- and three-dimensional digital representations. A spatial model of a warehouse facility, as shown in <FIG> for example, may represent a warehouse and obstacles within such as walls, ceilings, roof supports, windows and doors, shelving and storage bins. Obstacles may be stationary or moving, for example, such as other robots or machinery operating within the warehouse, or relatively fixed but changing, such as temporary partitions, pallets, shelves and bins as warehouse items are stocked, picked and replenished.

Spatial models in a warehouse facility may also represent target locations such as a shelf or bin marked with a fiducial to which a robot may be directed to pick product or to perform some other task, or to a temporary holding location or to the location of a charging station. For example, <FIG> depicts the navigation of robot <NUM> from a starting location <NUM> to intermediate locations <NUM>,<NUM> to destination or target location <NUM> along its path <NUM>,<NUM>,<NUM>. Here the spatial model captures features of the environment through which the robot must navigate, including features of a structure at a destination <NUM> which may be a shelf or bin or a robot charger station.

The spatial model most commonly used for robot navigation is a bitmap of an area or facility. <FIG>, for example, depicts a portion of a two-dimensional map for the areas shown in the spatial model of <FIG>. Map <NUM> may be represented by bitmaps having pixel values in a binary range <NUM>,<NUM>, representing black or white, or by a range of pixel values, for example <NUM>-<NUM> representing a gray-scale range of black (<NUM>) to white (<NUM>) or by color ranges, the ranges of which may depict uncertainties in whether a feature is present at the location represented by the pixel values. As shown in <FIG>, for example, pixels in black (<NUM>) represent obstacles, white (<NUM>) pixels represent free space, and areas of solid gray (some value between <NUM> and <NUM>, typically <NUM>) represent unknown areas.

The scale and granularity of map <NUM> shown in the <FIG> may be any such scale and dimensions as is suitable for the range and detail of the environment. For example, in some embodiments of the present invention, each pixel in the map may represent <NUM> square centimeters (cm<NUM>). In other embodiments each pixel may represent a range from <NUM><NUM> to <NUM><NUM>. However, the spatial resolution of a map for use with the present invention may be larger or smaller without loss of generality or benefit to the application of its methods.

As depicted in <FIG>, map <NUM> may be used by the robot to determine its pose within the environment and to plan and control its movements along path <NUM>,<NUM>,<NUM>, while avoiding obstacles. Such maps may be "local maps", representing spatial features in the immediate vicinity of the robot or target location, or "global maps", representing features of an area or facility encompassing the operating range of one or more robots. Maps may be provided to a robot from an external supervisory system or a robot may construct its map using onboard range finding and location sensors. One or more robots may cooperatively map a shared environment, the resulting map further enhanced as the robots navigate, collect, and share information about the environment.

In some embodiments the supervisory system may comprise a central server performing supervision of a plurality of robots in a manufacturing warehouse or other facility, or the supervisory system may comprise a distributed supervisory system consisting of one or more servers operating within or without the facility either fully remotely or partially without loss of generality in the application of the methods and systems herein described. The supervisory system may include a server or servers having at least a computer processor and a memory for executing a supervisory system and may further include one or more transceivers for communicating information to one or more robots operating in the warehouse or other facility. Supervisory systems may be hosted on computer servers or may be hosted in the cloud and communicating with the local robots via a local transceiver configured to receive and transmit messages to and from the robots and the supervisory system over wired and/or wireless communications media including over the Internet.

One skilled in the art would recognize that robotic mapping for the purposes of the present invention could be performed using methods known in the art without loss of generality. Further discussion of methods for robotic mapping can be found in<NPL>.

A robot outfitted with sensors, as described above, can use its sensors for localization as well as contribute to the building and maintenance of the map of its environment. Sensors used for map building and localization may include light detection and ranging ("LIDAR" or "laser scanning" or "laser-radar") sensors. Laser-radar scanners measure the range and distance to objects in a horizontal plane with a series of discrete, angular sweeps of the robot's local environment. A range finding sensor acquires a set of measurements, a "scan" taken at discrete angular increments of preferably one-quarter (<NUM>) degree increments over a <NUM>-degree arc or a greater or lesser degree arc, or a full <NUM>-degree arc about the robot. A laser-radar scan, for example, may be a set of measurements representing the return time and strength of a laser signal, each measurement at a discrete angular increment indicating a potential obstacle at a distance from the robot's current position.

For illustration, as shown in <FIG>, a laser-radar scan taken at location <NUM> can be represented graphically as a two-dimensional bitmap <NUM>. Scan <NUM> as shown depicts an approximately <NUM>-degree horizontal arc facing in the direction of travel of the robot at intermediate pose <NUM>. Individual laser-radar measurements <NUM>, depicted by directional broken lines, detect obstacles in the robot's environment at structures represented by pixels at <NUM>, <NUM>, <NUM>, and <NUM> in scan <NUM>. In some embodiments, scans of straight walls may be "filled in" in scan <NUM> where a connected geographic structure <NUM> may be known from other data or discernable by alignment of point cloud pixels.

Other forms of range finding sensors include sonar, radar, and tactile sensor without departing from the scope of the invention. Examples of commercially available range finding and location and orientation sensors suitable for use with the present invention include, but are not limited to, the Hokuyo UST-10LX, the SICK LMS <NUM>, and the Velodyne VLP-<NUM>. A robot may have one or more range or location sensors of a particular type, or it may have sensors of different types, the combination of sensor types producing measurements that collectively map its environment. Further discussion of methods of robotic mapping by LIDAR and other scanners can be found in <NPL>.

In order for a mobile robot to avoid obstacles, such as walls, shelving, people, other robots, among other things, it must perceive the obstacles with its laser scanner and then mark its observations in a 2D costmap (grid). From there, the robot generates a plan and executes a control trajectory to avoid the obstacles. Problematically, capturing and processing such a large amount of data, while the robot is navigating the environment, may result in a control cycle time for the mobile robot which is not quick enough to generate a control trajectory to avoid the obstacle.

The raw laser scan data output from laser-radar scanner <NUM> of <FIG>, for example, may be generated at <NUM>, which is far faster than the standard control cycle of the robot. This laser scan data and the commanded velocity of the robot may be used according to an aspect of this invention as a secondary means of collision detection and avoidance outside the primary sense/plan/act loop that guides robot navigation. More specifically, the robot uses the raw laser scan data, its current velocity, and the commanded velocity to make a prediction about where the robot will be after a predetermined amount of time, e.g. after N seconds, wherein N is configurable. N may be an integer or a real valued number between, for example, <NUM> and a maximum value of a double-precision floating point number. N may have a typical value of between <NUM> and <NUM> seconds, but it ultimately depends on the maximum travel velocity of the robot. N may be adjusted dynamically as the robot velocity changes over time. Using a predicted pose, the robot may also predict what the laser scan will look like at that moment.

Referring to <FIG>, <FIG> robot <NUM> is shown travelling along an arc path <NUM> towards two intersecting wall structures <NUM> and <NUM>, represented by thick black lines. Dot <NUM> on robot <NUM> indicates the front of the robot. The laser scanner of robot <NUM> reflects off the wall structures <NUM> and <NUM>, at a plurality of points producing the laser scan <NUM> indicated by a plurality of points in red, including e.g. laser scan point <NUM>. In <FIG>, the predicted position of robot <NUM> after N seconds, as it continues to travel along that arc path <NUM> at the commanded velocity, is represented by robot 800a shown in lighter shading closer to both of the wall structures <NUM> and <NUM>. In <FIG>, there is shown a representation of the laser scan 808a from the predicted position of robot 808a. In this predicted position the predicted laser scan points in blue, including e.g. laser scan point 809a are depicted.

In <FIG>, the predicted laser scan 808a from <FIG> is superimposed on the image showing robot <NUM> in its original location (<FIG>) relative to wall structures <NUM> and <NUM> and depicting the laser scan <NUM> from the original position. This depicts what the robot's laser scan will look like in N seconds, but relative to the current position of the robot. The current laser scan data and the predicted laser scan data can be used to determine if a collision with an obstacle is likely and from this information determine corrective action that can be taken to avoid the collision. However, this may be done at a much faster rate than could be by the robot's primary control system, as mentioned above.

In <FIG>, the current position of the robot is shown to be at the predicted position of <FIG>, 800a. In other words, after N seconds the robot has traveled from its then current position in <FIG> to its predicted position in <FIG>. In this position, robot <NUM> is much closer to wall structure <NUM> and is continuing on a trajectory <NUM> toward wall structure <NUM>. The current laser scan data, indicated by a plurality of points in red, including e.g. laser scan point <NUM> are shown. The predicted position of robot <NUM> after N seconds, as it continues to travel along that arc path <NUM> at the commanded velocity, is not shown in this figure, but the predicted laser scan points <NUM> in blue, including e.g. laser scan point <NUM> (inside the robot <NUM>) are depicted. As described in further detail below with regard to <FIG> and <FIG>, when the predicted laser scan points are within the robot, as is the case in <FIG>, a collision, in this case with the wall structure <NUM>, is predicted and corrective action must be taken to avoid a collision.

Since this algorithm may be applied to any type of AMR of any shape, the algorithm represents the robot as a polygon. This generalizes well to all robot morphologies: for rectangular robots, representation of the robot's footprint by a polygon is obvious. For circular bases, the robot footprint may be approximated with an R-sided convex polygon, which can be seen in <FIG>, where robot <NUM> is shown represented by polygon <NUM>. In this example, robot <NUM> is shown surrounded by wall structures <NUM>, <NUM>, and <NUM> off of which are reflected the laser scans of robot <NUM> at its current location.

The current laser scans are 904a, 906a, and 908a, which are aligned with the wall structures <NUM>, <NUM>, and <NUM>. The predicted position of robot <NUM> traveling along arc path <NUM> at the current velocity is determined (not shown) and a predicted laser scan from the predicted location is determined. The predicted laser scan at the predicted location is superimposed on the image relative to robot <NUM> in its original location. The predicted laser scans 904b, 906b, and 908b are depicted relative to current laser scans are 904a, 906a, and 908a.

The algorithm next draws an arc between each current laser scan point of laser scan 904a, 906a, 908a and its respective predicted laser scan point of predicted laser scans 904b, 906b, 908b to form a plurality of arcs 904c, 906c, 908c. The arcs are approximated by a series of L line segments, which can be more clearly seen in <FIG>, where a polygon <NUM> represents a robot and laser scan segment <NUM>, consisting of laser scan points 1002a-1002d represent the laser scan points reflecting off of an object from the current location of the robot. Predicted laser scan segment <NUM>, consisting of laser scan points 1004a-1004d represent the laser scan points reflecting off of an object from the predicted location of the robot represented by polygon <NUM> in N seconds, which is determined, as described above, based on the trajectory and current velocity.

If, as is the case shown in <FIG>, one or more of the plurality of arcs between the current laser scan and the predicted laser scan penetrate(s) the polygon (e.g. <NUM>), representing the robot at its current location, this indicates that, at the current velocity and trajectory, the robot will collide with the obstacle producing the laser scan points being reflected within N seconds or less. With the information that a collision is predicted, the algorithm, according to an aspect of this invention, may adjust the commanded velocity of the mobile robot. It may do this on the basis of scaling factor or a speed factor based on the depth of incursion into the polygon for one or more intersecting arcs.

The scaling/speed factor is determined by performing an intersection test for each laser scan arc and the polygon that represents the robot. If an arc intersects the robot, a "depth" of incursion into the polygon is used to compute the scaling/speed factor. The depth of the incursion for a given arc may be the distance from the predicted scan point, when the scan point is located in the polygon, to the intersection point in the polygon, i.e. the entry point, as is shown in <FIG>. Although not shown, it is possible that the predicted scan point for a given arc may be located outside of the polygon behind the robot and the arc will pass entirely through the polygon representing the robot. In that case the depth of incursion would be measured from the entry point, i.e. where the arc first intersects the polygon, to the exit point, i.e. where the arc exits the polygon. The depth of incursion determination may be simplified and normalized using arc approximations, as described below.

Continuing to refer to <FIG>, the arcs are represented by arc approximations, such as approximation <NUM>, which consists of arc approximating line segments 1006a-1006d. The arc approximating line segments are depicted connecting current laser scan points 1002a-1002d to predicted laser scan points 1004a-1004d. Each arc approximating line segment is formed of equal length line segments. As shown, arc approximating line segment 1006a, comprises two equal length line segments 1008a and 1010a. Each of the other arc approximating line segments 1006b-1006d are similarly formed of equal length segments <NUM> and <NUM>. As depicted, the line segments 1008a-1008d of each arc approximating line segment 1006a-1006d intersect polygon <NUM> at intersecting points 1012a-1012d, respectively.

In order to calculate the scaling/speed factor two quantities may be defined: d is the straight-line distance from each current laser scan point to the point of intersection of polygon <NUM>, and a is the length of a single segment in the arc approximation. Straight-line distance d and arc length segment length a for each laser scan point pair (<NUM> and <NUM>) are determined: d<NUM> to d<NUM> and a<NUM> to a<NUM>. The length of one entire arc approximation is given by the following equation: <MAT> Where L is the number of equal length line segments in an arc approximation. Note that the value of A will be different for each arc approximation. The final scaling/speed factor, f, calculation is given by determining the minimum ratio of d/A across the set, S, of all arc approximations as follows: <MAT>.

The final scaling/speed factor f may be limited to be in the range [<NUM>, <NUM>] and used to scale the final velocity command, Vc, of the robot, i.e. f *Vc. A scaling/speed actor of <NUM> causes the velocity commanded to also be <NUM>, while a scaling/speed factor of <NUM> maintains the full velocity commanded. The scaling factor maintains the commanded motion arc, that is, the ratio of linear and angular commanded velocity is maintained but scaled based on f. With a smaller value for d, indicating that the robot is in close proximity to the object, and a larger value for A, indicating that the predicted laser scan points will be located deeper within or even beyond the polygon (i.e. a depth of incursion), a small scaling/speed factor will result. The smaller the scaling/speed factor, the lower the scaled commanded velocity.

It should be noted that in order to achieve a scaling/speed factor of <NUM>, which would cause the robot to stop before colliding with an object, a safety buffer, i.e. a minimum distance to an object, is defined and the safety buffer value is subtracted from the determined minimum value d. When the minimum value d is equal to or less than the safety buffer value, f will be equal to zero and when applied to the final velocity commanded, it will result in a zero velocity causing the robot to stop.

Note that the straight-line distance d is always less than or equal to the along-the-segment distance to the intersection point. This means that f will always produce a speed factor that is less than the speed factor would be if d were computed along the line segments a. As this algorithm is designed for safety, this is a preferred result. However, for efficiency, f, may be determined by computing d as the total length along the line segments a, but there will be less margin for error. Or, the minimum value for d may be determined from the set of arcs and then the minimum value for d may be normalized by the arc length approximation A to get the final speed factor f.

A visualization of a robot represented by polygon 1000a in an environment <NUM> is shown in <FIG>. In it, the robot/polygon <NUM> is shown in close proximity to wall structure <NUM> and on a course to collide with it. The robot is being commanded by its primary control system to drive forward and, due to the long cycle time, it could collide with the wall before the primary control system could take corrective action. However, with the algorithm described herein, the current laser scan <NUM>, the predicted scan <NUM>, and the arc segments <NUM> connecting the current laser scan and predicted laser scan, depict that the predicted laser scan <NUM> is intersecting the polygon 1000a representing the robot. This indicates that a collision is imminent and the algorithm would calculate a speed factor, f, to scale final velocity command of the robot by f. In this case, f may be determined to be <NUM>, which cause the robot to stop short of the wall, thus preventing a collision.

The above described robot and overall robot system are implemented using one or more computing devices. <FIG> is a block diagram of an exemplary computing device <NUM> such as can be used, or portions thereof, in accordance with various embodiments as described above with reference to <FIG>. The computing device <NUM> includes one or more non-transitory computer-readable media for storing one or more computer-executable instructions or software for implementing exemplary embodiments. The non-transitory computer-readable media can include, but are not limited to, one or more types of hardware memory, non-transitory tangible media (for example, one or more magnetic storage disks, one or more optical disks, one or more flash drives), and the like. For example, memory <NUM> included in the computing device <NUM> can store computer-readable and computer-executable instructions or software for performing the operations disclosed herein. For example, the memory can store software application <NUM> which is programmed to perform various of the disclosed operations as discussed with respect to <FIG>. The computing device <NUM> can also include configurable and/or programmable processor <NUM> and associated core <NUM>, and optionally, one or more additional configurable and/or programmable processing devices, e.g., processor(s) <NUM>' and associated core (s) <NUM>' (for example, in the case of computational devices having multiple processors/cores), for executing computer-readable and computer-executable instructions or software stored in the memory <NUM> and other programs for controlling system hardware. Processor <NUM> and processor(s) <NUM>' can each be a single core processor or multiple core (<NUM> and <NUM>') processor.

Virtualization can be employed in the computing device <NUM> so that infrastructure and resources in the computing device can be shared dynamically. A virtual machine <NUM> can be provided to handle a process running on multiple processors so that the process appears to be using only one computing resource rather than multiple computing resources. Multiple virtual machines can also be used with one processor.

Memory <NUM> can include a computational device memory or random access memory, such as but not limited to DRAM, SRAM, EDO RAM, and the like. Memory <NUM> can include other types of memory as well, or combinations thereof.

A user can interact with the computing device <NUM> through a visual display device <NUM>, 111A-D, such as a computer monitor, which can display one or more user interfaces <NUM> that can be provided in accordance with exemplary embodiments. The computing device <NUM> can include other I/O devices for receiving input from a user, for example, a keyboard or any suitable multipoint touch interface <NUM>, a pointing device <NUM> (e.g., a mouse). The keyboard <NUM> and the pointing device <NUM> can be coupled to the visual display device <NUM>. The computing device <NUM> can include other suitable conventional I/O peripherals.

The computing device <NUM> can also include one or more storage devices <NUM>, such as but not limited to a hard-drive, CD-ROM, or other computer readable media, for storing data and computer-readable instructions and/or software that perform operations disclosed herein. Exemplary storage device <NUM> can also store one or more databases for storing any suitable information required to implement exemplary embodiments. The databases can be updated manually or automatically at any suitable time to add, delete, and/or update one or more items in the databases.

The computing device <NUM> can include a network interface <NUM> configured to interface via one or more network devices <NUM> with one or more networks, for example, Local Area Network (LAN), Wide Area Network (WAN) or the Internet through a variety of connections including, but not limited to, standard telephone lines, LAN or WAN links (for example, <NUM>, T1, T3, <NUM> kb, X. <NUM>), broadband connections (for example, ISDN, Frame Relay, ATM), wireless connections, controller area network (CAN), or some combination of any or all of the above. The network interface <NUM> can include a built-in network adapter, network interface card, PCMCIA network card, card bus network adapter, wireless network adapter, USB network adapter, modem or any other device suitable for interfacing the computing device <NUM> to any type of network capable of communication and performing the operations described herein. Moreover, the computing device <NUM> can be any computational device, such as a workstation, desktop computer, server, laptop, handheld computer, tablet computer, or other form of computing or telecommunications device that is capable of communication and that has sufficient processor power and memory capacity to perform the operations described herein.

The computing device <NUM> can run any operating system <NUM>, such as any of the versions of the Microsoft® Windows® operating systems (Microsoft, Redmond, Wash. ), the different releases of the Unix and Linux operating systems, any version of the MAC OS® (Apple, Inc. , Cupertino, Calif. ) operating system for Macintosh computers, any embedded operating system, any real-time operating system, any open source operating system, any proprietary operating system, or any other operating system capable of running on the computing device and performing the operations described herein. In exemplary embodiments, the operating system <NUM> can be run in native mode or emulated mode. In an exemplary embodiment, the operating system <NUM> can be run on one or more cloud machine instances.

<FIG> is an example computational device block diagram of certain distributed embodiments. Although <FIG>, and portions of the exemplary discussion above, make reference to a warehouse management system <NUM>, order-server <NUM>, or robot tracking server <NUM> each operating on an individual or common computing device, one will recognize that any one of the warehouse management system <NUM>, the order-server <NUM>, or the robot tracking server <NUM> may instead be distributed across a network <NUM> in separate server systems 1301a-d and possibly in user systems, such as kiosk, desktop computer device <NUM>, or mobile computer device <NUM>. For example, the order-server <NUM> may be distributed amongst the tablets <NUM> of the robots <NUM>. In some distributed systems, modules of any one or more of the warehouse management system software and/or the order-server software can be separately located on server systems 1301a-d and can be in communication with one another across the network <NUM>.

Claim 1:
A method for predicting a collision between a mobile robot (<NUM>, <NUM>) and an obstacle in an environment, comprising:
generating a control trajectory for the mobile robot (<NUM>, <NUM>) for each of a plurality of control cycles; and
predicting, between each of the plurality of control cycles, a collision of the mobile robot (<NUM>, <NUM>) and an obstacle, wherein the step of predicting includes:
obtaining laser scan data for the mobile robot (<NUM>, <NUM>) at a current location in the environment, wherein the laser scan data includes raw data output from a laser scanner and wherein the raw data output from the laser scanner includes laser scan points indicating points of reflection off of obstacles in the environment;
representing the mobile robot (<NUM>, <NUM>) at the current location as a polygon;
predicting a future location of the mobile robot (<NUM>, <NUM>) in the environment;
producing predicted laser scan data corresponding to the future location of the mobile robot (<NUM>, <NUM>) in the environment, wherein the predicted laser scan data includes predicted laser scan points indicating predicted points of reflection off of obstacles in the environment from the future location of the mobile robot (<NUM>, <NUM>); and
assessing the predicted laser scan data relative to the mobile robot (<NUM>, <NUM>) at the current location to determine whether a collision with the obstacle is predicted, wherein assessing the predicted laser scan data includes connecting each of the laser scan points with a corresponding predicted laser scan point with an arc, thereby forming a plurality of arcs, and determining if any of the plurality of arcs penetrate the polygon representing the mobile robot (<NUM>, <NUM>) at the current location.