Method For Collecting And Processing Relative Spatial Data

A method and system are disclosed for determining relative connectedness from temporal data. A user iterates through a list of items implemented on a mobile device. As each item on the list is located it is marked to generate a corresponding timestamp. The timestamps are then used to generate a timestamped list, which in turn is processed to determine the amount of elapsed time between each item on the list being located. The timestamped list data is then processed to generate relative connectedness data, which in turn is processed to generate a relative connectedness graph. The relative connectedness graph is then processed to assign coordinates to each item on the list. In turn, the coordinates are used to generate a map of the items.

DETAILED DESCRIPTION

FIG. 1is a block diagram of an exemplary client computer102in which the present invention may be utilized. Client computer102includes a processor unit104that is coupled to a system bus106. A video adapter108, which controls a display110, is also coupled to system bus106. System bus106is coupled via a bus bridge112to an Input/Output (I/O) bus114. An I/O interface116is coupled to I/O bus114. The I/O interface116affords communication with various I/O devices, including a keyboard118, a mouse120, a Compact Disk-Read Only Memory (CD-ROM) drive122, a floppy disk drive124, and a flash drive memory126. The format of the ports connected to I/O interface116may be any known to those skilled in the art of computer architecture, including but not limited to Universal Serial Bus (USB) ports.

Client computer102is able to communicate with a service provider server152via a network128using a network interface130, which is coupled to system bus106. Network128may be an external network such as the Internet, or an internal network such as an Ethernet Network or a Virtual Private Network (VPN). Using network128, client computer102is able to use the present invention to access service provider server152.

A hard drive interface132is also coupled to system bus106. Hard drive interface132interfaces with a hard drive134. In a preferred embodiment, hard drive134populates a system memory136, which is also coupled to system bus106. Data that populates system memory136includes the client computer's102operating system (OS)138and software programs144.

OS138includes a shell140for providing transparent user access to resources such as software programs144. Generally, shell140is a program that provides an interpreter and an interface between the user and the operating system. More specifically, shell140executes commands that are entered into a command line user interface or from a file. Thus, shell140(as it is called in UNIX®), also called a command processor in Windows®, is generally the highest level of the operating system software hierarchy and serves as a command interpreter. The shell provides a system prompt, interprets commands entered by keyboard, mouse, or other user input media, and sends the interpreted command(s) to the appropriate lower levels of the operating system (e.g., a kernel142) for processing. While shell140generally is a text-based, line-oriented user interface, the present invention can also support other user interface modes, such as graphical, voice, gestural, etc.

As depicted, OS138also includes kernel142, which includes lower levels of functionality for OS138, including essential services required by other parts of OS138and software programs144, including memory management, process and task management, disk management, and mouse and keyboard management. Software programs144may include a browser146and email client148. Browser146includes program modules and instructions enabling a World Wide Web (WWW) client (i.e., client computer102) to send and receive network messages to the Internet using HyperText Transfer Protocol (HTTP) messaging, thus enabling communication with service provider server152. In various embodiments, software programs144may also include a relative connectedness graphing system150. In these and other embodiments, the relative connectedness graphing system150includes code for implementing the processes described hereinbelow. In one embodiment, client computer102is able to download the relative connectedness graphing system150from a service provider server152.

The hardware elements depicted in client computer102are not intended to be exhaustive, but rather are representative to highlight components used by the present invention. For instance, client computer102may include alternate memory storage devices such as magnetic cassettes, Digital Versatile Disks (DVDs), Bernoulli cartridges, and the like. These and other variations are intended to be within the spirit, scope and intent of the present invention.

FIG. 2is a simplified spatial map of items on a list generated in accordance with an embodiment of the invention from temporal data provided by a user. In various embodiments, a user iterates through a list of items (e.g., a shopping list) implemented on a mobile device, such as a smart phone or tablet computer. As each item on the list is located it is either scanned or marked on the list by the user, which generates a corresponding timestamp. These timestamps, which include temporal data, are then respectively appended to each item to generate a timestamped list. In various embodiments, the user's mobile device is implemented with instrumentation capabilities to provide, and subsequently process, the temporal data to generate the timestamped list.

The resulting timestamped list is then processed to determine the amount of elapsed time between each item on the list being located by the user. In various embodiments, the user's mobile device is used to provide the timestamped list for processing. During the processing, timestamped list data associated with large timestamp intervals are discarded, as they indicate items that are unlikely to be in close proximity to one another. The method of determining the value of the large timestamp intervals is a matter of design choice. The remaining timestamped list data is then processed to generate relative connectedness data, which in turn is processed to generate a relative connectedness graph. The relative connectedness graph is then processed to assign coordinates to each item on the list. In turn, the coordinates are used to generate a map of the items. In various embodiments, the relative connectedness graph is used to convert relative location information to coordinate-based location information and back again. As used herein, a graph refers to a mathematical construct familiar to those of skill in the art.

Referring now toFIG. 2, a physical site has an entrance202, a fruit aisle204, a dairy aisle212, and an exit220. The fruit aisle204contains apples206, oranges208, and bananas210, while the dairy aisle212contains cheese214, yogurt216, and milk218. In this embodiment, a first user creates a list of items on a mobile device:

The first user then navigates to the entrance202of the physical site200to begin locating the items on their list. As each item is located it is either scanned or marked on the list by the first user, which results in the generation of a corresponding timestamp. These timestamps, which include temporal data, are then respectively appended to each item to generate a timestamped list:

The user then uses their mobile device to provide the timestamped list for processing to determine which items are likely to be near one another. For example, the timestamp interval between locating the apples206and locating the oranges208was 15 seconds, implying that they are likely close to one another. During the processing of the timestamped list, timestamped list data associated with large timestamp intervals are discarded, as they indicate items that are unlikely to be in close proximity to one another. As an example, the timestamp interval between locating the oranges208and locating the milk218is 2 minutes and 15 seconds. Therefore, the timestamp data associated with the milk218is discarded since it is unlikely that the milk218is located close to the oranges208or apples206. The method of determining the value of the large timestamp interval is a matter of design choice.

As described in greater detail herein, the remaining timestamp intervals are then processed to generate relative connectedness data, which in turn is processed to generate a relative connectedness graph. The relative connectedness graph turn is then processed to assign coordinates to each item on the list. In turn, the coordinates are used to generate a map of the items within the physical site200. Over time, other users provide their respective timestamped lists, which are likewise processed to improve the accuracy and coverage of the map. Those of skill in the art will recognize that errors and inefficiencies in the generation of the map can be reduced over time as new timestamped list data is received and processed.

For example, processing various timestamped lists may establish that the timestamp interval between locating the oranges208and locating the bananas210averages 10 seconds. Therefore, proximity is established for apples206, oranges208, and bananas210. In one embodiment, the proximity of the apples206, oranges208, and bananas210, all of which are fruit, implies that these items are located on a fruit aisle204. To continue the example, a second user may have created the following list of items on their connected device:

After locating the apples206on the fruit aisle204, the second user can be informed that the cheese214is on the dairy aisle212, which is proximal to the fruit aisle204. Once the cheese214is located, the second user can then be informed that both the yogurt216and the milk218are on the dairy aisle212as well. Once all items on the list are located, the second user leaves the physical site through exit220. In various embodiments, a coordinate system can be imposed upon the map of the physical site200for robotic or other computer-assisted navigation. Skilled practitioners of the art will recognize that the invention has many possible applications and that the foregoing grocery shopping metaphor is not intended to limit the spirit, scope or intent of the invention.

FIG. 3is a simplified spatial map of a physical site implemented in accordance with an embodiment of the invention. In this embodiment, the physical site300includes a starting point302, an ending point308, nine aisles ‘A’ through ‘I’304, each of which includes eight items ‘0’ through ‘7’306. For simplicity, it is assumed that the items ‘0’ through ‘7’306are accessible from both sides of aisles ‘A’ through ‘I’304.

As described in greater detail herein, computing systems typically process spatial data as a series of Cartesian coordinates. Humans, however, use the much more flexible concept of relative placement—the pencils are near the phone, the milk is near the Ranch Dressing in the refrigerator. Furthermore, implementing Cartesian-based systems is undesirable in many situations due to their intrinsic cost and complexity. For example, wiring a retail store or warehouse, such as physical site300, with indoor telemetry equipment that could be used by robotic or human-interfacing computers could be prohibitively difficult, costly, or both.

In various embodiments, as likewise described in greater detail herein, human-facing list systems are instrumented with a coordinate system to provide both coordinate-based and relative placement descriptions of item locations. In these embodiments, the item locations are determined through the use of modest computing resources typically associated with mobile devices.

In various embodiments, these item locations are expressed as a mathematical graph. As shown inFIG. 3, the graph may be rendered as a directed graph. However, direction information is not relevant to the information represented except in the case of randomized shopping trips described in greater detail herein. Furthermore, in certain embodiments, the graphs can be combined with coordinates to improve accuracy. As a result, graphs of environments, such as the physical site300shown inFIG. 3, benefit from human intelligence and can be used to provide an approach to various graph problems. As an example, with repeated navigation, humans typically find relatively efficient ways to traverse the distance separating the location of two items. If the time to traverse the distance is recorded, and the velocity of the traversal can be estimated, then the relative connectedness of the two items can be determined.

FIG. 4is a simplified graph of randomized lists implemented in accordance with an embodiment of the invention for sequentially locating a subset of the items depicted in the map ofFIG. 3. In this embodiment, a plurality of randomized lists (e.g., 1,000) are generated, each of which contain a subset of the 72 available items depicted in the map ofFIG. 3. The randomized lists are then assigned to a predetermined number of users, who in turn use the randomized lists to sequentially locate the items they contain. For clarity, only eight of the randomized lists are shown inFIG. 4.

As each item on the randomized list is located, it is either scanned or marked on the list by the user, which generates a corresponding timestamp. These timestamps, which include temporal data, are then respectively appended to each item in the randomized list to generate a timestamped randomized list. An example of a timestamped randomized list is as follows:

As shown above, each step of the example randomized list encodes the current item (“node”), the previous item, the time it took to navigate between them, and the total time of the randomized list at that step. During processing, all information is discarded except the name of the items and the length of the time step. In this embodiment, a simple algorithm is implemented to compute the time steps where traversing items within an aisle takes five seconds and traversing an aisle takes ten seconds when the user is at the end of an aisle as depicted inFIG. 3. As likewise depicted inFIG. 3, the user travels to the end of the next closest aisle when the next item on the randomized list is not in the current aisle.

From the foregoing, it will be appreciated that little useful information can be gleaned from this excess of information, excluding perhaps which items are most popular. Certainly no useful information regarding the location of items, either relatively or absolutely, can be determined. However, as described in greater detail herein, additional information regarding the arrangement of items in the physical site300ofFIG. 3can be combined with the graph400shown inFIG. 4.

FIGS. 5aand5bshow one grouping of the individual items depicted in the simplified graph ofFIG. 4into a plurality of subgraphs implemented in accordance with an embodiment of the invention. As shown inFIG. 5a, the individual items depicted in the simplified graph ofFIG. 4have been grouped into a plurality of subgraphs500, each of which correspond to a predetermined aisle ‘A’ through ‘I’304depicted inFIG. 3.FIG. 5bshows a cropped view ofFIG. 5afor additional clarity. However, this cropped view of the graph data shown inFIG. 5areveals that very little of the intrinsic structure of the data is apparent without performing additional processing of the data resulting from the randomized list operations depicted inFIG. 4.

FIG. 6shows another grouping of the individual items depicted in the simplified graph ofFIG. 4into a plurality of subgraphs implemented in accordance with an embodiment of the invention. In this embodiment, the order of the items within each aisle ‘A’ through ‘I’304depicted inFIG. 3is added to the graph shown inFIG. 5. As shown inFIG. 6, the randomized list navigation data simply results in a confused graph where it is not possible to determine which order the aisles would be in ordinarily, despite the foreknowledge that the aisles ‘A’ through ‘I’304are depicted in alphabetical order inFIG. 3. For example, aisle ‘B’ is shown to be located between aisle ‘F’ and ‘H’ in the subgraphs600instead of between aisle ‘A’ and ‘C’ as depicted inFIG. 3. Furthermore, as shown inFIG. 6, humans would not be able to navigate across the aisles ‘A’ through ‘I’304depicted inFIG. 3as shown by the subgraphs600inFIG. 6.

FIG. 7shows yet another grouping of the individual items depicted in the simplified graph ofFIG. 4into a plurality of subgraphs implemented in accordance with an embodiment of the invention. Skilled practitioners of the art will recognize that working with data in the form of a graph poses both challenges and advantages. While existing algorithms for graph data (e.g., “optimal” navigation algorithms) may be used, graphs become more and more complex as the number of nodes increases. Therefore, it is advantageous for algorithms dealing with graph data to be able to process incoming data in linear time.

This issue is addressed in various embodiments by implementing an algorithm that discards data where the time step interval exceeds a predetermined value. In this embodiment, the time step interval value is selected to be equivalent to the hypotenuse of the minimal intra-aisle/inter-aisle navigation, or sqrt(5̂2+10̂2). As a result, the subgraphs700shown inFIG. 7provide the ability for a human to navigate the aisles ‘A’ through ‘I’ depicted inFIG. 3. However, the order of the items within each of the aisles ‘A’ through ‘I’304depicted inFIG. 3is not accurately depicted. As an example, it is not clear that item ‘A1’ is between items ‘A0’ and ‘A2.’

FIG. 8shows still yet another grouping of the individual items depicted in the simplified graph ofFIG. 4into a plurality of subgraphs implemented in accordance with an embodiment of the invention. In this embodiment, the essence of the positional data is captured and expressed from a mathematical perspective through the implementation of the following algorithm.

As a result, the majority of the subgraphs800accurately depict the order of the items within each of the aisles ‘A’ through ‘I’304depicted inFIG. 3. While the implementation of this algorithm does not result in a perfect depiction, discrete aisles are visible, particularly aisles ‘C’, and ‘F’ through ‘I’. However, the algorithm does not appear to have determined that items ‘D4’ and ‘D5’ are next to one another although they are by definition. Nonetheless, they are still represented within the subgraphs800as relatively close. Imposing knowledge of the aisles ‘A’ through ‘I’304depicted inFIG. 3further clarifies the arrangement and depiction of the subgraphs800. It will be appreciated that while errors are present in the subgraphs800, the overall depiction is useful in obtaining an understanding of the data contained therein.

It will likewise be appreciated that the implementation of the randomized lists described in greater detail herein are truly random and take no advantage of the intelligence a human would typically apply in a real-world scenario. Furthermore, the number of lists needed to accurately depict the items within the subgraphs800would likely decrease as the users shoppers would typically locate the items on their list in a time-efficient manner. Moreover, even if a given user did not have knowledge of a predetermined physical site, they would generally realize that similar items (e.g., apples, oranges and other fruit) would be proximal while dissimilar items (e.g., bread and bath soap) are unlikely to be proximal to one another.

From the foregoing, it will be appreciated that the graph information depicted in the subgraphs800could be converted into other useful expressions in various ways. For example, human-friendly descriptions could be provided to a user of an intelligent application implemented on a mobile device. To further the example, if the user asks where the bananas are, the mobile device may be able to respond that they are near the cherries the user just located. Such an application could apply graph techniques to assist in navigation, or in a shopping metaphor, simply organize items in the order a shopper would be able to locate them most quickly. Other sorts of user-driven navigation scenarios are easily imagined, such as item picking in warehouses.

Likewise, by implementing coordinates at the edges of the graph, a computing device may be able to produce approximate coordinates for other items based upon making various assumptions of locations of items relative to other items in the graph. It will be appreciated that the ability to produce approximate coordinates calculated from fuzzier, human-instrumented data collection might be desirable in situations where robots need to interact with humans.

FIGS. 9aand9bare a generalized flowchart of operations implemented in accordance with an embodiment of the invention for performing relative connectedness graphing operations. In this embodiment, relative connectedness graphing operations are begun in step902, followed by a user using a mobile device in step904to generate a list of items to locate in a target physical site. An item on the list is then located by the user in step906, followed by processing temporal data to generating a timestamp for the located item in step908as described in greater detail herein.

The resulting timestamp is then appended to the corresponding item on the list in step910, followed by a determination being made in step912whether to locate another item on the list. If so, the process is continued, proceeding with step906. Otherwise, the timestamped list is provided for processing in step914. Timestamped list data is then processed in step916, as described in greater detail herein, to generate timestamp intervals. Timestamped list data corresponding to timestamp intervals larger than a predetermined value, as likewise described in greater detail, is then discarded in step918.

A determination is then made in step920whether a relative connectedness graph currently exists for the target physical site. If not, then the remaining timestamped list data and corresponding timestamp intervals are processed in step922to generate new relative connectedness data, which in turn is processed on step924to generate a new relative connectedness graph for the target physical site. Otherwise, timestamped list data and corresponding timestamp intervals associated with an existing relative connectedness graph is retrieved for the target physical site in step926. The remaining and retrieved timestamped list data, along with corresponding timestamp intervals, are then processed in step928to generate updated relative connectedness data, which in turn is processed in step930to generate an updated relative connectedness graph for the target physical site. Once the new or updated relative connectedness graph is respectively generated in step924or930, a determination is made in step932whether to end relative connectedness graphing operations. If not, then the process is continued, proceeding with step904. Otherwise, relative connectedness graphing operations are ended in step934.