Location system

• US 6,718,278 B1
• Filed: 12/11/2000
• Issued: 04/06/2004
• Est. Priority Date: 06/11/1998
• Status: Expired due to Term

• Current Assignee: AT&T Istel (AT&T, Inc.)
• Original Assignee: AT&T Laboratories-Cambridge Limited (AT&T, Inc.)
• Inventors: Steggles, Peter Joseph
• Primary Examiner(s): Barlow, John
• Assistant Examiner(s): BHAT, ADITYA S
• Application Number:
  US09/719,300
• Time in Patent Office: 1,212 Days
• Field of Search: 702/150, 342/357, 324/331, 340/573, 367/117
• US Class Current: 702/150
• CPC Class Codes: G01S 15/872 Combination of several systems for attitude determination using inertial means G01C9/00, control of attitude G05D1/49
• CPC Class Codes: G01S 15/876 Combination of several spaced transmitters or receivers of known location for determining the position of a transponder or a reflector G01S15/872 takes precedence
• CPC Class Codes: G01S 5/186 Determination of attitude using inertial means G01C9/00; control of attitude G05D1/49
• CPC Class Codes: G01S 5/30 Determining absolute distances from a plurality of spaced points of known location

Abstract

A location system for objects having location devices (16) as a means for repeatedly interrogating the location devices on each object to provide position signals. A means (18) to detect the position signals are provided. The position of each object and the area associated with each object are determined from the position signals and stored. The system is then able to determine the relative locations of the thus determined objects and associated areas.

Claims

1. A method for determining whether interaction may occur between objects, at least some of which include a position indicator, said method comprising the steps of:

associating a predefined area with each of said objects; and

repetitively determining whether a predetermined relationship between the areas of said objects is fulfilled, wherein this step of determining comprises repeatedly executing the sub-steps of;

(a) determining location of each of the objects that has said position indicator;

(b) determining location of the area associated with each object whose location is determined in step (a), from location of its associated object;

(c) storing the area data for each object whose area is determined in step (b); and

(d) evaluating the predetermined relationship between the areas associated with each object, using the stored associated area data, to determine whether or not interaction may occur.

2. A method according to claim 1, wherein the predetermined relationship between areas is the containment of one area by another.

3. A method according to claim 1, wherein the predetermined relationship between areas is the failure of one area to contain another area.

4. A method according to claim 1, wherein the predetermined relationship is the overlapping of one area by another area.

5. A method executed in a computer comprising the steps of:

(a) for a first object of a plurality of objects, obtaining an interaction space, within a base space, that is associated with said first object, the interaction space defined as a set of squares in a hierarchical tree of squares;

(b) for a second object of said plurality of objects, computing an interaction space within said base space that is associated with said second object and which follows movement of said second object, the interaction space defined as a set of squares in a hierarchical tree of squares;

(c) determining a spatial relationship between said first object and said second object by comparing said interaction space of said first object with said interaction space of said second object, and assessing whether said interaction space of said first object overlaps contains, or is contained by said interaction space of said second object, which corresponds to a non-null logical intersection between said interaction space of said first object and said interaction space of said second object with a goal of establishing a non-null working relationship between said first object and said second object; and

(d) repeating steps (b) arid (c).

6. The method of claim 5 where said obtaining in step (a) is accomplished by retrieving said interaction space from memory, or by computing said interaction space.

7. The method of claim 5 where said space is a two dimensional space.

8. The method of claim 5 where said step of determining considers whether there exist squares in said set of squares identified in step (a) that are not also founding said set of squares identified in step (b), and vice versa.

9. The method of claim 5 where said step (b) is executed by operating on a signal received from each of one or more signal sources that arc physically coupled to said second object.

10. The method of claim 9 where said step (d) is executed whenever a new signal is received from said one or more signal sources of said second object.

11. The method of claim 10 where said signal received from each of said one or more signal sources is received in response to an interrogation of said one or more signal sources.

12. The method of claim 9 where said step (a) is executed by operating on a signal received from each of one or more signal sources that are physically coupled to said first object, and said step (d) executed whenever a new signal is received from said one or more signal sources of said second object or, inclusively, from said one or more signal sources of said first object.

13. The method of claim 5 where said step of determining employs an algorithm that focuses on change in said interaction space of said first object indicative of movement of said first object, and change in said interaction space of said second object indicative of movement of said second object, in order to determine whether spatial relationship between said first object and said second object changes in character.

14. The method of claim 5 where said step (b) comprises repeatedly interrogating one or more signal sources that are coupled to said second object.

15. The method of claim 14 where said step (a) comprises repeatedly interrogating one or more signal sources coupled to said first object.

16. The method of claim 5 further comprising a step of taking action said step of determining ascertains that said spatial relationship changes state, from a null interaction to a non-null intersection, or vice versa.

17. The method of claim 16 where said first object is a computer terminal, and said second object is an object carried by a person.

18. The method of claim 17 where said action relates to providing computing services to said person.

19. A method comprising the steps of:

(a) obtaining static information about objects in a location;

(b) receiving information relating to position of said objects and interrogating said objects by pinging said objects with an active signal from a set of signals that includes ultrasound;

(c) calculating maximum cover for at least some of said objects to obtain a set of quadtree cells for each of said objects;

(d) ascertaining containment/overlapping index for each of said sets of quadtree cells; and

(e) updating a memory with said ascertained indices.

20. The method of claim 19 further comprising a process of repeating steps (b) through (d).

21. The method of claim 19 further comprising a process of executing a predetermined program related to a first object, in a second object that comprises a processor, when the index associated with said second object indicates that the quadtree cells set associated with said first object contains, is contained by, or overlaps, the quadtree cells set associated with said second object.