System for determining position of an object

Described are systems and techniques for determining a position of one or more people within a physical environment, such as an aisle in a fulfillment center. In some instances, the aisle is instrumented with a plurality of radio frequency receivers (RFRXs), active infrared transmitter-receiver pairs (AIRTRPs), and passive infrared (PIR) proximity sensors. A radio frequency-emitting tag carried by the user is detected by the RFRX to determine an identity and approximate position along the length of the aisle. Data indicating obscuration of beams from one or more of the AIRTRPs provides further refinement as to position along the length of the aisle. Data from the PIR provides disambiguation as to which side of the aisle the user is on. Accordingly, the user may be identified and precisely positioned in the aisle.

BACKGROUND

Retailers, wholesalers, and other product distributors typically maintain an inventory of various items that may be ordered, purchased, leased, borrowed, rented, viewed, etc. by clients or customers. For example, an e-commerce website may maintain inventory in a fulfillment center. When a customer orders an item, the item is picked from inventory, routed to a packing station, packed and shipped to the customer. Likewise, physical stores maintain inventory in customer accessible areas (e.g., shopping area) and customers can pick items from inventory and take them to a cashier for purchase, rental, and so forth. Many of those physical stores also maintain inventory in a storage area, fulfillment center, or other facility that can be used to replenish inventory located in the shopping areas or to satisfy orders for items that are placed through other channels (e.g., e-commerce). Other examples of entities that maintain facilities holding inventory include libraries, museums, rental centers and the like. Users may move about the respective facilities such as the fulfillment centers, libraries, museums, rental centers, and the like. It is desirable to track the position of the users within the facility.

DETAILED DESCRIPTION

This disclosure describes systems and techniques for determining a position of an object in a facility. The object may comprise a user, a robot, a tote, and so forth. The object may move or be moved from one position to another within the facility. For example, a user may walk through the facility to gather inventory items. Similarly, a robot may move items throughout the facility.

As used in this disclosure, position may be a relative position, or an absolute position with respect to an external reference point. For example, the relative position may comprise an indication of a location within a particular aisle, such as five meters from a first end of the aisle and on the left. In comparison, an absolute position may specify coordinates of a particular latitude and longitude with regard to a geographic datum.

Various services or functionalities within the facility may use the position of the object. For example, an information prompt or indicator may be presented to the user based on the position in the facility. In another example, the position may be used to guide a robot through the facility. In yet another example, the position information may be used to direct the user from one position to another within the facility.

The facility may include one or more aisles, sections, pods, and so forth. For convenience, and not by way of a limitation, this disclosure uses the term “aisles” to denote a portion of the facility. The facility, or portions thereof, may be segregated for positioning purposes into cells. For example, and aisle may be divided into a two dimensional grid which includes rows extending across the aisle from left to right and columns extending from one end of the aisle to the other. In some implementations indications of these cells may be presented to users by way of visual indicia in the form of lines, text, and so forth painted or projected onto the floor. In other implementations, the placement of the cells may be invisible to the users of the facility. The disclosure discusses the cells or positions as a rectilinear grid for ease of illustration and not by way of limitation. In other implementations cells of other shapes may be used. For example, the cells may comprise hexagons arranged in a honeycomb fashion, or other polygons in an area-filling pattern.

Inventory locations may be arranged on one or both sides of the aisles. The inventory locations may include one or more of shelves, racks, cases, cabinets, bins, floor locations, or other suitable storage mechanisms. One or more items comprising physical goods may be stored in the inventory locations. Objects may move along the aisles to access the inventory locations. The objects may include, but are not limited to, people, robots, totes, and so forth. For example, a user or robot may move down the aisle to a particular inventory location to place or retrieve an item. In some implementations the relative position in the facility may be expressed in terms of, or associated with, an inventory location. For example, a relative location may be expressed in terms of “aisle and rack”, such as the user is located in aisle five, in front of rack alpha.

The facility may include, or have access to, an inventory management system. The inventory management system may be configured to maintain information about items within the facility. For example, an inventory management system may maintain information indicative of quantities of items at various inventory locations.

The facility includes, or has access to, an object positioning system. The object positioning system is configured to use input from one or more sensors to determine a position of one or more objects within the facility. As described above, the position may be relative or absolute. In addition to position, the object positioning system may be configured to determine and identify the object. For example, the object positioning system may determine a particular user or a particular robot and the position within the facility. In some implementations, the object positioning system may operate in conjunction with the inventory management system. For example, the object positioning system may provide object position data to the inventory management system to track which user is adding or removing inventory from an inventory location. The object position data may include an identity and a position of the object at a specified time or over a time series, providing a track of movement. In some implementations the object position data may include vector information, such as a direction and speed of the object.

The object positioning system determines the object position data using data acquired from one or more sensors. The one or more sensors provide data about objects which may be present within, or proximate to, the aisle. The sensors may include, but are not limited to, radio frequency (RF) receivers, active infrared (IR) transmitter and IR receiver pairs, and passive IR sensors. Other sensors may be used, such as cameras, microbolometers, weight sensors, motion sensors such as accelerometers or gyroscopes, and so forth.

A tag may be associated with the object. The tag may be affixed to, integral with, or carried by, the object. For example, the user may carry a key fob containing the tag. In another example, the tag may be incorporated in a tote. The tag is configured to emit an RF signal. In one implementation, the tag may be a radio frequency identification (RFID) tag configured to emit the RF signal upon activation by an external signal. In another implementation, the tag may comprise a Bluetooth transmitter.

The RF receivers are configured to receive the RF signal emitted by the tag. The RF receivers are configured to provide RF data, which may include an indication of relative signal strength, data transmitted by the signal, and so forth. For example, the RF receivers may provide received signal strength information (RSSI) for the RF signals received. Based at least in part on the RSSI, a distance between the RF receiver and the tag may be determined. Given a known location of the RF receiver with respect to the facility, receiver sensitivity, transmitter output, antenna patterns, and so forth, a set of cells within which the tag may be positioned is determinable. For example, the tag may be determined to be within 1.5 meters of the RF receiver and thus occupies one of the cells within an area described by this distance.

The active infrared (IR) transmitter and IR receiver pairs may be configured to provide a light curtain within the aisle. The light curtain may comprise one or more light beams emitted by the IR transmitter(s) and received by the IR receiver(s). The light curtain may extend horizontally across the aisle from one side to another. In one implementation, the pair of active IR transmitter and IR receiver may be located at about 75 centimeters height relative to the ground, with the IR transmitter on one side of the aisle, and the IR receiver on the opposite side of the aisle. The pair of active IR transmitter and IR receiver may define a row within the aisle. Pairs of the active IR transmitters and corresponding IR receivers may be arranged at intervals along the length of the aisle. As the object moves along the aisle, light beams produced by the IR transmitters are obscured. Data produced by the IR transmitter and IR receiver pairs is also known as active data. The active data provides an indication of which row an object is positioned in and may also provide other information such as a direction of travel, speed, and so forth.

The passive IR sensors may also be arranged along the aisle. For example, passive IR sensors may be arranged at intervals along the length of the aisle and on both sides of the aisle. The passive IR sensors are configured to determine presence of an object based on emission of infrared radiation by, or associated with, the object. The passive IR sensors may be configured with a detection zone extending from an outer edge of the aisle towards a centerline or middle of the aisle. Passive data acquired by the passive IR sensors, provide information indicative of proximity of the object to one or more of the passive IR sensors. Given a known position of the passive IR sensor, determination of presence of the object may be used to determine which side of the aisle the object is positioned on. For example, a passive IR sensor on a left side of the aisle may detect an object, while a corresponding passive IR sensor on the right side of the aisle detects no object. The resulting passive data may be processed to determine that the object is positioned on the left side of the aisle.

Information from the active and passive optical sensors may be combined to form IR observations. In one implementation, the active data provides one or more rows of cells occupied by the object while the passive data provides one or more columns of cells occupied by the object. For example, the object may be determined to be within the cell(s) at the intersection of the determined row(s) and column(s).

The object positioning system is configured to use the data acquired by the non-optical sensors such as the RF receivers, and the optical sensors such as the active IR transmitter and receiver pairs as well as the passive IR sensors. The data is processed using a probabilistic graphical model, Bayesian network, or other technique to generate the object position data. In one implementation, the input to the probabilistic graphical model is a sequence of observations based on the data from the one or more sensors.

The object positioning system is configured to determine probabilities that the object is positioned within a cell. The probabilities may be based on one or more models associated with different aspects of the system. An RSSI model provides a probability distribution of RF signal strength values given the tag being positioned within a particular cell. An optical model provides probability that the object is positioned within a given cell. The optical model may be expressed as a Boolean structure, such as true/false or high/low with regard to a particular cell being occupied by the object. Using the probabilities determined by the RSSI model and the optical model, a first position for the object at a first time “T” may be determined using a Viterbi decoder by identifying the position having a greatest probability. The first position for the object may be used in subsequent steps by the model to determine the position as time increases.

At subsequent times, the model may consider candidate cells for the position at those subsequent times “T+dT”. An IR score may be calculated for each of the candidate cells. In one implementation, the IR observations from T+dT may be used to restrict the set of possible positions for the object. For example, an IR beam provided by an IR transmitter, which becomes unblocked at time T+dT implies no object is in the row of cells corresponding to the IR transmitter. As a result, a zero or very low score may be calculated for the cells in the row. Cells with an IR score below a threshold value may be disregarded.

Cells with an IR score above the threshold value comprise a set of candidate cells. Adjacent cells may be determined which are adjacent to the candidate cell. A score for each of the candidate cells is calculated. The score is representative of probabilities associated with movement of the object and the RSSI values obtained by the RF receivers. At a given time, the object positioning system may output as the object position the cell having a highest score.

Furthermore, the tag identifier acquired by the RF receiver from the tag may be used to identify the object. A user, administrator, or automated process may associate the tag identifier with a particular user account. For example, the tag identifier “Z93” may be associated with the user “Alice”. For example, a previously unassociated tag identifier may be detected upon entry into the facility. The unassociated tag may then be associated with a corresponding user account based on biometric identification of the user at an entry point.

The facility may include a material handling facility, library, museum, and so forth. As used herein, a materials handling facility may include, but is not limited to, warehouses, distribution centers, cross-docking facilities, order fulfillment facilities, packaging facilities, shipping facilities, rental facilities, libraries, retail stores, wholesale stores, museums, or other facilities or combinations of facilities for performing one or more functions of materials (inventory) handling.

The systems and techniques described herein allow for determining the position and identity of multiple objects within the aisle or other portions of the facility which are instrumented with the one or more sensors. The combination of the RF and optical sensors used in conjunction with the probabilistic graphical model described herein provides a robust, accurate, and computationally efficient system. In some implementations, the object positioning system may be configured to provide position information which is accurate to within 100 centimeters or less at a 99thpercentile of accuracy and identity. The resulting object position data may be used by other systems associated with the facility, such as providing information associated with the items stored in the fulfillment center, audit trail information, loss prevention, access control, and so forth.

Illustrative System

An implementation of a materials handling system100configured to store and manage inventory items is illustrated inFIG. 1. A materials handling facility102(facility) comprises one or more physical structures or areas within which one or more items104(1),104(2), . . . ,104(Q) may be held. As used in this disclosure, letters in parenthesis such as “(Q)” indicate an integer value. The items104comprise physical goods, such as books, pharmaceuticals, repair parts, electronic gear, and so forth. The materials handling facility102may include one or more areas designated for different functions with regard to inventory handling. In this illustration, the materials handling facility102includes a receiving area106, a storage area108, and a transition area110.

The receiving area106may be configured to accept items104, such as from suppliers, for intake into the materials handling facility102. For example, the receiving area106may include a loading dock at which trucks or other freight conveyances unload the items104.

The storage area108is configured to store the items104. The storage area108may be arranged in various physical configurations, such as a series of aisles112. The aisle112may be configured with, or defined by, inventory locations114on one or both sides of the aisle112. The inventory locations114may include one or more of shelves, racks, cases, cabinets, bins, floor locations, or other suitable storage mechanisms. The inventory locations114may be affixed to the floor or another portion of the materials handling facility's structure, or may be movable such that the arrangements of aisles112may be reconfigurable. In some implementations, the inventory locations114may be configured to move independently of an outside operator. For example, the inventory locations114may comprise a rack with a power source and a motor, operable by a computing device to allow the rack to move from one position within the materials handling facility102to another.

One or more objects116may move within the materials handling facility102. The objects116may include, but are not limited to, people, robots, totes, and so forth. For example, the object116may be a user moving about within the materials handling facility102to pick or place the items104in various inventory locations114. In another example, the object116may be a tote, which is moved by a person, robot, or other agency within the facility102.

Each object116has a position118within the space of the facility102. The position118may be expressed as a relative position or an absolute position. The position118may be expressed as a one-dimensional, two-dimensional, or three-dimensional set of coordinates. For example, a compact facility102comprising a single aisle112may express the position118as a one-dimensional value, such as distance down the aisle relative to a reference point. In comparison, a two-dimensional position118may express the position118as a set of X and Y coordinates relative to a reference point. Similarly, a three-dimensional set of coordinates may express the position118as a set of X, Y, and Z coordinates where Z indicates height. In other implementations, instead of or in addition to coordinates the position118may be expressed in terms of a particular cell, inventory location114, and so forth. For example, the location may be specified as “Aisle 7, Row 5, Left Column (side)”.

One or more sensors120may be configured to acquire information about the objects116in the aisle112. The sensors120may include, but are not limited to, radio frequency (RF) receivers, active infrared (IR) transmitter and IR receiver pairs, and passive IR sensors. Other sensors may be used, such as cameras, microbolometers, weight sensors, motion sensors such as accelerometers or gyroscopes, and so forth. The sensors120are discussed in more detail below with regard toFIG. 2.

While the storage area108is depicted as having one or more aisles112, inventory locations114storing the items104, sensors120, and so forth, it is understood that the receiving area106, the transition area110, or other areas of the facility102may be similarly equipped. Furthermore, the arrangement of the various areas within the facility102are depicted functionally rather than schematically. For example, in some implementations multiple different receiving areas106, storage areas,108, and transition areas110may be interspersed rather than segregated.

The facility102may include, or be coupled to, an inventory management system122. The inventory management system122is configured to interact with users or devices such as sensors, robots, material handling equipment, computing devices, and so forth in one or more of the receiving area106, the storage area108, or the transition area110.

The materials handling facility102may be configured to receive different kinds of items104from various suppliers, and to store them until the customer orders or retrieves one or more of the items104. A general flow of items104through the materials handling facility102is indicated by the arrows ofFIG. 1. Specifically, as illustrated in this example, items104may be received from one or more suppliers, such as manufacturers, distributors, wholesalers, and so forth, at the receiving area106. In various implementations, the items104may include merchandise commodities perishables, or any suitable type of item, depending on the nature of the enterprise that operates the facility102.

Upon being received from a supplier at receiving area106, the items104may be prepared for storage. For example, in some implementations, items104may be unpacked, or otherwise rearranged. The inventory management system122may include one or more software applications executing on a computer system to provide inventory management functions. These inventory management functions may include maintaining information indicative of the type, quantity, condition, cost, location, weight, or any other suitable parameters with respect to the items104. The items104may be stocked, managed, or dispensed in terms of countable, individual units or multiples, such as packages, cartons, crates, pallets, or other suitable aggregations. Alternatively, some items104, such as bulk products, commodities, and so forth, may be stored in continuous or arbitrarily divisible amounts that may not be inherently organized into countable units. Such items104may be managed in terms of measurable quantity such as units of length, area, volume, weight, time, duration, or other dimensional properties characterized by units of measurement. Generally speaking, a quantity of an item104may refer to either a countable number of individual or aggregate units of an item104or a measurable amount of an item104, as appropriate.

After arriving through the receiving area106items104may be stored within the storage area108. In some implementations, like items104may be stored or displayed together in the inventory locations114such as in bins, on shelves, hanging from pegboards, and so forth. In this implementation, all items104of a given kind are stored in one inventory location114. In other implementations, like items104may be stored in different inventory locations114. For example, to optimize retrieval of certain items104having high turnover within a large physical facility, those items104may be stored in several different inventory locations114to reduce congestion that might occur at a single inventory location114.

When a customer order specifying one or more items104is received, or as a user progresses through the facility102, the corresponding items104may be selected or “picked” from the inventory locations114containing those items104. In various implementations, item picking may range from manual to completely automated picking. For example, in one implementation, a user may have a list of items104they desire and may progress through the facility102picking items104from inventory locations114within the storage area108, and placing those items104into a tote. In other implementations, employees of the facility102may pick items104using written or electronic pick lists derived from customer orders. These picked items104may be placed into a tote as the employee progresses through the facility102.

After items104have been picked, they may be processed at a transition area110. The transition area110may be any designated area within the facility102where items104are transitioned from one location to another, or from one entity to another. For example, the transition area110may be a packing station within the facility102. When the item104arrives at the transition area110, the items104may be transitioned from the storage area108to the packing station. Information about the transition may be maintained by the inventory management system122.

In another example, if the items104are departing the facility102a list of the items104may be obtained and used by the inventory management system122to transition responsibility for, or custody of, the items104from the facility102to another entity. For example, a carrier may accept the items104for transport with that carrier accepting responsibility for the items104indicated in the list. In another example, a customer may purchase or rent the items104and remove the items104from the facility102.

The facility102includes, or has access to, an object positioning system124. The object positioning system124is configured to use input from the one or more sensors120to generate object position data126. The object position data126may include one or more of position information, identity, direction of movement, speed of movement, proximity to other objects116, and so forth. The position of the object116may be stored as a time series, providing a track of movement. As described above, the position118may be relative or absolute.

In some implementations, the object positioning system124may operate in conjunction with the inventory management system122or other systems. For example, the object positioning system124may provide the object position data126to the inventory management system122for use in tracking which user is adding or removing items104at a particular inventory location114. In another example where the object116is an employee, the object position data126may be used to generate time and attendance data.

The object positioning system124may employ a probabilistic graphical model. The model may be used to determine the position118based at least in part on probabilities indicative of the object116, at a particular position. These probabilities may be based on information acquired from non-optical and optical sensors. The sensors120and operation of the object positioning system124are discussed in more detail below.

FIG. 2is a block diagram200illustrating additional details of the materials handling facility102, according to some implementations. The facility102may be connected to one or more networks202, which in turn connect to one or more servers204. The network202may include private networks, public networks such as the Internet, or a combination thereof. The network202may utilize wired technologies (e.g., wires, fiber optic cable, and so forth), wireless technologies (e.g., RF, IR, acoustic, optical, and so forth), or other connection technologies. The network202is representative of any type of communication network, including one or more of data networks or voice networks. The network202may be implemented using wired infrastructure (e.g., copper cable, fiber optic cable, and so forth), a wireless infrastructure (e.g., RF, cellular, microwave, satellite), or other connection technologies.

The servers204may be configured to execute one or more modules or software applications associated with the inventory management system122, the object positioning system124, and so forth. While the servers204are illustrated as being in a location outside of the facility102, in other implementations at least a portion of the servers204may be located at the facility102. The servers204are discussed in more detail below with regard toFIG. 3.

As described above the facility102may have one or more objects116which move throughout the facility102. One or more RF tags206may be associated with the object116. The RF tags206are configured to emit an RF signal208. In one implementation, the RF tag206may be a radio frequency identification (RFID) tag configured to emit the RF signal208upon activation by an external signal. For example, the external signal may comprise a radio frequency signal or a magnetic field configured to energize or activate the RFID tag. In another implementation, the RF tag206may comprise a transmitter and a power source configured to power the transmitter. For example, the RF tag206may comprise a Bluetooth Low Energy (BLE) transmitter and battery. In other implementations, the tag may use other techniques to indicate presence. For example, an acoustic tag may be configured to generate an ultrasonic signal.

The objects116which may move about the facility102may include a tote210. The tote210is configured to carry or otherwise transport one or more items104. For example, the tote210may include a basket, a cart, a bag, and so forth. In some implementations, the tote may include an RF tag206.

Generally, the inventory management system122, the object positioning system124, or other systems associated with the facility102may include any number and combination of input components, output components, and servers204.

The one or more sensors120may be associated with the inventory locations114. The sensors120may include one or more RF receivers212configured to detect the RF signal208emitted by the RF tag206. The RF receivers212may be configured to report received signal strength information (RSSI) data associated with the received RF signal208. The RF receivers212may also be configured to receive other information. For example, the RF receivers212may be configured to receive data transmitted by the RF tag206, such as a tag identifier. As described below, the tag identifier may be associated with an identity of the object116. For example, the tag identifier“Z93” may be associated with the user account for the person “Alice”.

The RF receivers212exhibit a receive range or distance which is based at least in part on the antenna, receiver sensitivity, local RF noise, and so forth. In some implementations, the RF receivers212may be configured to exhibit a typical receive range or distance of about 1.5 meters to 2 meters with respect to the RF signal208. The RF receivers212are arranged within the facility102at known positions. This arrangement is discussed in more detail below with regard toFIG. 5.

An RF transmitter may be combined with the RF receivers212. For example, the RF receivers212may be part Bluetooth LE nodes. In some implementations these RF transmitters and the RF receivers212may be used to provide network connectivity. For example, the Bluetooth LE nodes may act as network access points.

The sensors120may also include active IR transmitter/receiver pairs (pairs)214. These pairs214are configured to emit a light beam from the IR transmitter, which is directed towards a corresponding receiver. When in the path of the light beam, the object116may obscure the light beam decreasing the intensity of the received beam at the receiver. The pairs214are arranged within the facility102at known positions.

In some implementations, an active IR transmitter/receiver pair214may be associated with each row in the aisle112. A plurality of the pairs214may be arranged along the aisle112, forming a “light curtain”. This arrangement is discussed in more detail below with regard toFIG. 5. Output from the receiver may be used to determine the presence of the object116in the row. While the active IR transmitter and receiver are described in pairs, in other implementations, other configurations may be used. For example, a single IR transmitter may provide light beams to a plurality of IR receivers.

In some implementations, the light emitted by the IR transmitter may be modulated. For example, different IR transmitters may use different pulse width modulation frequencies.

The sensors120may include passive IR sensors216. The passive IR sensors216are configured to determine proximity of an object116by detecting infrared radiation emitted by the object116. In some implementations the passive IR sensors216may be referred to as “passive IR sensors” or “passive IR proximity sensors”. The passive IR sensors216may comprise pyroelectric materials configured to generate an electrical signal or change one or more electrical characteristics (such as resistance) based on the IR radiation incident thereon. The passive IR sensor216may be configured to generate a signal when the level of the IR detected changes beyond a threshold amount, or exhibits a particular gradient of change. The passive IR sensor216may exhibit a window or area of coverage within which the object116may be detected. The passive IR sensors are arranged within the facility102at known positions. In some implementations, a passive IR sensor216may be placed on one or both sides of the aisle112for each row. This arrangement is discussed in more detail below with regard toFIG. 5. The resulting data provided by passive IR sensor216may thus indicate which side of the aisle112, or column, the object116is present at.

In some implementations, other proximity sensors may be used instead of, or in addition to the passive IR sensors216. For example capacitive proximity sensors may determine presence of the object116.

Other sensors218may also be used in the facility102and may provide data to one or more of the inventory management system122, the object positioning system124, or other systems. These other sensors218may include cameras, imaging devices, microbolometers, weight sensors, pressure sensors, Interpolating Force-Sensitive Resistance (IFSR) sensors, motion sensors, microphones, touch sensors, radio receivers, and so forth. The motion sensors may include accelerometers, gyroscopes, tilt sensors, gravimeters, and so forth. The other sensors218may include other components capable of receiving input about the environment.

The facility102may also include output devices. These output devices are configured to present information to users or otherwise provide output to the surrounding environment. The facility102may include one or more display devices220. The display devices220may include electronically addressable displays configurable to present a visual image. For example, the display devices220may include projectors, liquid crystal displays, cathode ray tubes, plasma displays, and so forth. One or more speakers222may also be available to present audible output. Other output devices (not depicted) may also be present, such as printers, haptic output devices, and so forth.

The facility102may include one or more access points224configured to establish one or more wireless networks. The access points224may use Wi-Fi, near field communication (NFC), Bluetooth, or other technologies to establish wireless communications between a device and the network202. The wireless networks allow the devices to communicate with one or more of the inventory management system122, the object positioning system124, the sensors120, other sensors218, the RF tag206, a communication device of the tote210, or other devices.

FIG. 3illustrates a block diagram300of the server204. The server204may be physically present at the facility102, may be accessible by the network202, or a combination of both. The server204does not require end-user knowledge of the physical location and configuration of the system that delivers the services. Common expressions associated with the server204may include “on-demand computing,” “software as a service (SaaS),” “platform computing,” “network-accessible platform,” “cloud services,” “data centers” and so forth. Services provided by the server204may be distributed across one or more physical or virtual devices.

The server204may include one or more hardware processors302(processors) configured to execute one or more stored instructions. The processors302may comprise one or more cores. The server204may include one or more input/output (I/O) interface(s)304to allow the processor302or other portions of the server204to communicate with other devices. The I/O interfaces304may comprise inter-integrated circuit (I2C), serial peripheral interface bus (SPI), Universal Serial Bus (USB) as promulgated by the USB Implementers Forum, RS-232, and so forth.

The I/O interface(s)304may couple to one or more I/O devices306. The I/O devices306may include input devices such as one or more of a keyboard, mouse, scanner, and so forth. The I/O devices306may also include output devices such as one or more of a display, printer, audio speakers, and so forth. In some embodiments, the I/O devices306may be physically incorporated with the server204or may be externally placed.

The server204may also include one or more communication interfaces308. The communication interfaces308are configured to provide communications between the server204and other devices, such as the sensors120, routers, the access points224, and so forth. The communication interfaces308may include devices configured to couple to personal area networks (PANs), wired and wireless local area networks (LANs), wired and wireless wide area networks (WANs), and so forth. For example, the communication interfaces308may include devices compatible with Ethernet, Wi-Fi, and so forth.

The server204may also include one or more busses or other internal communications hardware or software that allow for the transfer of data between the various modules and components of the server204.

As shown inFIG. 3, the server204includes one or more memories310. The memory310comprises one or more computer-readable storage media (“CRSM”). The CRSM may be any one or more of an electronic storage medium, a magnetic storage medium, an optical storage medium, a quantum storage medium, a mechanical computer storage medium, and so forth. The memory310provides storage of computer-readable instructions, data structures, program modules, and other data for the operation of the server204. The memory310provides storage of computer readable instructions, data structures, program modules and other data for the operation of the server204. A few example functional modules are shown stored in the memory310, although the same functionality may alternatively be implemented in hardware, firmware, or as a system on a chip (SOC).

The memory310may include at least one Operating System (OS) module312. The OS module312is configured to manage hardware resource devices such as the I/O interfaces304, the I/O devices306, the communication interfaces308, and provide various services to applications or modules executing on the processors302. The OS module312may implement a variation of the Linux operating system as promulgated by Linus Torvalds, the Windows Server operating system from Microsoft Corporation of Redmond, Wash., and so forth.

Also stored in the memory310may be one or more of the following modules. These modules may be executed as foreground applications, background tasks, daemons, and so forth.

A communication module314may be configured to establish communications with one or more of the sensors120, other servers204, or other devices. The communications may be authenticated, encrypted, and so forth.

The memory310may store an inventory management module316. The inventory management module316is configured to provide the inventory functions as described herein with regard to the inventory management system122. For example, the inventory management module316may track items104between different inventory locations114.

The memory310may also store an object positioning module318configured to provide the object position data126as described herein with regard to the object positioning system124. The object positioning module318is configured to access sensor data received from the one or more sensors120and generate the object position data126. In some implementations, the object positioning module318may use a probabilistic graphical model to determine the position of the object116. Operation of the object positioning module318and the techniques used to generate the object position data126are discussed below in more detail.

Other modules320may also be present in the memory310. For example, a time and attendance module may be configured to access the object position data to determine a quantity of hours in which an employee was within the facility102. In another example, a user authentication module may be configured to authenticate or identify a user. For example, the user authentication module may use biometric data such as a fingerprint, iris scan, venous pattern, and so forth to identify the user.

The memory310may also include a data store322to store information. The data store322may use a flat file, database, linked list, tree, executable code, script, or other data structure to store the information. In some implementations, the data store322or a portion of the data store322may be distributed across one or more other devices including other servers204, network attached storage devices, and so forth.

The data store322may include inventory data324. The inventory data324may comprise information associated with the items104. The information may include one or more inventory locations114, at which one or more of the items104are stored. The inventory data324may also include price, quantity on hand, weight, price, expiration date, and so forth. The inventory management module316may store information associated with inventory management functions in the inventory data324.

The data store322may also store sensor data326. The sensor data326may include one or more of RF data328, active data330, or passive data332. The object positioning module318may access the sensor data326.

The RF data328may comprise information generated by the RF receivers212. For example, the RF data328may include information indicative of a particular RF receiver212, a tag identifier received from the RF tag206, a received signal strength indication indicative of the signal strength associated with the RF signal208at a particular RF receiver212, and so forth. In some implementations the RF data328may include information acquired by one or more of the access points224.

The active data330may include information generated by active IR transmitter/receiver pairs214. The information may indicate whether light from a particular active IR transmitter is obscured or unobscured with respect to the corresponding IR receiver in the pair. For example, the active data330may include information indicative of a particular IR transmitter/receiver pair214, a duration of the obscuration, and so forth.

The passive data332may include information generated by passive IR sensors216. The information may indicate whether an object has been detected proximate to the passive IR sensor216. For example, the passive data332may include information indicative of a particular passive IR sensor216, size of the object, intensity of the infrared signal received from the object, and so forth.

In some implementations the placement of the tags and the receivers may be switched from that described above. For example, the object116may carry a receiver while the transmitters are arranged within the facility102. Continuing the example, the user may carry an acoustic receiver while acoustic transmitters are in fixed positions along with the sensors120.

Object data334may also be stored in the data store322. The object data334comprises information associated with the object116. The information may include type of object, RF tag identifier, object size data, identification characteristics, and so forth. For example, the object data334may indicate that the object116(1) is a user, is associated with the RF tag identifier of “Z93”, that the user is approximately 2 m tall, 60 cm wide, and 18 cm thick. Continuing the example, the object data334may also associate the object with a particular user account, device account, and so forth. The object positioning system124may access the object data334as part of the process to generate the object position data126. For example, the object positioning module318may retrieve the user account associated with a particular RF tag identifier.

Physical layout data336may also be stored in the data store322. The physical layout data336provides a mapping between different devices, such as the sensors120, and physical positions within the facility102. For example, the physical layout data336may indicate the coordinates within the facility102for each of the RF receivers212, the active IR transmitter/receiver pairs214, and the passive IR sensors216. The physical layout data336may also include the positions of the inventory locations114, the aisles112, or other features of the facility102. In some implementations, the physical layout data336may also include information designating boundaries of one or more cells used to indicate positions118within the facility102. For example, boundaries of, or a center of, a particular cell at a particular row and column of a given aisle112may be specified. The object positioning system124may access the physical layout data336as part of the process to generate the object position data126.

The memory310may also store the object position data126. The object position data126may include one or more of position information, identity, direction of movement, speed of movement, proximity to other objects116, and so forth. The position of the object116may be stored as a time series, providing a track of movement.

The data store322may store other data338as well, such as user preferences, configuration files, permissions associated with user accounts, time and attendance data, and so forth.

The server204may also include a power supply340. The power supply340is configured to provide electrical power suitable for operating the components in the server204.

FIG. 4illustrates a block diagram400of the tote210, according to some implementations. The tote210may include an RF tag206. The RF tag206may be affixed to, integral with, or is otherwise associated with the tote210. In some implementations, the tote210may have identifiers, tags, or other indicia thereupon. For example, a machine-readable optical code, such as a barcode, may be affixed to a side of the tote210.

The tote210may include one or more hardware processors402(processors) configured to execute one or more stored instructions. The processors402may comprise one or more cores. The tote210may include one or more I/O interface(s)404to allow the processor402or other portions of the tote210to communicate with other devices. The I/O interfaces404may include I2C, SPI, USB, RS-232, and so forth.

The I/O interface(s)404may couple to one or more I/O devices406. The I/O devices406may include input devices such as one or more of a camera, a microphone, a touch sensor, a button, range camera, accelerometer, gyroscope, magnetometer, tilt sensor, weight sensor, pressure sensor, proximity sensor, and so forth. Other input devices may include RFID readers, NFC readers, barcode scanners, fingerprint readers, and so forth. The I/O devices406may also include output devices such as one or more of a display, audio speakers, haptic output device and so forth. In some implementations input and output devices may be combined. For example, a touchscreen display may incorporate a touch sensor and a display220. In some embodiments, the I/O devices406may be physically incorporated with the tote210or may be externally placed.

The tote210may also include one or more communication interfaces408. The communication interfaces408are configured to provide communications between the tote210and other devices, such as other totes210, routers, access points224, the servers204, and so forth. The communication interfaces408may include devices configured to couple to PANs, LANs, WANs, and so forth. For example, the communication interfaces408may include devices compatible with Ethernet, Wi-Fi, Bluetooth, ZigBee, and so forth.

The tote210may also include one or more busses or other internal communications hardware or software that allow for the transfer of data between the various modules and components of the tote210.

As shown inFIG. 4, the tote210includes one or more memories410. The memory410comprises one or more CRSM as described above. The memory410provides storage of computer readable instructions, data structures, program modules and other data for the operation of the tote210. A few example functional modules are shown stored in the memory410, although the same functionality may alternatively be implemented in hardware, firmware, or as a SOC.

The memory410may include at least one OS module412. The OS module412is configured to manage hardware resource devices such as the I/O interfaces404, the I/O devices406, the communication interfaces408, and provide various services to applications or modules executing on the processors402. The OS module412may implement a variation of the Linux operating system, such as Android as promulgated by Google, Inc. Other OS modules412may be used, such as the Windows operating system from Microsoft Corporation of Redmond, Wash., the LynxOS from LynuxWorks of San Jose, Calif., and so forth.

Also stored in the memory410may be one or more of the following modules. These modules may be executed as foreground applications, background tasks, daemons, and so forth.

A communication module414may be configured to establish communications with one or more of the sensors120, servers204, or other devices. The communications may be authenticated, encrypted, and so forth.

The memory410may also store a tote item tracking module416. The tote item tracking module416is configured to maintain a list of items104, which are associated with the tote210. For example, the tote item tracking module416may receive input from a user by way of a touch screen display with which the user may enter information indicative of the item104placed in the tote210. In another example, the tote item tracking module416may receive input from one of the I/O devices406, such as an RFID or NFC reader. The tote item tracking module416may send the list of items104to the inventory management system122. The tote item tracking module416may also be configured to receive information from the inventory management system122. For example, a list of items104to be picked may be presented within a user interface on the display220of the tote210.

Other modules418may also be stored within the memory410. In one implementation, a user authentication module may be configured to receive input and authenticate or identify a particular user. For example, the user may enter a personal identification number or may provide a fingerprint to the fingerprint reader to establish their identity.

The memory410may also include a data store420to store information. The data store420may use a flat file, database, linked list, tree, executable code, script, or other data structure to store the information. In some implementations, the data store420or a portion of the data store420may be distributed across one or more other devices including the servers204, other totes210, network attached storage devices and so forth.

A unique identifier424may also be stored in the memory410. In some implementations, the unique identifier424may be stored in rewritable memory, write-once-read-only memory, and so forth. For example, the unique identifier424may be burned into a one-time programmable non-volatile memory, such as a programmable read-only memory (PROM). In some implementations, the unique identifier424may be part of a communication interface408. For example, the unique identifier424may comprise a media access control address associated with a Bluetooth interface.

Other data426may also be stored within the data store420. For example, tote configuration settings, user interface preferences, and so forth may also be stored.

The tote210may also include a power supply428. The power supply428is configured to provide electrical power suitable for operating the components in the tote210. The power supply428may comprise one or more of photovoltaic cells, batteries, wireless power receivers, fuel cells, capacitors, and so forth.

FIG. 5illustrates a plan view500looking down on an aisle112within the facility102. In this illustration, sensors120are arranged on both sides of the aisle112, such as to the left and to the right of the aisle112. As used in this disclosure, “left” and “right” with respect to positions in the aisle112are used for convenience and not as a limitation. The aisle112may be divided into a two-dimensional grid. In this illustration, cell boundaries502are indicated with a dotted line. The two-dimensional grid includes rows504and columns506. For ease of illustration, the rows504are designated by numbers while the columns506are designated as “Left” or “Right”. While two columns506are illustrated, in some implementations the aisle112may be divided into a single column or more than 2 columns.

As described above, a plurality of RF receivers212are configured to receive the RF signal emitted by the RF tag206. The RF receivers212are configured to provide RF data328, which may include an indication of relative signal strength, data transmitted by the RF signal208such as an RF tag identifier, and so forth. For example, the RF receivers212may provide received signal strength information (RSSI) for the RF signals208received. The RSSI may comprise a relative or dimensionless indication of signal strength, or may provide information expressed in dimensional terms, such as decibels referenced to one milliwatt (dBm). The RSSI may, but need not be, a value provided by a particular protocol, such as the received signal strength indicator as provided for in the Wi-Fi protocol. In some implementations other indications of received signal strength such as received channel power indicator (RCPI) as supported by Wi-Fi may be used. The RF receivers212may be arranged at known locations within the aisle212. For example, as illustrated here several RF receivers212are arranged at horizontal intervals along each side of the aisle112. For example, the RF receivers212(or the antennas thereof) located along a side of the aisle112may be placed at intervals of between 60 and 200 centimeters as measured horizontally between the devices.

The active infrared (IR) transmitter/receiver pairs (pairs)214may be configured to provide a light curtain within the aisle112. The light curtain may comprise a plurality of light beams508provided by the pairs214. The light curtain may extend horizontally across the aisle112from one side to another. The term light beam508is used by way of illustration, and not as a limitation. In some implementations, the IR transmitter may provide a non-focused emission of infrared light.

The pair214may be located above ground level, with the transmitter on one side of the aisle112, and the receiver on the opposite side of the aisle112. For example, the height of the pair214may be between 60 and 100 cm above the floor of the aisle112. The pair214may define the row504within the aisle. For example, each row504may have a single light beam508.

Horizontal spacing between the pairs214may be selected based on requirements to attain a particular level of accuracy. For example, shorter horizontal spacing may result in smaller cell sizes compared to larger spacing. For example, the horizontal spacing between the pairs214may be between 8 and 30 cm.

In this illustration, the light beam508is arranged approximately at a midpoint of the row504, relative to the cell boundaries502. Continuing the example above with regard to the horizontal spacing, each row504in this illustration may be about 15 centimeters as measured along a shortest dimension of the rectangle. In other implementations, the light beams508may define at least a portion of the cell boundary502.

As an object116moves along the aisle112, light beams508produced by the IR transmitters are obscured, or otherwise blocked or attenuated by the object116. For example, as illustrated here the object116(1) comprising a user is positioned with a center of mass at row 5 in the left column. The light beam508emitted by the IR transmitter within a row 5 is blocked by the body of the user, resulting in a drop in the detected intensity of the infrared light at the receiver on the opposite side of the aisle112.

The corresponding IR receivers generate active data330characterizing the infrared light falling on the receivers. The active data330may indicate the presence or absence of the light beam508, intensity of the received light, and so forth. The active data330provides an indication of which row504an object116is positioned within. Other information may be derived from the active data330, such as a direction of travel, speed, and so forth. However, because the light beam508spans the aisle112, the column506which the object116occupies is unknown.

The passive IR sensors216may also be arranged along the aisle112. For example, passive IR sensors216may be arranged at horizontal intervals along a length of the aisle112, on both sides of the aisle112. In some implementations, the passive IR sensors216may be arranged on one side of the aisle112, or may alternate from one side of the aisle112to the other.

The passive IR sensors216are configured to determine presence of an object116based on emission of infrared radiation by the object116, an occlusion of background infrared radiation by the object116, and so forth. In this illustration, the passive IR sensors216are arranged such that they provide a passive infrared detection zone510(zone) within a row504. In some implementations, such as depicted here, each row may have a passive IR sensor216on each side of the aisle112. However, in other implementations, the passive IR sensors216may be spaced horizontally along the length of the aisle112, such that the passive IR sensor216is present at every nthrow. For example, the passive IR sensor216may be located at every third row504.

The zone510is depicted as having a boundary within the row504and extended to approximately the midline of the aisle112, corresponding to the boundaries of the respective cells. In other implementations, the zone510may extend into adjacent rows, columns, or both. Thus a single passive IR sensor216may maintain a zone510, which covers 2 or more rows504.

The passive data332acquired by the passive IR sensors216, provides information indicative of proximity of the object116to one or more of the passive IR sensors216. Given a known position of the passive IR sensor216, determination of presence of the object116may be used to determine which side or column506of the aisle112the object116is positioned on. For example, as depicted here the user116(1) is detected by the passive IR sensors216located on the left side of the aisle112at the boundaries of the rows 4 and 5. The resulting passive data332indicates the object116is in the left column506. However, because the zone510extends across more than one cell, the row504, which the object116occupies, is unknown.

The spacing between the individual sensors120may be varied based on one or more factors. For example, a closer spacing may be used when a finer degree of position118determination is called for. Contrariwise, in situations where coarser position118is acceptable, spacing between the sensors120may be increased. Furthermore, the spacing between individual sensors120may vary from aisle112to aisle112, or within an aisle112. For example, a first portion of the aisle112may have the sensors120positioned at a first distance relative to one another while a second portion farther down the aisle112may have the sensors120positioned at a second distance relative to one another, wherein the second distance is greater than the first.

In other implementations other types of sensors may be used. For example, a microbolometer may be used to generate an infrared image of at least a portion of the aisle112. Data based on this infrared image may be used in place of, or in addition to, the active data330, the passive data332, or both.

As described above, the positions of the sensors120in the facility102may be stored in the physical layout data336. For example, the physical layout data336may indicate that the passive IR sensor216(597) maintains a zone510, which encompasses row 4 and row 5 of the left column506in aisle112(43). The object positioning module318may use the physical layout data336to generate the object position data126.

FIG. 6illustrates a plan view600looking down on the portion of the aisle112ofFIG. 5, according to some implementations. In this illustration, the rows504and columns506of the grid are depicted. The grid comprises a plurality of cells602. In some implementations, a non-rectilinear arrangement of cells602may be used. For example, cells602may comprise hexagons.

Superimposed on the cells602are RF ranges604associated with the RF receivers212. The RF ranges604are depicted as broken lines and indicate a distance at which an RF signal208of a given radiated power will produce a given signal strength at the RF receiver212. The RF ranges604are depicted in this illustration as ellipses, however, other patterns may result from different antenna design, signal phasing, physical placement, interference from RF noise sources, and so forth. Furthermore, while the RF ranges604are depicted to overlap and provide contiguous coverage for the portion of the aisle112depicted, in some implementations, there may be more or less overlap between 2 or more RF ranges604.

The object positioning module318may designate some of the cells as unoccupied cells606. For example, based on the active data330and the passive data332some cells may be determined to be unoccupied. This determination is discussed in more detail.

An occupied cell608is the cell in which the object116is positioned. In some implementations where the object116extends beyond the confines of a single cell602, the occupied cell608may indicate a center-of-mass (CoM) associated with the object116. As used in this disclosure, “center-of-mass” may indicate an arbitrary center of the object116, and not necessarily a physical or geometric balance point for the object116. As described in more detail below, the object positioning module318may determine a set of candidate cells610. These candidate cells610may include one or more adjacent cells612, which are proximate to, or about the occupied cell608. The adjacent cells612may include those cells which share at least one edge or vertex with the occupied cell608. The candidate cells610may include cells to which the object116may move to, or remain within, given a particular time interval. For example, the adjacent cells612may be based at least in part on assumptions as to a maximum speed the object116may travel within the facility102(such as 5 kilometers-per-hour) and a time interval (such as 200 milliseconds).

FIG. 7is a block diagram700illustrating a portion of the object positioning system124, according to some implementations. In this illustration, RF observations702are depicted. The RF observations702comprise RF data328at particular moments in time. For example, the RF data328for time “T” depicts that RF receiver212“2L” has an RSSI of “31” for the RF signal208received from the RF tag206having a tag identifier of “A93”. The RF receiver212may be identified in the RF data328by way of a serial number or other unique identifier associated with each RF receiver212, or by the physical position within the facility102. In other implementations where the receivers are configured to receive non-RF signals208, these may be designated as non-optical observations.

IR observations704are also depicted. The object positioning module318may accept the active data330and the passive data332and generate the IR observations704. The IR observations704may express output of an optical model, which uses the active data330and the passive data332to determine a probability that the object116is positioned within a given cell602. For example, as described above, the active data330may provide an indication as to the row504of the object116, while the passive data332provides an indication as to the column506of the object116. By combining this data, one or more cells602may be designated as occupied. As illustrated here, the IR observations704may be expressed as a Boolean structure such as true/false or high/low with regard to a particular cell602being occupied by the object116. In other implementations where the sensors are configured to operate in other wavelengths, such as ultraviolet or visible light, the information may be designated as optical observations.

The object positioning module318may include one or more additional modules including an identification module706, a probabilistic graphical model module708, a Viterbi decoder module710, and so forth. The identification module706is configured to identify the object116. This identification may be used to distinguish one object116from another. In one implementation, the identification module706may access the object data334and use the tag identifier included in the RF observations702to associate the RF tag206with a particular object116. For example, the RF tag identifier “Y17” may be associated with the user account for “Bob” while the RF tag identifier “W19” is associated with a device such as “Tote47”. The association between the RF tag identifier and the object116may be made at the time the object116enters the facility102. For example, upon entry to the facility102a user may be identified by way of one or more biometric characteristics such as facial, iris, or fingerprint recognition. The identification may then be associated with the RF tag206in the user's possession.

The probabilistic graphical model module708is configured to use a probabilistic graphical model to determine possible values of the RF observations702and the IR observations704given an unknown position118. The model may be used to generate scores for the cells602, with the score being based on or proportional to one or more probabilities associated with of the observations. In some implementations the probabilities may be representative of probability densities. The probabilistic graphical model module708may also access at least a portion of the physical layout data336to access position information associated with the one or more sensors120. In some implementations, the data provided by the one or more sensors120may include the self-reported position of the sensor120.

The Viterbi decoder module710may process the resulting probabilities to determine the cell602having the greatest probability of containing the object116. Based on this, the cell602having the greatest probability of containing the object116is reported as the position118for the object116in the object position data126. As time progresses, the probabilistic graphical model module708receives and processes additional RF observations702and IR observations704. The probabilistic graphical model module708may also account for transition or movement of the object116from one cell602to an adjacent cell612, and the object position data126may be updated accordingly. Operation of the probabilistic graphical model module708is described next with regard toFIG. 8.

The data and observations described above are illustrated in tabular format for ease of illustration, and not by way of limitation. In other implementations, other data structures may be used. For example the data may be stored as linked lists, object database nodes, key-value pairs, and so forth.

FIG. 8illustrates the probabilistic graphical model module (model)708, according to some implementations. In this illustration shaded boxes indicate unknown values which the model708is configured to determine. Unshaded boxes indicate known values, such as the observations based on data from the sensors120. Should an observation be unavailable, a default value may be used, or the missing value may be omitted from the process.

This illustration depicts the model at two points in time, an initial time “T” and a subsequent time “T+dT”. While two points in time are depicted, it is understood that the process implementing this model may continue running as time progresses.

As illustrated here at802(1), the positions118of “M” objects at time T is a hidden state, or unknown. The goal of the model708is to determine a true cell602occupied by the object116at time T and subsequent times T+dT.

An RF model may determine a probability distribution conditioned on a true position of the center-of-mass of the object118based on the RSSI value for the RF receivers212. The RF model is depicted in this figure as the arrow pointing from the positions of the M objects at time T802(1) (designated as OM(T)) to multiple RF observations702(designated as RM(T)). Assuming the radiated power of the RF tag206is relatively consistent, the received strength of the RF signal208at the RF receivers212will be proportionate to the distance between the RF tag206and the antenna of the RF receiver212. For example, the RSSI will be greater when the RF tag206is 30 cm from the antenna of the RF receiver212compared to when the RF tag206is 2 meters from the antenna. The RSSI may vary based on the orientation of the RF tag206with respect to the RF receiver212. In some implementations, the model may account for these different orientations. Based on the RF observations702. The model may produce a probability distribution of RSSI for the RF receivers212. The probability distribution may be analyzed to reduce or eliminate the image of outlier measurements.

In this illustration an arrow extending from the object116positions118OM(T)802(1) to the IR(T)704(1) and from OM(T+dT)802(2) to IR(T+dT)704(2) represent an IR model for the IR values. The IR model is based on an assumption that when the object116is known to be in a given cell602, adjacent light beams508within some distance will be blocked with a high probability. For example, the light beam508for the cell602containing the center-of-mass of the object116will have a probability of being obscured or blocked close to 1. Similarly, there is some non-zero probability for the adjacent cells612to be obscured as well. In some implementations, the object data334may provide information associated with the size of the object116. In these implementations, the size may be used to determine the probability in the IR model. For example, where the object116comprises a tote210having a known length and width of 1 meter and the rows504are 15 cm in length along the aisle112, there is a high probability that the light beams508of at least six rows504will be obscured by the tote210.

In this illustration an arrow extending from the object116positions118OM(T)802(1) to the object116positions118OM(T+dT)802(2) represent a transition probability804model. The transition probability804model allows the object positioning module318to account for the movement of the object116within the facility102. The object116may transition from one cell602to another cell602within the grid with some probability. The transition may include remaining within a cell602or moving to an adjacent cell612. The system may be configured with a dT and a cell602size such that the object116may only transition to one of the cells602immediately adjacent. For example, where the cells602are arranged in a grid, the object116may remain in the occupied cell608or transition to one of the five adjacent cells612, as depicted inFIG. 6. Based on these constraints, these six cells depicted as the candidate cells610inFIG. 6have a high probability conditioned on a previous location O(T), while the remaining unoccupied cells606have a low or zero probability.

The IR model and the corresponding IR dependence provide a Boolean true/false (or high/low) structure. Based on this, the Viterbi decoder module710may solve OM(T) as a cell602having a maximum likelihood of being occupied by the object116at time instant T, given as input the RF observations at time T702(1) and the IR observations at time T704(1).

As time progresses to time T+dT additional observations may be acquired. It is unknown whether the object116remained stationary or moved, thus OM(T+dT)802(2) maintains a hidden state. The candidate cells610are considered as potential locations for the object116at the subsequent time T+dT. The model may be used to compute a score for each of the candidate cells610, to determine the position OM(T+dT)802(2).

As illustrated here, the IR observations at time T+dT704(2) may be used to determine a set of cells602, which the object116may be occupying. For example, the IR observations704(2) may be used to restrict a space of possible positions for the object116, by eliminating from consideration the cells602which are unoccupied. As described above, an unobscured light beam508at the time T+dT implies no object is in that cell602or row504, and may also imply no object116is present in the cells602adjacent thereto. Based on this, the model may assign a zero or very low score below a threshold for consideration indicating these cells are unoccupied cells606. The unoccupied cells606may thus be removed from a set of candidate cells610, and may be subsequently ignored for all objects116. The candidate cell610may thus comprise those cells602, not otherwise excluded by the IR observations704.

The model having taken the IR observations704into account may now apply the RF observations702. For each of the candidate cells610, a set of cells602adjacent to a particular candidate cell610is determined. The particular candidate cell610undergoing analysis may be designated as “G” and the cells adjacent thereto may be designated as “H”. For example, referring toFIG. 6, the occupied cell608located at row 5 in the left column is surrounded by the adjacent cells612. The adjacent cell612located at row 4 in the right column in turn has a set of adjacent cells612. Thus where G is the cell602at row 4, right column, the cells “H” are all of the cells602in rows 3, 4, and 5.

The object positioning module318may be configured to calculate a score for each G according to the following equation:

At any time instant, the object positioning module318outputs the cell602with a highest score of G (as computed above) as the most likely position118of the object116.

By using the techniques described above, the object positioning module318is able to determine the position118of one or more objects116within the facility102. The objects116may be in motion relative to the facility102, relative to one another, or both.

The object positioning module318may generate a map of the position118of each object116. The maps of different objects116may be analyzed to determine when objects116come together or separate, and to disambiguate between the objects116as they move adjacent to one another. For example, a first map is generated of a first user walking through the facility102, while a second map is generated of a second user walking through the facility102.

The object positioning module318is configured to provide object position data126for a plurality of objects116such as the users which may move past one another within the aisle112. For example, as the two users approach and finally pass one another, their positions as indicated by their respective maps over time, draw closer, overlap, or coalesce, and then separate. At the point of closest approach, a zone of confusion may exist within which the object positioning module318is unable to distinguish one user from another user, and the position thereof. The transition probability804model may be used to estimate the position118and relative motion over time of the object116within the zone of confusion.

The object positioning module318may then disambiguate between the two users as they separate based at least in part on the RF observations702. For example, the RSSI at an RF receiver212(1) at one end of the aisle112will increase as the RF tag206(1) worn by the first user approaches the RF receiver212(1). Similarly, the RSSI at another RF receiver212(2) located at an opposite end of the aisle112will increase as the RF tag206(2) worn by the second user approaches the RF receiver212(1). Based on the RF observations702, the users may be disambiguated from one another.

In another example, the object positioning module318may be configured to provide object position data126for a plurality of objects116moving down an aisle112in a group. For example two users may walk side by side down the aisle112. While the IR observations704may place the users within particular rows504, the column506in which a particular user is positioned may be disambiguated based on the RSSI data acquired from their respective RF tags206. For example, at the RF receiver212located on the left side of the aisle112, the RSSI will be greater for the RF signal208(1) from the RF tag206(1) of the user in the left column506then the signal208(2) from the RF tag206(2) of the user in the right column506.

Illustrative Processes

FIG. 9depicts a flow diagram900of a first process for determining a position118of an object116such as a user, according to some implementations. The process may be performed at least in part by the object positioning system124.

Block902accesses the first RF observations, such as RF observations702. As described above the RF observations702may comprise data indicative of a tag identifier received from the RF tag206and received signal strength information (RSSI) associated with reception of the RF signal208at the RF receivers212. The RF data328from which the RF observations702are produced may be received from one or more of the RF receivers212.

Based on the first RF observations, block904determines a first set of one or more cells in an aisle potentially occupied by the user. For example, based on known factors of the RF tag206and the RF receivers212, a distance between the RF receiver212and the RF tag206may be estimated. Using a known location of the RF receiver212as stored in the physical layout data336, the cells602within an area described by the distance may be determined.

Block906accesses first infrared information from a light curtain across an aisle, such as the active data330. As described above, the active data330may be obtained from the active IR transmitter/receiver pairs214. The active data330indicates whether the light beam508for the row504is unobstructed or obstructed with respect to the corresponding receiver.

Block908determines the one or more rows in the aisle occupied by the user based on the first infrared information. For example, when the pair214for row 5 indicates the light beam508is not received at the RF receiver, the user may be determined to be in row 5.

Block910accesses second infrared information from proximity sensors, such as passive data332. As described above, the passive data332may be obtained from the passive IR sensors216indicating proximity of the user. As described above, the passive IR sensors216may be arranged on both sides of the aisle112.

Block912determines one or more columns of the aisle occupied by the user based on the second infrared information. For example, passive data332may indicate the proximity of the user to the passive IR sensor216located on the left side of the aisle112. Based on this proximity, the user may be determined as being in the left column506.

Block914generates IR observations indicating the one or more cells potentially occupied based on the determined rows and determined columns. For example, the IR observations704may comprise a Boolean data structure in which each cell602is assigned a value of true or false indicative of a presence of the user.

Block916determines a second set of one or more cells potentially occupied by the user based on the RF observations and the infrared observations, wherein the second set is a subset of the first set.

Block918generates a score for each cell of the second set, wherein the score expresses a probability the cell is occupied by the user. In some implementations, the score may be calculated using the method described above with regard to Equation 1. For example, the score for a given cell602in the second set may comprise a sum of values for all adjacent cells612to the given cell602and including the given cell602, the value comprising a product of: an adjacency score indicative of probability of presence of the user in the adjacent cell612at a previous time, a transition score indicative of a probability the user moved from the adjacent cell612to the given cell602, and a probability of the RSSI having a certain value when the given cell602is the position of the RF tag.

Block920determines the cell having a highest score as position of the user. In some implementations the position may be expressed in terms of the cell602, such as aisle, row, and column, or as other coordinates or representations of physical location.

Block922determines an identity of the user based on a tag identifier. For example, the RF tag identifier received in the RF signal208may be used to search the object data334to determine a corresponding user account, username, and so forth.

Block924stores the identity of the user and the position. For example, the object positioning module318may generate the object position data126.

FIG. 10depicts a flow diagram1000of a second process for determining a position of an object116, according to some implementations. The process may be performed at least in part by the object positioning system124.

Block1002accesses non-optical information from one or more non-optical sensors. The non-optical sensors are configured to receive a non-optical signal from a tag associated with the object116and generate non-optical information. In one implementation, the non-optical sensors may include the RF receivers212configured to accept an RF signal208generated by an RFID tag206. In other implementations, the non-optical sensors may include microphones or other acoustic signal receivers, and so forth configured to accept an acoustic signal generated by an acoustic tag.

Block1004accesses optical information from the one or more optical sensors. The optical sensors are configured to optically detect a presence of the object116and generate optical information. In one implementation, the optical sensors may include the active IR transmitter/receiver pairs214, the passive IR sensors216, or both. In other implementations, the optical sensors may include microbolometers, imaging cameras, range cameras, laser scanners, and so forth. As described above, the microbolometer may be configured to detect infrared radiation associated with the object116, or detect occlusion by the object116of infrared radiation in the background.

Block1006determines probabilities of an object occupying one or more of a plurality of cells based on the non-optical information and the optical information. The probability determination may employ a model wherein the position118occupied by the object116is a hidden state and the optical information and the non-optical information comprise the observations used to determine the probability that the object116occupies one or more of the plurality of positions118. In some implementations, the model may produce a plurality of cells602having corresponding probabilities that the cells602are occupied. A Viterbi decoder may be used to solve for the one of the plurality of positions118having a maximum probability of containing the object116.

The determination of the probability may include calculating a transition probability indicative of a probability the object moves from a first position to a second position, wherein the second position is part of a set of positions adjacent to the first position. The determination of the probability may also include a previously calculated probability of the object116occupying the second position.

In some implementations the determination of the probability may include calculating a probability of detecting a particular received signal strength by a particular non-optical sensor given the tag at a particular position. For example, the probability may be expressed as an RSSI value given a particular RF receiver212and the RF tag206at a given position.

In some implementations, one or more of the size or shape of the object116may be determined. Manual entry, analysis of one or more two-dimensional images acquired by cameras, point cloud data acquired by a range camera or other three-dimensional input device, and so forth may provide information indicative of size and shape data of the object116upon entry to the facility102. The probability that the object116occupies one or more of the plurality of positions118may be based at least in part on one or more of the size or shape of the object116. For example, as described above, the size of the object116may be used to determine how many light beams508in the light curtain may be obstructed by the object116.

Block1008determines a position of the object based on the probabilities. For example, the cell having a highest probability of being occupied by the object116may be designated as the occupied cell608.

Block1010determines an identity of the object based on the non-optical information. For example, the RF identifier received from the RF tag206may be associated with a particular user or tote210. In some implementations, the identity of the object116may be determined based on information other than that acquired from the RF tag206. In one example, voice recognition may be used to identify a user.

In other implementations, the identity of the object116may be determined at least in part by mechanisms using optical information. For example optical object recognition may be used to identify an object116based on an image acquired by an imaging device such as a camera. In another example, a machine readable code may be read and used to provide identity information.

Block1012stores the position and the identity of the object as object position data126. In some implementations time of the position may also be stored. As described above, the object position data126may be accessed by other systems, such as the inventory management system122, time and attendance systems, and so forth.

FIG. 11depicts a flow diagram1100of a third process for determining position of an object, according to some implementations. The process may be performed at least in part by the object positioning system124.

Block1102determines a probability the object occupies a first set of positions. The probability may be based at least in part on RF data328gathered by a plurality of radio frequency (RF) receivers212receiving a RF signal208from an RF tag206associated with the object116. In some implementations positions118of a plurality of objects116may be disambiguated based at least in part on the RF data328from the plurality of RF receivers212.

Block1104determines a probability the object occupies a second set of positions, wherein the second set is a subset of the first set. The probability may be based at least in part on active data330, passive data332, or both, as gathered by a plurality of optical sensors. In some implementations the second set of positions118is a subset of the first set of positions118.

Block1106determines, for each of the positions in the second set, a score indicative of the object occupying the position. The score may be based on data gathered from sensors associated with the object116. For example, the object116may incorporate one or more motion sensors comprising one or more of an accelerometer, a gyroscope, or a magnetic field sensor. Motion sensor data from one or more motion sensors associated with the object116may be received and processed to determine movement data indicative of movement of the object116. The movement data may be used to generate a probability of the object116transitioning from one position118to another, such as from one cell602to an adjacent cell612. The determination of the score indicative of the object occupying the position may then be based at least in part on the motion sensor data.

In one implementation, the score may be calculated as described above with regard to Equation 1. This may include summing values for all positions118adjacent to and including the given position118, the value comprising a product of: an adjacency score indicative of probability of presence of the object116in the adjacent position118at a previous time, a transition score indicative of a probability of object116movement from the adjacent position118to the given position118, and a probability of a particular signal strength of the signal received from the tag when the given position118is the position of the RF tag.

Block1108determines the position associated with a highest score. For example, the scores may be sorted and the highest ranking score, selected.

Block1110stores the position having a greatest score as a position of the object116. As described above, and some implementations, the identity of the object116may also be determined.