`[19]
`[11] Patent Number:
`5,806,017
`
`Hancock
`[45] Date of Patent:
`Sep. 8, 1998
`
`U8005806017A
`
`[54] ELECTRONIC AUTOROUTING
`NAVIGATION SYSTEM FOR VISUALLY
`IMPAIRED PERSONS
`
`2 661 607
`WO 95/04440
`
`France.
`11/1991
`2/1995 WIPO.
`
`OTHER PUBLICATIONS
`
`Inventor: Michael B. Hancock, Galveston, Tex.
`
`Assignee: Board of Regents The University of
`.
`Texas System, Austin, Tex.
`
`Yevvman, The Seeing—Eye BOX’ Blamedzcal Inquzry, The
`UniverSity of Texas Medical Branch at Galveston, Spring
`1996
`
`Appl. No.: 699,580
`.
`.
`Aug. 19’ 1996
`Flled'
`Int. Cl.6 .......................... G01C 21/00; G06F 165/00
`
`............................................. 701/209; 701/211
`US. Cl.
`Field of Search ................................. 364/443, 444.1,
`364/4442, 448, 449.2, 449.3, 449.5; 701/200,
`201, 202, 206, 208, 209, 211
`
`References CltEd
`US. PATENT DOCUMENTS
`
`9/1963 Strauss et a1.
`.............................. 35/25
`3,104,478
`
`2/1973 Mowat
`..........
`340/1 R
`3,718,896
`5/1977 Travf’wka 1H ~~
`- 343/65 LC
`4:025:92
`
`" 343/113 PT
`8/1977 Daptran """""
`470457799
`
`"
`10/1978 Moncca et al’
`340/407
`4’119’811
`3/1980 Reymond et a1.
`356/152
`4,193,689
`
`
`3/1987 Ban et al. ................ 356/4
`4,648,710
`4/1987 Osaka .
`340/407
`4 660 022
`
`2/1990 Sato ......
`340/825.57
`4,904,993
`
`6/1990 Friedman ..
`367/118
`4,935,907
`
`
`7/1991 Friedman ..
`434/112
`5,032,083
`.......................... 340/325.71
`7/1991 Ono et al.
`5,032,836
`11/1991 Person ..................................... 364/444
`5,067,081
`
`9/1992 Alonmetal‘
`340/825‘49
`571447294
`
`5/1993 verSter """
`340572
`5’214’410
`
`4/1995 Lima .....
`364/449
`5,406,491
`1/1996 Kelk ........................................ 434/112
`5,487,669
`4/1996 Silverman ............................... 340/944
`5 508 699
`2/1997 Dunn et al.
`............................... 379/59
`5,600,706
`FOREIGN PATENT DOCUMENTS
`
`Primary Examiner—Michael Zanelli
`Assistant Examiner—Edward Pipala
`Attorney, Agent, or Firm—Arnold, White & Durkee
`
`[57]
`
`ABSTRACT
`
`The present invention is an autorouting navigation system
`for directing one or more visually impaired persons to a
`physical location. The present invention includes a portable
`autorouting navigation unit that includes an input device for
`selecting a target locationcorresponding to a phys1cal loca-
`tion of a plurality of location beacons, a receiver configured
`to receive signals from the location beacons, a memory
`storing information correlating the locations of the location
`beacons, and an output device for communicating with the
`user. A microcontroller or microprocessor under program
`control
`rocesses the si nals received from the location
`b
`1
`th
`g.
`1
`d
`1 t.
`d t
`d
`p
`eaC°n§> am We?
`056 51g“ S a“
`for“? a 10“
`a3; a“
`determines a routing path from the user s present pos1tion to
`the target location. The microcontroller may also provide an
`indication, such as an audible sound, to the user of Whether
`or not the user is following the routing path to the target
`location. Significantly,
`the present
`invention relies upon
`beacons that send out location and direction information
`Without being polled by the portable unit determines a
`routin
`ath that allows for autoroutin Beacons ma
`also
`b
`g p.
`d .
`f b
`it
`lyt
`t
`eacons
`6 organlze
`1“ groups 0
`a 8m cor.” ?‘ e 0
`geographlcal landmarks SUCh as hallways m a bmldlng to
`reduce the size of the correlating data stored in the memory
`of the portable unit and thereby reduce processing time.
`
`0 338 997 10/1989 European Pat. Off.
`
`.
`
`15 Claims, 10 Drawing Sheets
`
`1,2,9,1 12,1111
`
`504
`
`>3?
`1,2,92 12,102
`
`502
`
` T<
`
`
`
`
`
`500
`
`503
`
`506
`
`1
`
`APPLE 1006
`
`APPLE 1006
`
`1
`
`
`
`US. Patent
`
`Sep. 8,1998
`
`Sheet 1 0f 10
`
`5,806,017
`
`MO
`
`
`
`
`3X4 MATRIX
`KEYPAD
`
` TFM85400
`INFRARED DETECTOR
`MODULE
`
`195
`
`102
`
`
`
`
`
`103
`
`
`
`
`PARALLAX
`
`MICRO CONTROLLER
`
`
`
`
`BSII
`
`NiCd/NIMH
`BATTERY
`
`105
`
`EARPHONE
`
`INFORMATION STORAGE
`
`DEVICES ISDZSOO
`VOICE STORAGE IC
`
`1134
`
`FIG. 1A
`
`2
`
`
`
`US. Patent
`
`Sep. 8,1998
`
`Sheet 2 0f 10
`
`5,806,017
`
`151
`
`152
`
`15g
`
`\
`
`159
`
`
`
`156
`
`153
`
`154
`
`155
`
`158
`
`157
`
`FIG. 1B
`
`3
`
`
`
`US. Patent
`
`Sep. 8,1998
`
`Sheet 3 0f 10
`
`5,806,017
`
`
`
`EXTERNAL 12V
`POWER SUPPLY
`
`
`
`
`
`
`
`PARALLAX BSI
`MICRO CONTROLLER
`
`WITH INTERNAL
`LM7805 VOLTAGE
`REGULATOR
`
`
`
`
`
`207
`
`
`
`SHARP GL528
`
`
`
`INFRARED LED'S
`
`MAIN BEACON
`
`
`SHARP GL528
`INFRARED LED'S
`
`MAIN BEACON
`
`
`
`
`
`L POWER
`AMPLIFIER
`
`. POWER
`AMPLIFIER
`
`206
`
`263
`
`
`
`SHARPGL528
`
`230
`
`/_I
`
`-—--———.
`~----
`
`
`
`INFRARED LED
`
`AUXILIARY BEACON
`
`
`
`231
`
`II
`
`FIG. 2A
`
`4
`
`
`
`US. Patent
`
`Sep. 8,1998
`
`Sheet 4 0f 10
`
`5,806,017
`
`259
`
`254
`
`5
`
`
`
`US. Patent
`
`Sep. 8,1998
`
`Sheet 5 0f 10
`
`5,806,017
`
`ROOM12
`
`310
`
`
`FIG. 3
`
`6
`
`
`
`US. Patent
`
`Sep. 8,1998
`
`Sheet 6 0f 10
`
`5,806,017
`
`400
`
`1,1,12,2
`
`
`
`FLOOR
`
`HALLWAY
`
`ID
`
`DIRECTOR
`
`w
`
`4%
`
`w
`
`433
`
`FIG. 4
`
`7
`
`
`
`US. Patent
`
`Sep. 8,1998
`
`Sheet 7 0f 10
`
`5,806,017
`
`1,2,9,1 12,113,1'
`
`1,2,7,1
`
`1,2,8,1
`
`N<
`
`>00
`
`1,2,7,2 12,82
`
`
`
`5Z0
`
`FIG. 5A
`
`8
`
`
`
`US. Patent
`
`Sep. 8,1998
`
`Sheet 8 0f 10
`
`5,806,017
`
`593
`
`5Q4
`
`>3)
`km 13,131
`<r<
`
`5213
`
`
`
`506
`
`9
`
`
`
`US. Patent
`
`Sep. 8, 1998
`
`Sheet 9 0f 10
`
`5,806,017
`
`601
`
`POWER
`
`
`
`
`ACTIVE VOICE
`
`STORAGE IC-
`“ENTER TARGET
`
`CODE NUMBER“
`
`602
`
`60D
`
`6256
`
`C)
`
`
`
`
`
`
`
`
`BEACON
`
`AND TARGET FLOOR
`NUMBERS
`
`MMCH;
`
`
`
`
`
`
`ACTIVATE VOICE
`
`
`BEACON
`STORAGE IC - “TARGET
`
` YES
`
`AND TARGET
`ON DIFFERENT FLOOR
`
`
`
`HALLWAY NUMBERS
`ROUTING TO
`MATCH?
`STAIRWA “
`
`
`
`OBTAIN SET OF HALLWAY
`NUMBERS AND
`
`DIRECTIONS FROM
`LOOKUP TABLES THAT WILL
`
` ROUTE USER TO TARGET.
`
`NO
`
`
`BEACON AND
`TARGET ID NUMBERS
`MATCH?
`
`
`
`
`
`
`
`
`BEACON
`
`NO
`DIRECTOR=O? TARGE
`
`
`AUXILIARY BEACON
`
`DETECTED?
`
`
`
`TR'EbEgBNE
`
`
`SWGLETONE
`BURST
`
`SET STORAGE CODE
`NUMBER:
`STAIRWAY CODE
`
`
`
`
`
`NUMBER
`
`
`
`
`
`
`
`
`COB
`
`
`
`
`BEACO
`HALLWAY
`
`NUMBER=MEMBER 0F
`LINKING SET?
`
`
`
`
`
`YES
`
`ENGLETONE
`BURST
`
`618
`
`619
`
`FI(3.I3/\
`
`10
`
`10
`
`
`
`US. Patent
`
`Sep.8,1998
`
`Sheet 10 0f 10
`
`5,806,017
`
`
`BEACON ID
`NUMBER >TARGET ID
`
`
`NUMBER?
`
`
`
`
`
`
`BEACON
`BEACON
`DIRECTOR = 2?
`POLARITY = 1?
`
`
`
`
`
`
`
`SINGLE TONE
`BURST
`
`621
`
`SINGLE TONE
`BURST
`
`62G
`
`FIG. BB
`
`11
`
`11
`
`
`
`1
`ELECTRONIC AUTOROUTING
`NAVIGATION SYSTEM FOR VISUALLY
`IMPAIRED PERSONS
`BACKGROUND OF THE INVENTION
`
`invention relates to systems for guiding
`The present
`visually impaired individuals so that
`they may achieve
`greater independence in reaching desired destinations or
`targets, particularly in unfamiliar buildings.
`Various methods and systems have been devised to aid
`visually impaired persons in guiding themselves through
`unfamiliar surroundings. From such early and crude devices
`as the long cane have evolved electronic systems that
`provide audible or tactile stimuli as guide indicators for the
`visually impaired. For example, traffic signals have been
`developed that produce sounds to inform visually impaired
`persons about traffic signal states.
`More sophisticated systems have also evolved, such as
`that disclosed by Osaka, US. Pat. No. 4,660,022, in which
`the user carries a transmitter control unit
`that activates
`
`location indicators. By actuating the transmitter control unit,
`the user causes a control signal
`to be transmitted to a
`receiver that is placed near a desired location. Upon recep-
`tion of the control signal, the receiver emits an audio signal
`that guides the user to the desired location. Although this
`system may effectively guide the user toward a desired
`destination,
`it has two significant drawbacks: (1) a loud
`audio signal is produced at the target, which may be dis-
`tracting to others in the vicinity; and (2) the system employs
`polling which does not accommodate multiple users because
`the user does not know whether or not someone else is
`
`activating the audio signal, and because simultaneous poll-
`ing transmissions mutually interfere.
`Another system is shown in US. Pat. No. 4,935,907 to
`Friedman. This system is an electronic homing system for
`directing a user to a plurality of objects. The system includes
`a plurality of remote modules and a portable module. The
`remote modules transmit an uncoded omnidirectional ultra-
`
`sonic signal in response to a coded request signal sent from
`the portable unit. The portable unit receives the ultrasonic
`signal binaurally, and converts differences in the time of
`arrival of the ultrasound reaching the detectors into an
`audible signal that guides the user to the desired remote
`module. Again, this system requires that the portable unit
`actively poll the remote modules, that the remote modules
`send back a signal in response to that polling, and that the
`portable unit receive a response signal. This requirement of
`polling creates significant problems with multiple users.
`Furthermore, in such a system, for a user to reach a remote
`module that
`is not presently near the user,
`there must
`generally be provided relay modules, or repeaters, which
`convey the signal from the activated remote module through
`several rooms or corridors to the user. Guidance or naviga-
`tion systems that use polling may be acceptable for single
`users, but they are virtually useless in multiple user areas,
`such as in rehabilitation centers and schools for visually
`impaired persons, because simultaneous polling transmis-
`sions from multiple users result in mutual interference and
`cause erratic and non-specific beacon activation. This is
`likely the reason why prior systems have not achieved
`commercial success.
`
`An object of the present invention is to overcome these
`problems with prior systems, and provide an electronic
`navigation system capable of simultaneously directing any
`number of visually impaired users to a plurality of locations,
`and in particular to locations within a building, between
`buildings on a campus, or within a small neighborhood.
`
`5,806,017
`
`2
`SUMMARY OF THE INVENTION
`
`The present invention contemplates an autorouting navi-
`gation system for directing one or more visually impaired
`persons to a physical location. In partial respects, the present
`invention includes a portable autorouting navigation unit
`having an input device (e.g., a keypad) for selecting a target
`location corresponding to a physical location of a plurality
`of location beacons, a receiver configured to receive signals
`from the location beacons, a memory that stores information
`correlating the locations of the location beacons, and an
`output device for communicating with the user.
`In one significant respect,
`the present invention relies
`upon location beacons that send out location and direction
`information without being polled by a portable unit from any
`single user. More specifically,
`the present invention may
`utilize location beacons that transmit digitally-modulated
`infrared (IR) signals without being polled by a portable unit
`from any user. The system, therefore, is passive (i.e., it does
`not use polling). The IR signals transmitted by the location
`beacons include digital location and direction information
`about
`the physical
`location of a beacon and about
`the
`direction of travel of the user relative to the beacon. The
`
`10
`
`15
`
`20
`
`25
`
`signals may be received by any portable unit held by one of
`a plurality of users when that user is within range of the
`beacon.
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`In more detailed respects, the location beacons may be
`grouped according to geographical subdivisions, such as
`hallways in buildings. The microcontroller within a portable
`unit may be programmed to use several logic statements
`along with beacon correlation or lookup tables to determine
`a set of intermediate or way-point beacons by which the user
`is routed to the desired location beacon (i.e.,
`the target
`beacon).
`In this manner,
`the present
`invention may be
`autorouting and provide a routing path to guide the user from
`beacon to beacon to the user’s ultimate destination.
`
`In another respect, the autorouting navigation system of
`the present invention includes a plurality of location beacons
`positioned at a plurality of physical locations and at least one
`portable navigation unit. The location beacons emit signals
`including information representative of physical locations of
`the location beacons. Each location beacon includes a trans-
`
`mitter for emitting the signal, and a control means for
`causing the transmitter to emit
`the signal. The portable
`navigation unit includes an input device for selecting a target
`location, a receiver configured to receive signals from the
`location beacons, a memory storing correlation data linking
`the location beacons together, an output device, and a
`control means. The control means may be a microcontroller
`under program control and is electronically coupled to the
`input device, the receiver, the memory and the output device.
`The control means processes the signals from the location
`beacons and analyzes the correlation data to determine a
`routing path to the target location. The control means also
`causes the output device to indicate to a user that the user is
`following the routing path to the target location.
`In a further embodiment, the plurality of location beacons
`are organized into a plurality of groups of location beacons
`and the correlation data links the plurality of groups of
`location beacons. Also, the signal emitted by the location
`beacons within a group of location beacons may include
`information identifying the location beacon within the loca-
`tion beacon’s respective group. Each beacon may also have
`a plurality of transmitters providing at least two transmission
`directions. In particular, the two transmission directions may
`be separated by over 90°. The beacons may also be orga-
`nized into groups, and each group of location beacons may
`12
`
`12
`
`
`
`5,806,017
`
`3
`include a master beacon and a plurality of slave beacons,
`which are controlled by the master beacon. The beacons may
`also emit
`infrared (IR) signals, and the receiver of the
`portable navigation unit may be constructed to receive the
`infrared signals.
`In another respect, the present invention is a method of
`automatically routing at least one visually impaired person
`to a target
`location. This method includes the steps of
`positioning a plurality of location beacons at physical
`locations, generating correlation data linking the location
`beacons, storing the correlation data within a portable navi-
`gation unit,
`inputting a target
`location into the portable
`navigation unit, determining with the portable navigation
`unit a routing path to the target location, scanning with the
`portable navigation unit to detect a signal from at least one
`of the plurality of location beacons, determining with the
`portable navigation unit whether the signal corresponds to
`the routing path, and providing an output signal indicating to
`a user whether the user is proceeding along the routing path
`to the target location. In further respects, the plurality of
`location beacons may be positioned at physical locations
`within the interior hallways of a building.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1A is a block diagram of connections for the basic
`components of a portable navigation unit (e.g., an infrared
`receiver/microcontroller (IRRM)) according to the present
`invention.
`
`FIG. 1B is a diagram of external features for a portable
`navigation unit (e.g., IRRM) according to the present inven-
`tion.
`
`FIG. 2A is a block diagram of connections between
`components of a main location beacon and an auxiliary
`location beacon for identifying physical locations, according
`to the present invention.
`FIG. 2B is a diagram of external features for a main
`location beacon and an auxiliary location beacon according
`to the present invention.
`FIG. 3 is a diagram showing an example of how a main
`location beacon and an auxiliary location beacon may be
`located at a doorway, according to the present invention.
`FIG. 4 shows an example transmission, including four
`code numbers, from one side of a main location beacon and
`shows the function identified for each of the four code
`numbers.
`
`FIGS. 5A and 5B are a diagram showing an example floor
`plan for a building, the position of location beacons, the
`respective sets of code numbers for each location beacon,
`and the route of a user.
`
`FIGS. 6A amd 6B are a flowchart of an example search
`algorithm that may be used by the programmable portable
`navigation unit, according to the present invention.
`DETAILED DESCRIPTION
`
`invention contemplates an electronic,
`The present
`microcontroller-based, autorouting navigation system
`capable of simultaneously directing one or more blind users
`to a plurality of locations. The present invention may include
`a plurality of beacons (e.g., microcontroller-equipped, infra-
`red (IR) transmitters) that may be positioned at physical
`locations, which are potential destinations for a visually-
`impaired user. For example, beacons may be located over
`doorways or facilities, such as restrooms, water fountains,
`stairways, elevators, or the like. These beacons may be
`programmed to transmit information concerning the physi-
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`cal location of the beacon and the direction to the beacon. A
`portable unit, which may be held by the user, may be
`programmed to receive these transmissions, to determine a
`routing path from the user’s current location to the target
`location, and to direct a user to the desired location. Thus,
`this invention provides autorouting, which has not been
`provided in systems previously designed to guide a blind
`user, and is passive so that any number of visually impaired
`persons may use the system simultaneously.
`Each physical location may also be identified with mul-
`tiple beacons, such as a main IR transmitter beacon and an
`auxiliary IR transmitter beacon. To identify a physical target
`location, a main beacon may be located high on the wall or
`ceiling above the target. An auxiliary beacon, which corre-
`sponds to this main beacon, may be mounted in close
`proximity to a relevant structure of the target location, for
`example at waist level on a wall next to a door knob.
`The beacon transmissions may be sets of four code
`numbers sent via infrared emitting diodes (IRED’s) driven
`by a microcontroller. In this embodiment, each of the code
`numbers is serially transmitted as an eight-bit (no parity, one
`stop bit) byte. This is adequate for most buildings, since few
`have more than 255 floors, hallways, or rooms per floor,
`which need identification. Beacons that are within line-of-
`sight of one another may also be slaved to a master micro-
`controller which sets the cycle period and sequentially
`activates the beacons. Master controllers for different groups
`of beacons may free-run, or they may be linked, so that two
`activated beacons are never visible simultaneously to an
`observer to prevent mutual interference between IR trans-
`missions. Beacon transmissions may be detected and pro-
`cessed by hand-held, portable units, such as an infrared
`receiver/microcontroller (IRRM). Because each beacon
`transmits a distinct set of code numbers, each beacon may be
`“identified” by the IRRM.
`In one embodiment, for example, the user turns on the
`IRRM, which resets the microcontroller, and enters, via the
`IRRM keypad,
`the floor number followed by the room
`number of the target beacon (e.g., “236”—second floor,
`room 36). This three-digit number is termed the room or
`facility ID number, and may be obtained by the user from a
`Braille directory or from a voice-storage device that is part
`of, or an accessory to,
`the IRRM. The user scans the
`environment horizontally until a beacon is detected. A
`search algorithm is executed by the IRRM microcontroller
`to determine a route or routing path from the beacon
`detected at the user’s starting location to the target beacon.
`This routing path may depend upon a look-up table or other
`information, correlating the beacons to each other. Main
`beacons other than the target main beacon may serve as
`intermediate or way-points to the target location. The user
`receives a signal, such as an audible signal (e.g., single tone
`burst), each time the IRRM detects an IR transmission from
`a valid way-point beacon. The user will receive or hear a
`different audible signal (e.g., a triple tone burst) when the
`target auxiliary beacon has been detected. At any point along
`the route, the user may reset the IRRM microcontroller by
`turning it off and then on again. The user then reenters the
`same, or a different,
`target ID number. A new route or
`routing path will then be determined by the IRRM.
`The autorouting program for a particular building or
`campus may be uploaded into an IRRM in a reception area
`near the building entrance. A receptionist, or the user, could
`upload the program from a fixed computer. Alternatively, the
`program could be loaded automatically through serial, wire-
`less communication (i.e.,
`infrared or
`radio frequency
`transmission) which would serve to connect the IRRM with
`a fixed computer.
`13
`
`13
`
`
`
`5,806,017
`
`5
`Additional information may also be provided to a user.
`For example, a directory of facilities or individuals within a
`building or group of buildings along with their correspond-
`ing ID numbers may be stored in a Braille listing or in a
`digital voice-storage device contained within the IRRM or
`attached to the IRRM as an accessory. A subroutine in the
`IRRM program could allow the directory to be announced.
`For instance, the microcontroller may be programmed so
`that pressing the “#” key on the IRRM keypad, after the
`microcontroller is reset, may direct the voice-storage device
`to announce all of the listings in the directory. Also, pressing
`the “*” key after reset may direct the microcontroller to
`identify only the beacon first detected after the key is
`pressed. This would allow the user to get oriented quickly.
`The digital voice-storage device may be an integrated circuit
`(IC) chip installed either in the IRRM or in a detachable unit
`that may be kept separate from the IRRM.
`Now an embodiment of the present invention will be
`described in more detail with reference to the attached
`drawings. As would be understood by one of skill in the art,
`alternative embodiments of the present invention, as well as
`alternative embodiments of the systems depicted in the
`drawings, are possible.
`The block diagram in FIG. 1A shows an embodiment of
`a portable autorouting navigation unit, according to the
`present
`invention,
`in the form of an infrared receiver/
`microcontroller (IRRM) 100. The IRRM 100 includes a
`microprocessor or microcontroller 105,
`for example a
`BASIC STAMP II microcontroller (BSII, available from
`Parallax, Inc., 3805 Atherton Rd., #102, Rocklin, Calif.
`95765). This microcontroller 105 may have internal RAM
`memory that allows storage of information. Microcontroller
`105 controls the activities of the portable device. The
`microcontroller is connected to an input device, such as a
`keypad 106, for entering data into the device. The keypad
`106 may be a 3x4 matrix device with keys for digits 0—9 and
`for characters “*” and “#”. The microcontroller 105 is also
`connected to a receiver 101, such as a TFMS5400
`(Telefunken) infrared detector module, that receives infor-
`mation being sent from the location beacons. The micro-
`controller 105 may be connected to an output device 103,
`such as an ISD2500 voice-storage IC, which is available
`from Information Storage Devices and which is capable of
`storing 90 seconds of speech. An earphone 104, or other
`speaker or output device, may be connected to the voice-
`storage IC. This allows either a tone or audio instruction to
`be provided to the user. Finally, the IRRM 100 may contain
`a power supply 102, such as a nickel/cadmium (NiCd) or
`nickel/metal hydride (NiMH) rechargeable battery. A volt-
`age regulator on the BSII microcontroller provides 5 volt
`power to the infrared detector module 101 and the voice-
`storage IC 103. ISD2500 voice-storage ICs may also be
`cascaded to provide additional speech storage. It is noted
`that the embodiment depicted and described herein is one
`example embodiment, and that alternative designs and
`embodiments may be used for a portable autorouting navi-
`gation unit for receiving transmitted location information,
`according to the present invention.
`FIG. 1B shows the external features of an embodiment of
`
`an IRRM 150. The front surface 151 has a port 152 to allow
`the entry of an IR signal. A 3x4 matrix keypad 156 is
`mounted on the top 159 of the IRRM 150. The side 155 of
`the IRRM 150 contains an on—off slide switch 153 and a
`
`connector 154 to connect an external power supply for
`recharging the internal battery. The rear 158 of the IRRM
`150 contains a connector 157 to attach an earphone.
`FIG. 2A is a block diagram of an embodiment of the
`present
`invention showing the connections between the
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`components of a main beacon 200 and an auxiliary beacon
`230. A main beacon 200 may be mounted high on the wall
`or ceiling to identify a physical
`location. An auxiliary
`beacon 230 may be connected to the main beacon 200 and
`mounted in close proximity to a particularly relevant part of
`a target location, such as a door knob on a door.
`For controlling the device,
`the main beacon 200 may
`include a microprocessor or microcontroller 201, such as a
`BASIC STAMP I microcontroller (BSI, available from
`Parallax, Inc., 3805 Atherton Rd., #102, Rocklin, Calif.
`95765). An external power supply 220, such as a 12 volt DC
`power supply, may be connected to main beacon 200 to
`supply power both to the main beacon 200 and auxiliary
`beacon 230. The main beacon 200 may also include an
`oscillator 202, such as a NE555-based oscillator providing a
`40 KHZ subcarrier, which can be modulated by digital
`signals from the microcontroller 201. The 40 KHZ signal and
`the serial outputs (8 data bits, no parity, and 1 stop bit) of the
`BSI microcontroller 201 provide inputs to logic gates 208,
`such as a CD4081 two-input, quad, AND gate integrated
`circuit. The output 207 of the AND gates switches power
`amplifiers 206. The 40 KHZ chopping of the serial outputs
`is required in this embodiment because the IR detector
`module in the IRRM 100 contains a 40 KHZ band-pass filter
`for noise reduction. The power amplifiers 206 switch the
`current in the infrared emitting diodes (IRED) 204 and 205
`of the main beacon and infrared emitting diode 231 of the
`auxiliary beacon. The LED’s may be a IRED by the desig-
`nation GL528, which is made by Sharp. The current through
`the IRED’s 204, 205 and 231 are set at 80—100 mA by
`current regulators, such as LM7805 current regulators. The
`IRED 231 of the auxiliary beacon 230 may also be driven at
`low power, so that IRED 231 may be detected by the
`portable navigation unit only when the user is within several
`feet of the beacon. As noted above, the embodiment depicted
`and described herein is one example embodiment, and
`alternative designs and embodiments may be used for a
`beacon that transmits location information, according to the
`present invention.
`FIG. 2B shows the external features of an embodiment of
`
`a main beacon 250 and an auxiliary beacon 260. Three
`connector ports 252 and 253 are mounted in the top of the
`main beacon. Connector ports 252 are used to link to other
`beacons. Such a link allows other beacons to serve as a
`master beacon or slave beacons to main beacon 250. This
`
`interconnection of beacons may also be used for sequential
`activation of adjacent beacons. In other words, a number of
`location beacons may be organized in a group of location
`beacons, for example in a hallway of a building. One of the
`location beacons within the group may serve as a master
`beacon and thereby control the transmissions of the other
`slave beacons. In this manner, location beacons within a
`group of beacons may be sequentially activated so that only
`one beacon within the group is sending out a signal at any
`one time. This may help avoid interference in system
`operation.
`Power is supplied to the main beacon 250 through con-
`nector port 253. Multiple (e. g., four) IREDs 254 and 259 are
`located on sides 259 and 254 of the main beacon 250. The
`bottom 257 of the main beacon 250 includes an additional
`
`connector port 256 that is used to connect the main beacon
`250 to connector port 262 in the top 261 of the auxiliary
`beacon 260. The front of auxiliary beacon 260 may include
`an IRED 265. The bottom 264 of auxiliary beacon 260 may
`be featureless.
`
`FIG. 3 is a diagram of an example positioning of a beacon
`300 at a physical location. In particular, FIG. 3 shows an
`14
`
`14
`
`
`
`5,806,017
`
`7
`example placement of a main beacon 303 and an auxiliary
`beacon 309 with respect to a doorway 306 and a door knob
`307 of an example “Room 12.” The IREDs 302 (four
`IRED’s shown) and 304 (four IRED’s shown) of main
`beacon 303 are aimed in generally opposite directions down
`the hallway in which Room 12 is located. The auxiliary
`beacon 309 is mounted close to the door knob 307. The
`IRED 308 of the auxiliary beacon 309 is aimed across the
`hallway. Each group of IREDs 302, 308, and 304 are
`activated sequentially, and each group of IREDs transmits a
`different set of code numbers to provide location informa-
`tion regarding the main beacon 303 and the auxiliary beacon
`309.
`
`10
`
`FIG. 4 provides an example of a set of code numbers 400
`which may be transmitted from one side of main beacon
`303. The first number 401 identifies the floor number. The
`
`15
`
`second number 402 identifies the hallway number on the
`particular floor. The third number 403 is the room or facility
`identification number (ID). The fourth number, which may
`be a 0, 1, or 2, provides beacon, and thus hallway, polarity,
`and is termed the “director.” The director “2” is transmitted
`
`in the direction of descending ID numbers, so that an IRRM
`aimed in the direction of increasing rank order of ID
`numbers will receive the director “2” from any beacon that
`is detected. The system’s use of the director information is
`further discussed below. Conversely,
`the director “1” is
`transmitted in the direction of ascending ID numbers. Aux-
`iliary beacons transmit the director “0.” The set of code
`numbers 400 in FIG. 4 is “1, 1, 12, 2” and,
`therefore,
`identifies the 1st floor, hallway number 1, room or facility
`12, and director 2. The auxiliary beacon associated with a
`main beacon emitting the set code numbers 400 would,
`therefore, serially transmit the code numbers “1, 1, 12, 0.”
`It is noted that alternative conventions may be used for the
`location beacon transmissions, with corresponding changes
`in the search algorithm discussed below.
`As discussed in more detail below, a location beacon
`positioned at a hallway intersection would not generally
`have an auxiliary beacon associated with it. Such intersec-
`tion beacons may be designed to transmit in three or four
`directions, and the hallway numbers for the intersection
`beacons may be identical to the hallway numbers for the
`hallways they link. The intersection beacons may also have
`an ID number like any room or facility. This is demonstrated
`by beacon 508 in FIG. 5A, which links hallways 1, 2 and 3.
`The operation of a system according to the present
`invention will now be described in more detail with respect
`to FIGS. 5A and 5B and 6A and 6B.
`
`FIGS. 5A and 5B are a diagram of an example arrange-
`ment 500 of a plurality of main beacons located at doorways
`within intersecting hallways on a floor inside of a building.
`The hallways include doorways identified with the identifi-
`cation numbers 1—17. These figures also provide the respec-
`tive sets of numerical codes that the main beacons transmit,
`along with the general direction of these transmissions. All
`sets of code numbers begin with the number “1,” designating
`that the beacons are all located on the first floor. The floor
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`has been divided, by the intersection of hallways, into three
`hallway segments 501, 502 and 503, which are defined by
`the second code number related to each transmission. The
`
`60
`
`third code number provides the room or facility ID number.
`The fourth number transmitted by each main beacon is either
`the director “1” or “2,” which serves to polarize the hall-
`ways. For example, if a user moves in a direction such that
`the IRRM detects only the director “2,” the IRRM may
`determine that
`the ID numbers in that direction are in
`
`65
`
`increasing rank order, as discussed above with respect to
`
`8
`FIG. 4. Conversely, a user traveling in the direction where
`the director “1” is being detected, will detect beacons with
`decreasing ID numbers.
`FIGS. 6A and 6B are a flow chart of an example search
`algorithm that may be implemented by a portable autorout-
`ing navigation unit, according to the present invention, to
`guide a user to a desired location. An example user of this
`system is depicted in FIGS. 5A and 5B. Using the search
`algorithm provided in FIGS. 6A and 6B, the portable unit
`will guide the user from his or her starting location 510,
`along path 509 and 506, through hallway 5