VWGoA - Ex. 1007
`Volkswagen Group of America, Inc., Petitioner
`
`1
`
`

`
`Mg§§;..Ew§§e£22&u§.EE
`
`as
`
`...IHEnwsqSEE
`
`ts:is
`
`8_H
`
`IHD_Easasxa_“§_$&SE‘$8838%*
`
`
`ll_”E3:.5g“§3m5%asm“Ease>t\t<ssssfik§%E.ESE:_,_
`wlllllllllllllllllllllllllllllllllllllllllllll
`
`U
`
`
`..........................................E.“ _m_5.3%E:.Es_P_;§\.§=Ea_su__.
`
`
`8
`
`72
`
`06
`
`
`
`
`
`
`
`.A~...aEmma..?.$.&..§\.<Qat...EKath55%53«EVS;.2SESE$55
`
`2
`
`
`

`
`U
`
`Ll
`
`4W.
`
`0
`
`.§$<%Et
`
`SEaas:H2sawHW.
`nHax‘
`
`m%EsemmE:E_M_EE5_P_§E_SFllllllllllllllllllllllllllllllllllllllllllllllL
`33%:_1,__M._is:asass53:_“§.E&Sam__2:.=EmSac.~53“
`SEEM:2Es_fi...............:z.-...................._3:Eu5%as3&8S:SE.5_m"CXEE
`
`
`
`
`
`
`5«EE:.2Eumafia§b§EisN
`
`3
`
`
`

`
`U
`
`W.
`
`29
`
`O6
`
`§$E.S
`
`t_#5»M_33%»E:QaF.fiizbai
`3_§Eu3%asgas3%wJt§tESEES»BE3vs~_§\.§:
`
`_Em*}EmsE15_Ext»5:
`
`....s\alllllllllllllllllls|Ial.IIIII«IfIIIIlIII|.I|__E3:
`
`
`is._S.‘six‘
`
`
`
`S__.IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII-
`
`sEEE.as
`
`
`
`50.Wu,QEVS;.2émfimakaI.§.m§.EMGSM%.
`
`s._s§mrSag:Mgg33¢mniE:3%Ka3.8
`
`4
`
`
`

`
`U
`
`1
`
`4
`
`mm_3%3:ass5;:._§$&E5%asan“_is_ug$isMM_§=c&E:a§§as_M._§»:$\a§tSE_P”QUE_S_FuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuEnnnnnnEu»:._
`
`,_
`
`SE35%_3“5.Sq.52as3.EsH_w_23.2853%SE35;£52:En
`__.5::as»SEE
`
`s§m§¢ME».3%.E
`m~SSE5:8§9"ass.ESE
`
`065,472,5
`
`
`
`«E§§.§.§§E.IE<3:.$§.§m§a=Sa%
`
`E3E§§
`QxrfitEEEEtttw3%
`
`St:8
`
`mmsq
`
`§
`
`5
`
`
`
`

`
`em.P«MU
`
`M
`
`M
`
`59
`
`065
`
`m»EB:
`
`W.5.5:$5‘:~§.3tSt.¢.
`
`.$3.$3
`
`6
`
`

`
`M.CtaPQMU
`
`3mm,
`
`6
`
`59
`
`065,
`
`
`
`uzahwfiwmfi$323:
`
`
`
`c.E§E53SEN\S§S$2.5m.§mE&333E2:SE3ES3&3%EssmsE2$§%E&E§¥§\§%§§esfifi~$..
`
`4.
`
`.9/.émEats:..E§Smama»vat
`
`M%©<§&%an:3‘EEEsa3%:E:ESEE
`
`
`
`8E:§.§.§«358%2%
`
`..m3.5.s:.G$E§55$
`
`%E.,.:
`
`7
`
`
`

`
`U
`
`t3
`
`D
`
`1
`
`729
`
`06
`
`m.§F§.Ean3%a29:5ms:3:
`
`3.§5§2%E:§....§§%wESEEE3£5.§.
`
`.$5:
`
`
`
`%twkbtfizaE§§..§&.§m&K
`
`5:33:
`
`..§EEas:E..=32E
`
`7E3.35$.235:3m_Sr.III‘'!INIIII‘III|‘IIIIL
`allllllllllllllllllllIIJ3_MxSums$53..as$33:
`
`mxEimam2%;8§._$2.3
`
`tSEEE:33Es:SE3£3:2&3%2535:Eam3§..£.¥.
`E§£sE\m§§%.§:%%§.
`
`P.$§.wu..U§k&.wk1btxkgfikQ\<
`
`ab..333.‘-
`
`8
`
`
`

`
`U.S. Patent
`
`Dec. 28, 1993
`
`Sheet 8 of 8
`
`2:5
`
`065
`
`u,____
`
`__.......__
`
`V-—-' fix
`
`M 1-—‘§
`
`=E\+.___._._W\_.Em
`
`9
`
`

`
`1
`
`5,274,560
`
`'
`
`SENSOR FREE VEHICLE NAVIGATION SYSTEM
`UTILIZING A VOICE INPUT/OUTPUT
`INTERFACE FOR ROUTING A DRIVER FROM
`HIS SOURCE POINT TO HIS DESTINATION
`POINT
`
`RELATED APPLICATION
`
`This application is a continuation-in-part of applica-
`tion Ser. No. 07/621,577, filed Dec. 3, 1990, now aban-
`doned.
`
`NOTICE REGARDING COPYRIGHTED
`MATERIAL
`
`A portion of the disclosure of this patent document
`contains materials which is subject to copyright protec-
`tion. The copyright owner has no objection to the fac-
`simile reproduction by anyone of the patent document
`or the patent disclosure as it appears in the Patent and
`Trademark office patent file or records, but otherwise
`reserves all copyright rights whatsoever.
`
`BACKGROUND OF THE INVENTION
`1. Field of the Invention
`
`This invention relates in general to navigation sys-
`tems, and more particularly to a navigation system in-
`corporating artificial intelligence that is useful for cars
`and trucks requiring no sensors for spatially locating the
`vehicle and which uses an audio, rather than visual,
`interface with the driver.
`
`2. Description of the Related Art
`Many existing navigation systems utilize internal sen-
`sors or navigation satellites to locate the subject vehicle
`with respect to a digital map and then, once located,
`create a visual presentation of the map, the location of
`the vehicle and the destination point on a CRT mounted
`in the dashboard or elsewhere in the vehicle. Some
`systems also calculate a preferred route which is high-
`lighted on the displayed map. A great deal of effort and
`technology is used in these systems in order to locate
`the vehicle as accurately as possible in order to perform
`the navigation function.
`U.S. Pat. Nos.
`4,630,209; 4,829,578; 4,502,123;
`4,242,731; 4,679,147; 4,796,189; 4,677,429; 4,882,696;
`4,749,924; 4,758,959 and 4,827,520 pertain to car naviga-
`tion systems or to voice actuated control of a vehicle
`and are representative of these existing navigation sys-
`tems.
`
`For example, U.S. Pat. No. 4,758,959 issued to Tho-
`one et al., is indicative of both the ability and shortcom-
`ings of the existing systems. In US. Pat. No. 4,758,959,
`speedometers and accelerometers are utilized to esti-
`mate the vehicle’s position and corrections are made to
`try to keep the vehicle positioned on the map. The map
`and the vehicle are displayed on a CRT. The operator
`inputs his source and destination points via a keyboard.
`The problems associated with this kind of system are
`as follows:
`
`1. The accelerometer and velocity sensors are subject
`to drift and can go out of calibration. Even if the sensors
`were perfect or if very accurate satellite positioning
`were possible, the maps available are not accurate, hav-
`ing been digitized from maps which are essentially hand
`drawn. Thus, it is difficult to determine what street or
`section of street the vehicle is actually on.
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`45
`
`50
`
`55
`
`65
`
`2
`2. The presentation of a map on a CRT in a moving
`vehicle is a dangerous distraction, especially in heavy
`traffic found around cities.
`3. The use of a keyboard for input from the driver is
`another distraction and could be dangerous to use while
`the vehicle is in motion.
`4. The use of on-board sensors requires the use of
`specialized procedures with specially trained personnel
`for proper installation. Typically, this kind of installa-
`tion is best done at the factory where the vehicle is built.
`Therefore, these devices miss the broad after-market of
`existing cars.
`SUMMARY OF THE INVENTION
`
`Accordingly, the following are some of the primary
`objects and advantages of the present invention:
`1. To provide a navigation system which uses artific-
`ial intelligence algorithms to find the best route from
`source to destination, without requiring any sensors to
`locate the car;
`2. To provide a navigation system which contains an
`audio, rather than a visual, interface with the driver and
`is thereby non-distracting;
`3. To provide a means for the driver of the vehicle to
`negate or deny any turn instruction given by the com-
`puter and to demand an alternative route. This feature
`overcomes the need for extremely accurate maps in
`which every one-way street and every possible turn
`restriction (including time of day turn restrictions) have
`been incorporated;
`4. To provide a navigation system having few me-
`chanical parts in order to increase reliability and de-
`crease the cost of production;
`5. To provide a navigation system that can be built
`around a very inexpensive, portable compact disk music
`player which will keep the music functions while add-
`ing the navigation functions;
`6. To provide a navigation system which does not
`have to be installed in the car. It can be portable or in
`the form of an AM/FM Compact Disc Radio and can
`be sold to anyone who already has a car;
`7. To provide a navigation system with traffic avoid-
`ance capability, when digitized traffic information be-
`comes available. An FM receiver can be tuned to pick
`up the latest traffic information and adjust street and
`highway speeds accordingly. The artificial intelligence
`routing algorithms in the device will automatically
`route the driver around congested areas;
`8. To provide a navigation system which may option-
`ally utilize a drive shaft rotation sensor as a convenience
`to alert the driver that his next turn is coming up. It can
`also aid in escaping a highway traffic jam which has
`been detected up ahead by the traffic update receiver
`(see 7 above);
`In summary, the present invention is directed to a
`navigation system for a vehicle including means, such as
`a speech digitizer or an analog signal processor, for
`converting a spoken audio signal into a corresponding
`electrical signal and for storing said electrical signal as
`data in a location data memory. A microprocessor is
`coupled to the location data memory and to a map data
`memory for processing data from each of the memories
`according to a program stored in a program memory.
`The stored program includes path finding procedures
`for selecting a path between two points, a first point
`being represented by data stored in the location data
`memory and a second point being represented by data
`stored in the map data memory, and for generating a set
`
`10
`
`10
`
`

`
`5,274,560
`
`4
`
`LIST OF REFERENCE NUMERALS
`
`Refer to FIG. 4
`
`Micro Processor Components
`
`3
`of electrical signals representing a selected path. Means
`are coupled to the microprocessor for converting the
`set of electrical signals representing the selected path to
`an audibly perceptible signal.
`A method for the navigation of a vehicle embodying
`the present invention includes the steps of: sensing a
`spoken audio command from the user and converting
`the sensed audio command into a corresponding electri-
`cal signal; storing the electrical signal as data in a loca-
`tion data memory; selecting a path between two points,
`a first point being represented by data stored in the
`location data memory, and a second point being repre-
`sented by data stored in a map data memory by process-
`ing in a microprocessor data from the location data
`memory and from a map data memory according to a
`program stored in a program memory; generating a set
`of electrical signals representing a selected path; and,
`converting the set of electrical signals representing the
`selected path to an audibly perceptible signal.
`The novel features of construction and operation of
`the invention will be more clearly apparent during the
`course of the following description, reference being had
`to the accompanying drawings wherein has been illus-
`trated a preferred form of the device of the invention
`and wherein like characters of reference designate like
`parts throughout the drawings.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 is a navigator embodiment which contains a
`single processor, a compact disk with an FM receiver,
`and a drive shaft rotation sensor. The Digital Signal
`Processor is the more expensive 32 bit style processor
`which has a wide enough address space to perform the
`Navigation functions in addition to the Speech Process-
`ing and Disk Control functions. This embodiment can
`perform traffic avoidance functions.
`FIG. 2 is a navigator embodiment which contains
`two processors. The Digital Signal Processor is the less
`expensive 16 bit style which only has enough addressing
`capability to perform the speech processing and disc
`control functions. The Navigation functions, which
`require a larger address space, are done in a separate 32
`bit Micro Processor. Communication between the two
`
`processors is by means of a FIFO. The compact disk
`player does not contain an FM radio and therefor this
`embodiment cannot perform the traffic update func-
`tions.
`
`FIG. 3 is a navigator embodiment which contains a
`single processor and a drive shaft rotation sensor. It
`contains the more expensive 32 bit Digital Signal pro-
`cessor. The compact disk player does not contain an
`FM radio and therefor this embodiment cannot perform
`the traffic update functions.
`FIG. 4 is a navigator embodiment which contains
`two processors, a compact disk with an FM receiver,
`and a drive shaft rotation sensor.
`
`FIG. 5 shows how routing occurs utilizing a multi-
`level map data base.
`FIG. 6 is a flow diagram of the speech training pro-
`cess.
`
`FIG. 7 is a flow diagram of the speech recognition
`process.
`FIG. 8 is a graph of nodes and arcs of a map data
`base.
`
`FIG. 9 is a graph of arcs of a map data base.
`
`10
`
`I5
`
`20
`
`25
`
`30
`
`35
`
`45
`
`50
`
`55
`
`60
`
`65
`
`1 Noise cancelling microphone
`2 Audio amplifier for amplifying the signal from the
`microphone
`3 Analog To Digital Converter for digitizing audio
`signal
`4 Digital Signal Processor for disk and speech input-
`/output
`5 EEPROM for storing speech templates
`6 ROM for storing the bootstrap routine
`7 RAM for storing program, speech and map data
`8 FIFO used for data transfers between the two mi-
`croprocessors
`9 Navigation Processor
`10 ROM for storing the bootstrap routine
`11 RAM for storing program and map data
`12 Sub-carrier demodulator for retrieving digital
`traffic information
`"
`13 Optional drive shaft rotation sensor
`
`Compact Disk Player Components
`14 FM receiver
`15 Tracking control servo
`16 Three beam LAZER pickup
`17 Focus control servo
`
`18 Signal processor for error correction
`19 Random access memory for data buffering
`20 Digital processor for music functions
`21 Serial digital to analog converter for voice and
`music output
`22 Left speaker audio amplifier
`23 Right speaker audio amplifier
`S1 Music/Navigation selection switch
`S2 Music/Navigation selection switch
`
`BRIEF DESCRIPTION OF THE APPENDICES
`
`The following APPENDICES A—C are computer
`program listing and the computer program listing will
`not be part of the printed patent.
`APPENDIX A
`
`Appendix A contains a program listing for control-
`ling the microprocessor of the illustrated embodiment.
`Appendix A contains nine modules, Al—A9.
`Module Al contains a routing algorithm for comput-
`ing the path from the starting address to the destination
`address.
`
`Module A2 contains an input/output routine which
`enables the microprocessor to control the digital signal
`processor like a slave.
`Module A3 is the executive routine which is used to
`call the other routines of the program.
`Module A4 is an address matching algorithm which
`finds the node in the map data base which corresponds
`to an address.
`
`Module A5 contains a spelling checker routine.
`Module A6 contains a routine to create sentences for
`the enunciation of the computed path.
`Module A7 contains a speech training routine.
`Module A8 contains a data file of the voice templates
`for the digital signal processor.
`Module A9 contains the helper file.
`Module A10 contains a test program for the branch
`and bound/A‘ algorithm.
`
`11
`
`11
`
`

`
`5
`
`APPENDIX B
`
`5,274,560
`
`Appendix B contains the program for controlling the
`digital signal processor for speech recognition and
`speech creation.
`
`5
`
`APPENDIX C
`
`Appendix C contains a program for compressing
`speech data utilizing an analog devices ADDS2l01
`DSP evaluation board to perform the A/D conversion
`process.
`
`DETAILED DESCRIPTION OF THE
`DRAWINGS
`
`Refer To FIG. 4
`
`A directional Microphone (1) p the driver’s voice.
`An Audio Amplifier (2) amplifies the signal from the
`microphone and rolls off the frequencies above 4000
`Hz.
`
`A 13 bit (or better) Analog To Digital Converter (3)
`samples and quantizes the output of the audio amplifier
`at about 8000 Hz.
`
`A high speed Digital Signal Processor (4) analyzes
`the digitized, sampled output and extracts important
`speech features. In the illustrated embodiment, the DSP
`(4) is a model 21 ll integrated circuit manufactured by
`Analog Devices. Appendix B included with the present
`specification contains a program listing for operating
`the Digital Signal Processor (4) as a speech analyzer.
`The program listing of Appendix B is written in the
`BASIC programming language. The program may also
`be written in assembly language for the 2111 DSP inte-
`grated circuit.
`-
`EEPROM (5) or some equivalent nonvolatile mem-
`ory is used for storing speech feature “templates” cre-
`ated by the Digital Signal Processor (4).
`ROM (6) holds a minimal bootstrap program utilized
`by the Digital Signal Processor at startup or restart.
`RAM (7) is used for temporary storage of optical disk
`data input by the Digital Signal Processor (4) from the
`optical disk (not shown).
`FIFO (8) is used for data transfers between the Digi-
`tal Signal Processor (4) and the Navigation Processor
`(9). The FIFO (8) may be implemented using memories
`on board the DSP (4).
`The Navigation Processor (9) of the illustrated em-
`bodiment is a 68010 microprocessor manufactured by
`Motorola. Appendix A included within the present
`specification contains a program listing which includes
`modules A1-A9 for operating the microprocessor 9.
`Module A3 contains the executive portion of the pro-
`gram for calling the other routines. Module A9 contains
`the helper file (C language).
`ROM (10) holds a minimal bootstrap program uti-
`lized by the Navigation Processor (9) at startup or re-
`start.
`
`RAM (12) holds digital map data used by the Naviga-
`tion Processor (9).
`Drive Shaft Rotation Sensor (13) is a magnet fastened
`to the drive shaft in the vicinity of a pickup coil, which
`provides a pulse each time the shaft rotates past the coil.
`Using this optional sensor, the computer can tell when
`the next turn is coming up and can therefor alert the
`driver with a pleasant sounding chime.
`FM Receiver (14) is tuned to a traffic update channel
`by the Navigation Processor. The output of the receiver
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`45
`
`50
`
`55
`
`65
`
`6
`is demodulated by DEMOD (12) and passed to the
`Navigation Processor (9).
`Track Control Servo (15) is used to maintain the
`LASER Pickup (16) over the center of an optical disc
`track or to slew inward or outward when a track jump
`needs to be performed. Track jump signals come from
`the Digital Processor (20) or from the Digital Signal
`Processor (4) depending on the setting of Switch S2.
`Digital Processor (20) controls music playing when
`the unit is in the music mode.
`
`Signa.l Processor (18) and its associated RAM (19) are
`used to de-interleave and to detect and correct errors in
`the music or data read from the optical disk. The cor-
`rected signal is routed to the Serial D/A Converter (21)
`or to the Digital Signal Processor (4) depending on the
`setting of Switch S1.
`Serial D/A Converter (21) converts digitized music
`or voice records to analog waveforms for left and right
`channels. Sound is output via the left and right Audio
`Amplifiers (22 and 23).
`Switches S1 and S2 select the system mode—music
`or navigation. When these switches are in the down
`(navigate) position,
`the Digital Signal Processor (4)
`receives optical disk data from the Signal Processor (18)
`and sends track jump commands to the Track Control
`Servo (15).
`
`OPERATION OF THE INVENTION
`ILLUSTRATED EMBODIMENT (Refer To FIG. 4)
`
`Speech Training
`
`The type of speech recognition algorithm used by
`this navigator is a small vocabulary, speaker dependent
`recognizer. This type of recognizer requires a training
`phase in which the user says the words in the vocabu-
`lary several times in order to form templates against
`which future utterances can be matched. Training re-
`moves many problems associated with people who have
`unusual accents or voice qualities.
`This training task is accomplished by the Digital
`Signal Processor (4) under the direction and control of
`the Navigation Processor (9) using primarily module
`A7 of the program of Appendix A. Refer to FIG. 6 for
`the training functional flow.
`the
`NOTE: Unless specifically stated otherwise,
`word “computer” will be used from hereon to refer to
`both of these devices working together to perform par-
`ticular functions.
`I
`
`To accomplish the training, a dialog between the
`computer and the operator is begun in which the com-
`puter asks the operator to say the letters of the alphabet
`A-2,
`the numerals 0-9, and various control words
`needed by the computer, such as “Yes”, “No”, “No
`Turn”, etc. The user responds by speaking the re-
`quested words into the directional Microphone (1).
`An Audio Amplifier (2) conditions the signal, ampli-
`fying it and rolling off the high frequencies above 4000
`Hz.
`
`Ari Analog To Digital Converter (3) samples and
`quantizes the word being spoken at 8000 Hz and passes
`the quantized samples to the Digital Signal Processor
`(4)-
`The Digital Signal Processor (4), breaks the word
`into overlapping 20 msec frames and analyzes each
`frame for important features in a process known as
`“feature extraction”. Features commonly extracted by
`commercial recognizers are total frequency band en-
`ergy, Linear Predictive Coding (LPC) coefficients and
`
`12
`
`12
`
`

`
`7
`cepstral coefficients which can be derived from LPC
`coefficients. The features are stored in EEPROM (5) as
`templates as module A8. Other non-volatile memories
`may be used such as FLASH memories, and battery
`backed up CMOS memories.
`Test performed with the “NEC SAR-10 Voice Plus”
`speech demonstration card show that accurate recogni-
`tion for this application requires two or three training
`passes. Additionally, since the audio navigator may be
`used regularly by more than one person, the EEPROM
`(5) must be large enough to hold two or three sets of
`templates for each person who will be using the device
`on a regular basis.
`
`Speech Recognition
`
`Speech input is required when the driver starts his
`trip and during the trip. When the driver starts his trip,
`he will verbally enter the address of his source and
`destination; during the trip, he will ask for the next
`instruction when he has completed the previous instruc-
`tron.
`
`In order to recognize the word being spoken, the
`Digital Signal Processor (4) under the control of the
`Navigation Processor (9) using primarily module A2,
`extracts the features, just as was done during the train-
`ing phase. But this time, the features of the spoken word
`are matched with the templates stored in the EEPROM
`(5) memory and the best match is taken to be the word
`spoken. Refer to FIG. 7 for a functional flow diagram of
`this process.
`The matching process used is set forth in Appendix B
`and is called “Dynamic Time Warping” in which the
`features in the unknown word are time aligned and
`compared with each of the templates. The template
`with the smallest distance from the unknown word is
`the winner. An ASCII code for the recognized word is
`passed to the Navigation Processor (9) by means of the
`bi-directional FIFO (34).
`
`l0
`
`15
`
`20
`
`25
`
`30
`
`35
`
`Spelling Checker
`
`In the English language (and in Spanish also) certain
`letters rhyme and can be easily confused by speech
`recognizers. Therefore, in this system, speech recogni-
`tion is enhanced by use of spelling checker software
`(module A5),
`to remove ambiguities associated with
`letters which rhyme in the English alphabet, such as
`“B” with “P”, “I" with “Y”, “J” with “K”. The spel-
`ling checker solves this by treating rhyming letters as
`nearly equivalent and using a scoring technique to pull
`the correct street name out of a number of possible
`spellings. Thus, the spelling checker makes speech input
`possible using imperfect speech recognizers. Without it,
`there would be too many errors and speech input would
`become impractical.
`The spelling checker is required only for the English
`alphabet. The numeric digits from 0 to 9 do not rhyme
`with each other and therefore speech recognition of
`numbers is relatively easy to accomplish. A spelling
`checker is not possible and is not required for recogniz-
`ing numeric digits.
`To illustrate the power of the spelling checker, let us
`assume that the driver wants to spell the street name
`BARBARA STREET. Due to mis-recognition,
`the
`computer hears DKRVJRK STREET. When scoring
`is applied, however, the rhyming letters D, V, B and A,
`J, K give BARBARA STREET the highest score and
`so BARBARA STREET is chosen as the most likely
`street name. The correctness of this process has been
`
`45
`
`50
`
`55
`
`60
`
`65
`
`5,274,560
`
`8
`verified many times in trial runs using prototype soft-
`ware and hardware.
`
`Creating Speech Output Records
`
`Digitized voice records are stored on the optical disc
`preferably in a highly compressed form using a Mu Law
`compression technique to achieve a compression of 64
`Kbits/sec. It is anticipated that an enhanced LPC en-
`coding technique may be used to achieve a compression
`of 13 Kbits/s while keeping the voice quality high.
`The voice records are created at a work station, such
`as an IBM PC compatible computer using the program
`of Appendix C, where an actor or actress speaks the
`street names and the guidance words, such as “TURN
`LEFT ON”, in his or her natural voice. The words are
`digitized, compressed and saved in a data base which is
`eventually placed on the optical disk.
`By compressing the speech, the time to retrieve the
`word from the disk becomes smaller and the amount of
`RAM memory required for buffering is smaller, thus
`saving the cost of additional RAM memory.
`This method is superior to voice synthesis and gives a
`natural, non-robotic sound. Since the optical disk con-
`tains sufficient space for digitized voice records, it is a
`cost effective way of implementing voice output.
`
`Disk Input functions
`
`The map data base and the compressed digitized
`voice records are stored on the optical disk (not shown).
`Additionally, to allow software updates, the software
`for both the Digital Signal Processor (4) and the Navi-
`gation Processor (9) are also stored on the disk. Both
`processors have minimal bootstrap programs stored in
`their respective on-chip or external ROMs (6 and l0)—-
`just enough to allow the software stored on the optical
`disk to be loaded into the RAMS (7 and 12).
`In order to read any particular sector on the disk, a
`signal is first sent to the Track Control Servo (15) via
`Switch S2 to open the tracking servo loop. Next, a
`slewing signal is sent to command the LASER Pickup
`(16) to move inward or outward. As the head moves
`past tracks on the disc, the servo loop generates a saw
`tooth shaped error function with a frequency which
`corresponds exactly to the rate at which track jumping
`is occurring. By counting saw tooth waves, the Digital
`Signal Processor (4) knows approximately on which
`track the read head is located.
`
`When the read head is positioned near or past the
`required track, the Digital Signal Processor (4) closes
`the servo loop, allowing the LASER Pickup (16) to
`acquire data and pass it on to the Signal Processor (18)
`for de-interleaving and error correction. The error cor-
`rected output from the Signal Processor is serial pulse
`train of 16 bit words. This output is a routed to the
`Digital Signal Processor (4) via Switch S1 to be con-
`verted from serial pulses to 16 bit words.
`If the data being read is map data, it is stored in FIFO
`(8) for use by the Navigation Processor (9). If the data
`being read are digitized voice records, the Digital Sig-
`nal Processor (4) may store them in its own RAM (7) to
`be decompressed and output as described earlier or in
`RAM 17.
`
`When Switches S1 and S2 are UP, the system is in the
`music mode and neither processor is active.
`
`Speech Output functions
`
`When the computer needs to speak to the operator,
`the Navigation Processor (9) using primarily modules
`
`13
`
`13
`
`

`
`9
`A2 and A6, places into the FIFO (9) a list of pointers
`(optical disk sector numbers) to the compressed, digi-
`tized words to be spoken.
`The Digital Signal Processor (4) retrieves the list
`from the FIFO (9), seeks to the correct sector number
`and reads the compressed records from the disc into
`RAM (7). Then it decompress the records and clocks
`the speech output data to the compact disk player’s
`Serial Analog To Digital Converter (21) via Switch S1.
`The output from the DAC is amplified by the left and 10
`right Audio Amplifiers (60 and 62) and sent to a pair of
`speakers or headphones.
`
`5
`
`Traffic Avoidance functions
`
`20
`
`In the future, when State and Federal agencies begin 15
`to broadcast digitized traffic information over reserved
`FM frequency channels, this invention will be able to
`utilize updated highway speed information in calculat-
`ing optimum routes. This gives the driver another use
`for the device, that of traffic avoidance.
`To achieve traffic avoidance, the Navigation Proces-
`sor (9) sends a signal to tune the FM Receiver (14) to
`the traffic avoidance frequency. The FM receiver’s
`output is demodulated by the DEMOD (12) and the
`digitized highway speed information is input by the 25
`Navigation Processor (9). If, during a trip, the computer
`finds that one of the highways to be used on the trip has
`become congested, it does the following actions:
`1. Calculates the delay which will be caused due to
`the highway slow down.
`2. If the delay exceeds five or ten minutes, the com-
`puter informs the driver of the delay and asks him if he
`wants to calculate an alternate route.
`3. If the driver agrees, the computer will calculate a
`route using the new speeds. If the route is different, the 35
`computer will tell the driver what the new route is,
`otherwise, it will tell the driver that his present route is
`still on the best route.
`
`30
`
`Map data base description
`The map data base is stored on the optical disk. The
`data base contains the following elements:
`Names list—a file of street names and pointers to
`corresponding digitized voice records. It is used for
`voice output of street names.
`Street index—a file of street name numbers, grid
`numbers, and address ranges. It is used to find the grids
`surrounding the operator’s source and destination ad-
`dresses.
`
`40
`
`45
`
`Level 1 grids—a file of street segments contained in 50
`the level 1 map grids. Level 1 grids are the most de-
`tailed and contain segments and linkages for (a) local
`streets, (b) major streets, (c) on-off ramps, (d) highway
`interchanges and (e) highways. Level 1 grids are about
`lXl mile in size. Four level one grids surrounding the 55
`source and destination points are read into RAM (12)
`prior to the route finding process.
`Level 2 grids—a file of street segments contained in
`the level 2 map grids. Level 2 grids are less detailed and
`contains segments and linkages for (a) major streets, (b) 60
`on-off ramps, (c) highway interchanges and (d) high-
`ways; local streets are omitted. Level 2 grids are about
`6X6 miles in size. Four level‘ 2 grids surrounding the
`source and destination points are read into RAM (12)
`prior to the route finding process.
`Level 3 grid—a file of street segments contained in
`the level 3 map grid. The level 3 grid has still less detail
`and contains segments and linkages for (a) on-off ramps,
`
`65
`
`5,274,560
`
`10
`(b) highway interchanges and (c) highways. There is
`only one level 3 grid and it encompasses one or more
`counties.
`
`Level 4 grid—a file of street segments contained in
`the level 4 map grid. The level 4 grid is the least detailed
`and contains segments and linkages for (a) highway
`interchanges and (b) highways. There is only one level
`4 grid and it covers the a very large area, for example,
`Northern California. Level 4 is only used for routing
`from city to city over the highway system.
`
`Voice data base description
`
`For data bases which cover a relatively small area,
`such as a single city, a single level grid may be used.
`
`Voice data base description
`
`The voice data base is a file of compressed voice
`records. The record lengths are variable and contain
`digitized street names and guidance phrases, such as
`“BEAR LEFT ONTO .
`.
`. ”, or “TURN RIGHT ON
`. .
`. ”. They are formed by an actress speaking the words
`into a microphone at a work station which compresses
`the records and plays them back for editing.
`
`Routing Algorithm
`
`The routing algorithm utilized in this system is based
`on the A‘ path finding algorithm described by Peter
`Hart et al., “A Formal Basis for the Heuristic Determi-
`nation of Minimum Cost Paths”, IEEE Transactions
`System Science and Cybernetics, Vol. SS-4, No. 2, July,
`1968. This path finding algorithm, also called a “Dy-
`namic Programming” algorithm, has the advantage
`over other types of search algorithms in that it locates
`the best path without having to search all possible paths.
`An example of such an A‘ algorithm is given in mod-
`ule A1. Various routing algorithm including the A‘ are
`discussed in the book “Artificial Intelligence” by Pat-
`trick Henry Winston, pages 89-120. In tailoring the A’
`algorithm for this navigator, a modification was per-
`formed. That is, travel time was optimized rather than
`travel distance. This was done by incorporating street
`speed codes into the data base.
`It is appreciated that the search can be conducted
`from are center to are center, rather than from node to
`node (nodes are points where two or more arcs inter-
`sect). It is believed that it takes less memory to store a
`network of arcs, and that it is easier to incorporate turn
`restrictions into the data base.
`
`The implementation of the A‘ algorithm of module
`A1 differs from the usual implementation with regard to
`the data base layout. In order to understand the differ-
`ence, some terms must first be defined.
`A digitized road map data base, called a GRAPH,
`consists of a list of straight line segments called ARCS,
`which represent the streets. Curved streets are broken
`into a series of straight line arcs in order to approximate
`the curve.
`The point at which two or more arcs intersect is
`called a NODE. A common example is the intersection
`of two streets in which four arcs meet at a central node.
`FIG. 8 shows an example of a graph containing 12
`nodes and l7 arcs. In the usual implementation, all the
`NODE information is placed in a NODE list and all the
`ARC information is placed in an ARC list.
`As a minimum, each node in the node list contains the
`node’s x, y coordinates, points to each