United States Patent 55
`5,806,017
`[45] Date of Patent: Sep. 8, 1998
`Hancock
`
`
`
`[11] Patent Number:
`
`US005806017A
`
`[54] ELECTRONIC AUTOROUTING
`NAVIGATION SYSTEM FOR VISUALLY
`IMPAIRED PERSONS
`
`[75]
`
`Inventor: Michael B. Hancock, Galveston, Tex.
`
`2 661 607
`WO 95/04440
`
`France .
`11/1991
`2/1995 WIPO.
`
`OTHER PUBLICATIONS
`
`[73] Assignee: Board of Regents The University of
`Texas System, Austin, Tex.
`
`Yewman, “The Seeing—Eye Box,” Biomedical Inquiry, The
`University of Texas Medical Branch at Galveston, Spring
`1996.
`
`[21] Appl. No.: 699,580
`Primary Examiner—Michael Zanelli
`“44.
`Assistant Examiner—Edward Pipala
`[22]
`Filed:
`Aug. 19, 1996
`
`[51] Int. Che eee GO1C 21/00; GO6F 165/00=Alforney, Agent, or Firm—Arnold, White & Durkee
`[52] US. Ceeeecescsecsnesetesseeestesseesseensennes 701/209; 701/211
`[57]
`ABSTRACT
`[58] Field of Search 0. eee 364/443, 444.1,
`364/444.2, 448, 449.2, 449.3, 449.5; 701/200,
`201, 202, 206, 208, 209, 211
`
`[56]
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`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 toa physical loca-
`tion of a plurality of location beacons, a receiver configured
`to receive signals from the location beacons, a memory
`3,104,478
`9/1963 Strauss et al. eee este 35/25
`
`storing information correlating the locations of the location
`3,718,896
`.. 340/1 R-
`2/1973 Mowat..........
`beacons, and an output device for communicating with the
`4,025,922
`5/1977 Trawick, III ..
`- 343/6.5 LC
`
`user. A microcontroller or microprocessor under program
`4,045,799
`»- 343/113 PT
`8/1977 Dapiran.........
`
`control processes the signals received from the location
`loseso i980 nonceqta ”
`” sels)
`
`beacons, analyzes those signals and correlation data, and
`,
`”
`4648710
`3/1987 Ba etal
`356/4
`
`
`4.660.022 ..340/407_—determinesa routing path from the user’s presentposition to4/1987 Osaka seccmece.
`
`
`2/1990 Sato ......
`340/825.57
`4,904,993
`the target location. The microcontroller may also provide an
`
`6/1990 Friedman ..
`we. 367/118
`4,935,907
`indication, such as an audible sound,to the user of whether
`
`
`7/1991 Friedman ..
`wee 434/112
`5,032,083
`or not the user is following the routing path to the target
`7/1991 Ono et al. wees 340/325.71
`5,032,836
`location. Significantly,
`the present
`invention relies upon
`5,067,081
`11/1991 Person seees ene eseseseseeseneeecesseseneees 364/444
`beacons that send out location and direction information
`9/1992 Alonziet al.
`340/825.49
`5,144,294
`without being polled by the portable unit determines a
`
`vo 340/572
`5/1993, Verster .....
`3,214,410
`routing path that allows for autorouting. Beacons may also
`
`w+. 364/449
`5,406,491
`4/1995 Lima.....
`:
`:
`.
`
`5.487669
`1/1996 Kelk
`434/112
`be organized in groups of beacons that can correlate to
`5,508,699
`4/1996 SilVerMANveces. 340/944
`Seographical landmarks such as hallways in a building to
`5,600,706
`2/1997 Dunnetal. ween 379/59
`reducethesize ofthe correlating data stored in the memory
`of the portable unit and thereby reduce processing time.
`FOREIGN PATENT DOCUMENTS
`
`0 338 997
`
`10/1989 European Pat. Off.
`
`.
`
`15 Claims, 10 Drawing Sheets
`
`sao
`
`1,2,9,1 1,2,10,1
`
`a 12,92 12,18.2)
`=
`
`
`
`1
`
`APPLE 1006
`
`APPLE 1006
`
`1
`
`

`

`U.S. Patent
`
`Sep. 8, 1998
`
`Sheet 1 of 10
`
`5,806,017
`
`189
`
`
`KEYPAD
`
`
`3X4 MATRIX
`
`INFRARED DETECTOR
`
`MODULE
`
` TFMS5400
`
`
`186
`
`182
`
`
`PARALLAX
`
`
`NiCd/NiMH
`
`
`BSIl
`BATTERY
`MICRO CONTROLLER
`
`
`105
`
`EARPHONE
`
`104
`
`
`
`
`INFORMATION STORAGE
`
`DEVICES ISD2500
`
`VOICE STORAGE IC
`
`183
`
`FIG. 1A
`
`2
`
`

`

`U.S. Patent
`
`Sep. 8, 1998
`
`Sheet 2 of 10
`
`5,806,017
`
`151
`
`152
`
`153
`
`154 155
`
`Cele}Le]Le]
`
`158
`
`157
`
`FIG. 1B
`
`3
`
`

`

`U.S. Patent
`
`Sep. 8, 1998
`
`Sheet 3 of 10
`
`5,806,017
`
`
`
`PARALLAX BSI
`MICRO CONTROLLER
`
`WITH INTERNAL
`
`LM7805 VOLTAGE
`
`REGULATOR
`
`207
`
`
`
`SHARP GL528
`
`
`INFRARED LED'S
`
`MAIN BEACON
`
`283
`SHARP GL528
`POWER
`Ly
`
`
`INFRARED LED'S
`206
`AMPLIFIER
`MAIN BEACON
`
`
`|{POWER
`
`AMPLIFIER
`
`205
`
`
`
`
`
`a= n-
`
`230
`
`-on---5
`SHARP GL528 AI
`
`INFRARED LED
`
`AUXILIARY BEACON
`
`
`
`t!
`
`FIG. 2A
`
`4
`
`

`

`U.S. Patent
`
`5,806,017
`
`Sep. 8, 1998
`
`Sheet 4 of 10
`
`
`
`5
`
`

`

`U.S. Patent
`
`Sep. 8, 1998
`
`Sheet 5 of 10
`
`5,806,017
`
`306
`
`383
`
`319
` ROOM 12
`
`FIG. 3
`
`6
`
`

`

`U.S. Patent
`
`Sep. 8, 1998
`
`Sheet 6 of 10
`
`5,806,017
`
`400
`
`1,1, 12, 2
`
`HALLWAY
`
`ID
`
`DIRECTOR
`
` FLOOR
`
`401
`
`4p2|
`
`493
`
`404
`
`FIG. 4
`
`7
`
`

`

`U.S. Patent
`
`Sep. 8, 1998
`
`Sheet 7 of 10
`
`5,806,017
`
`1,2,9,1 1,2,19,1
`a
`
`1,2,9,2 1240.37 500
`o 'S
`
`
`
`580
`
`FIG. 5A
`
`8
`
`

`

`U.S. Patent
`
`Sep. 8, 1998
`
`Sheet 8 of 10
`
`5,806,017
`
`504
`
`583
`
`506
`
`
`MN_
`
`
`FIG. 5B
`
`9
`
`

`

`U.S. Patent
`
`Sep. 8, 1998
`
`Sheet 9 of 10
`
`5,806,017
`
`691
`
`{POWER
`
`ACTIVE VOICE
`STORAGE IC-
`“ENTER TARGET
`6@2|CODE NUMBER“
`
`
`
`
`
`
`690
`
`
`
`
`
`606
`
`
`
`ACTIVATE VOICE
`STORAGE IC - “TARGET
`
`
`
`
`ON DIFFERENT FLOOR
`HALLWAYNURHERS es
`
`
`
`
`ROUTING TO
`MATCH?
`STAIRWAY“ NO
`
`
`
`
`
`OBTAIN SET OF HALLWAY
`SET STORAGE CODE
`NUMBERS AND
`NUMBER=
`
`
`DIRECTIONS FROM
`STAIRWAY CODE
`
`
`
`NUMBER
`LOOKUP TABLES THAT WILL
`
`
`
`ROUTE USER TO TARGET. 68
`
`SINGLE TONE
`BURST.
`
`
`
`
`
`
`BEACON AND
`
`TARGET ID NUMBERS
`
`
`MATCH?
`
`
`NO
`
`BEACON
`DIRECTOR=0? TARGE
`AUXILIARY BEACON
`DETECTED?
`
`NO
`
`TRIPLE TONE
`BURST
`
`SINGLE TONE
`BURST
`
`
`
`
`
`
`
`
`618
`
`FIG. 6A
`
`619
`
`10
`
`10
`
`

`

`U.S. Patent
`
`Sep. 8, 1998
`
`Sheet 10 of 10
`
`5,806,017
`
`
`BEACON ID
`NUMBER > TARGETID
`
`NUMBER?
`
`
`
`
`BEACON
`BEACON
`DIRECTOR = 2?
`POLARITY = 1?
`
`
`
`
`
`
`BURST
`
` 628 621
`FIG. 6B
`
`SINGLE TONE
`BURST
`
`
`
`SINGLE TONE
`
`
`
`11
`
`

`

`5,806,017
`
`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 abouttraffic signal states.
`More sophisticated systems have also evolved, such as
`that disclosed by Osaka, U.S. 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 simultaneouspoll-
`ing transmissions mutually interfere.
`Another system is shown in U.S. 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 roomsor 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
`numberof 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.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`SUMMARYOF THE INVENTION
`
`The present invention contemplates an autorouting navi-
`gation system for directing one or more visually impaired
`personsto a physicallocation. 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 memorythat 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.c., 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
`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.
`
`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 whichthe 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 includesa plurality of location beacons
`positionedat 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 includesa 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 devicefor selecting a target
`location, a receiver configured to receive signals from the
`location beacons, a memorystoring 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 andthe 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 mayalso 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,
`whichare 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 whetherthe 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 beaconfor 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
`doorwaysor 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 andthe direction to the beacon. A
`portable unit, which may be held by the user, may be
`programmedto 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 numberof 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 maybelocated 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
`numbersis 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 belinked, 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, whichresets 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 throughserial, 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 bestored 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
`microcontrolleris reset, may direct the voice-storage device
`to announceall of the listingsin 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 orin 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 oneofskill 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 embodimentof
`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
`memorythat 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 providedto 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 showsthe 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 relevantpart 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 KHzsignal and
`the serial outputs (8 databits, 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 ofthe serial outputs
`is required in this embodiment because the IR detector
`module in the IRRM 100 contains a 40 KHz band-passfilter
`for noise reduction. The power amplifiers 206 switch the
`current in the infrared emitting diodes TRED) 204 and 205
`of the main beacon and infrared emitting diode 231 of the
`auxiliary beacon. The LED’s may be a IRED bythe 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 LM7805current regulators. The
`IRED 231 of the auxiliary beacon 230 mayalso be driven at
`low power, so that IRED 231 may be detected by the
`portable navigation unit only whenthe user is within several
`feet of the beacon. As noted above, the embodimentdepicted
`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 showsthe 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 numberof
`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.
`Poweris 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
`TRED’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 IREDstransmits a
`different set of code numbers to provide location informa-
`tion regarding the main beacon 303 andthe 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 orfacility
`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 orfacility
`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 numberlike any room orfacility. This is demonstrated
`by beacon 508 in FIG. 5A, which links hallways1, 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 beaconstransmit,
`along with the general direction of these transmissions. All
`sets of code numbers begin with the number“1,” designating
`that the beaconsare all located on the first floor. The floor
`
`has been divided, by the intersection of hallways, into three
`hallway segments 501, 502 and 503, which are defined by
`the second code numberrelated to each transmission. The
`third code number provides the room orfacility ID number.
`The fourth numbertransmitted by each main beaconiseither
`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
`
`increasing rank order, as discussed above with respect to
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`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 userofthis
`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 501 (ic., hallway
`number 1) and hallway 503 (i.c., hallway number 3), and
`finally to the desired target beacon 505 at door 16.
`Following the flow chart of FIGS. 6A and 6B, the user
`first turns on the IRRM in step 601 andis instructed to enter
`a target ID numberin step 602. For the example user in
`FIGS. 5A and 5B, the number 116 (ie., first floor, door
`number 16) is punched into the keypad. The user then scans
`the area in step 603. Decision step 604 provides a loop until
`a beacon