`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Road
`
`
`
`adominis-
`tration
`
`
`
`Individual
`
`communication
`center
`
`
`
`Information
`beacon
`
`Location
`1 beacon
`
`
`
`
`
`
`
`Automobile Navigation System Using
`Beacon Information
`
`
`
`
`
`
`
`Junkch Shima
`Takaharu Saito
`Hiroyuki Kanemitsu Yoshibumi Tanaka
`
`
`
`
`
`Toyota Motor Corporation
`
`
`
`
`1200 Mishuku, Susono,Sizuoka,410-11 ,Japan
`Tel 0559-97-2121 Fax 0559-97-4419
`
`
`
`
`
`
`
`
`
`
`
`ABSTRACT
`Various items of
`Road _and traffic information
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`road works,
`such as traffic conditions,
`information,
`
`
`
`
`
`
`
`
`
`
`
`
`location of car parks and available spaces etc., are
`A navigation and communication system utilizing
`
`
`
`
`
`
`
`
`
`
`
`transmitted from roadside beacons and may be selected
`roadside beacons
`is currently under
`
`
`
`
`
`
`for display on the digital map.
`development. This paper outlines the functions
`
`
`
`
`
`
`
`
`
`
`
`infrastructure of
`the system ( named
`and
`
`
`
`
`
`
`
`
`
`
`
`
`
`RACS), describes the in-vehicle equipment
`Route
`planning and
`The shortest route
`guidance
`
`
`
`
`
`
`
`
`
`
`
`
`between any two points can be calculated from stored
`developed by
`TOYOTA and reports the results of
`
`
`
`
`
`
`
`
`
`
`
`data and indicated on the digital map. If information
`field tests conducted in the Tokyo/ Yokohama
`
`
`
`
`
`
`
`
`
`
`regarding delays on or impassibility of the indicated
`system is considered to have
`The
`area.
`
`
`
`
`
`
`
`
`
`route is received from beacons, an alternative route
`considerable potential
`reducing and
`for
`
`
`is also displayed,
`improving road safety as well as being of great
`
`
`
`
`benefit to drivers.
`
`
`
`
`
`
`
`
`
`Personalcommunication Two-way communication for
`
`
`
`
`
`
`INTRODUCTION
`personal messages and fleet management etc.
`is
`
`
`
`
`
`provided via the communication service system.
`
`
`
`
`
`
`
`
`
`
`Driving an automobile today is
`becominc
`
`
`
`
`
`
`
`increasingly complex: The extension of
`the road
`Individual
`
`
`
`
`
`
`
`and highway network makes navigation more
`difficult,
`communication
`
`
`
`
`
`
`while the tremendous increase in vehicles has in many
`branch
`
`
`
`
`
`
`
`areas led to chronic traffic congestion. In order to
`
`
`
`
`
`
`
`
`promote road safety and ease congestion,
`an on-board
`a
`
`
`
`
`
`
`
`/ informational system based on roadside
`navigational
`
`
`
`
`
`
`al{ communication
`beacons will soon become indispensable. In this paper,
`
`
`
`
`
`
`a beacon Sy,
`authors present a prototype vehicle system
`the
`
`
`
`
`
`developed ta cperate in conjunction with the
`aN
`
`
`
`
`
`
`Z|
`¢
`communication network currently being established in
`
`
`
`
`
`
`
`Japan as a co-operative undertaking by the Public
`
`
`
`
`
`
`Works Reseach Institute of
`the Ministry of
`
`
`
`
`
`
`
`Construction and 25 private companies.
`The
`
`
`
`
`
`
`system provides the driver with such essential
`
`
`
`
`
`
`
`information as present
`location and traffic
`
`
`
`
`
`conditions, plots optimum and alternative route to the
`
`
`
`
`
`
`destination and enables
`limited two-way
`
`
`
`
`
`
`
`communication to be made. Field testing of
`the
`
`
`
`
`
`
`
`system is still being conducted. Here the
`results of
`the first two tests are discussed.
`
`
`OUTLINE OF RACS
`
`
`
`
`
`
`
`
`
`
`Road/Automobile Communication System ( RACS)
`
`
`
`
`
`
`
`
`
`
`
`is a network providing various services by means of
`
`
`
`
`
`
`
`Fig.? Road and automobile communication system
`roadside devices and a vehicle mounted computer.
`
`
`
`
`
`
`
`
`Fig.1
`shows the concept of RACS, which is based on
`
`
`
`
`
`
`intermittent narrow band digital data communication
`SystemConfiguration
`
`
`
`
`
`
`
`
`
`
`
`with limited range. Two-way individual communication
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`{i.e. private communication) for personal needs is
`Beacons are of three types.
`Beacons
`
`
`
`
`
`
`
`
`
`The location beacon (LB)
`transmits signals
`(i)
`currently under
`development and has not yet been
`
`
`
`
`
`
`
`
`identifying its location, i.e. secondary mesh code
`subjected to field testing.
`
`
`
`
`
`
`
`
`(the map reference number of the 1/25,000 scale maps
`
`
`
`
`
`
`
`Main Functions
`issued by the Geographical Survey Institute}, map
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`coordinates (x,y),
`link number (the number designated
`
`
`
`
`
`
`RACS are as follows.
`The main functions of
`to the road },
`link heading and beacon number.
`In
`
`
`
`
`
`
`
`
`
`addition other information of a constant nature may
`
`
`
`
`
`
`
`
`
`
`
`be transmitted.
`The dead reckoning
`Detection of vehicle location
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`(ii)
`The information beacon(IB)
`transmits both
`navigation device determines the present
`location in
`
`
`
`
`
`
`
`
`
`
`
`
`
`location signals and relays transient
`road and
`real time using the vehicle directional and distance
`
`
`
`
`
`
`
`traffic information received via a cable.
`(See Table
`sensors and
`corrects any error when a signal
`is
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`received from a roadside beacon. The location is
`1.)
`
`
`
`
`
`
`(iii) The individual communication beacon (ICB) will
`continuously indicated on the digital road map display.
`
`
`
`
`
`
`
`establish two-way radio communication with the
`
`
`
`
`
`
`vehicle. The ICB itself will be connected to the
`communication service system center by cable. The
`
`
`
`
`
`
`
`
`
`
`
`CH2789-6/89/0000-0139501.00 © 1989 IEEE
`
`
`
`
`
`
`
`
`
`
`139
`
`Page 1 of 7
`
`Unified Patents Exhibit 1011
`
`Page 1 of 7
`
`Unified Patents Exhibit 1011
`
`

`

`
`
`
`
`
`
`
`
`
`
`
`
`
`functions of the ICB may be expanded to include those
`of the IB.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`In the first two field tests, inductive radio
`
`
`
`
`
`
`
`was used for beacon transmissions. Currently microwave
`based communication is being tested. The
`
`
`
`
`
`
`
`specifications of the inductive radio are given in
`Table 2.
`
`
`
`
`Traffic control and communication centers
`
`
`
`
`
`
`
`
`
`
`
`
`The traffic control center, which is
`
`
`
`
`
`
`
`
`
`administered by the relevant local road authority,
`
`
`
`
`
`
`
`outputs road and traffic data based on the map and
`link numbers to the information beacons. The data is
`
`
`
`
`
`
`
`
`
`updated at 5-minute intervals,
`
`
`
`
`
`The communication service system center and
`
`
`
`
`
`branches act as an interface for personal messages to
`and fran particular vehicles.
`
`
`
`
`Table 1 Road and traffic information
`
`
`
`
`Link No., Direction,
`
`
`Congested lane, Cause,
`
`
`
`Level of congestion, etc.
`
`
`
`
`
`
`Traffic accident
`Link No., Direction,
`
`
`Cause, etc.
`
`
`
`
`
`
`Link No., Direction, etc.
`
`
`
`
`
`Congestion
`
`Roadwork
`
`Antenna
`
`
`Receiver
`
`
`
`
`
`
`Processing Unit
`
`CPC9OSO1VM21)
`
`|
` Touch-
`RS232C
`
`Sensitive
`
`Sensor
`Switch
`
`
`
`
`Wheel
`Revolution
`Sensor
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Esc ECU
`Gyro-
`Gyro ECU
`scope
`
`
`
`
`Fig.2 Block diagram of in-vehicle system
`
`
`
`Map Display and Data
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`CRT
`and memory unit The core of the man-machine
`
`
`
`
`
`
`interface is the display unit. Ideally the CRT should
`
`
`
`
`
`
`be as large as possible to facilitate use, but a
`
`
`
`
`
`limit is imposed by the available space. As viewing
`
`
`
`
`
`
`
`angle is also an important consideration, the test
`car made use of a 6 inch CRT mounted in the center of
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`the dash board (see Fig.3). In the prototype system,
`
`
`
`
`
`
`
`an IC memory (ROM) was used to store map data since
`the field test area is reasonably smali. For
`
`
`
`
`
`
`
`
`
`
`
`
`commercial systems, a CD-ROM such as used in the
`
`
`
`
`
`
`ELECTRO MULTIVISION system would appear to be the
`
`
`
`
`
`
`
`
`most. promising media for data storage. Specifications
`
`
`of the CRT and memory device are given in Table 3.
`
`
`
`
`
`Fig.3 Test car
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Digital map data Stored map data were campiled fram
`
`
`
`
`
`
`
`
`the database prepared by PWRI. As shown in Table 4,
`
`
`
`
`
`
`
`four scales of map are available. The smaller scale
`
`
`
`
`
`
`
`
`
`maps are provided to enable selection of the larger
`
`
`
`
`
`
`scale maps (1:115000 and 1:28500), which are used for
`
`
`
`
`
`
`navigation. Fig.4 shows an example of the largest
`
`
`
`
`
`
`
`scale navigation maps. The display changes
`
`
`
`
`
`
`
`automatically when the vehicle moves
`from one
`navigation map to another. Each navigation map
`
`Transmission antenna|Ferrite core coil
`
`
`247. 2KHz
`Frequency
`Transmission power
`Very weak
`
`MSK
`Modulation
`9600bps
`Transmission speed
`Transmission data
`IB: about 8000bits
`LB: 136bits,
`
`
`
`
`
`Ferrite core coil
`
`
`
`
`
`Car antenna
`
`
`Road/lane regulation
`
`
`
`
`
`
`
`
`
`Link No., Direction,
`
`
`Regulated lane,
`
`
`Nature of regulation,
`
`
`Cause, etc.
`
`
`
`
`
`
`
`Time needed to
`Link No., Direction,
`
`
`
`Tine
`travel link length
`
`
`
`
`
`
`
`
`Table 2 Inductive radio specifications
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`In-vehicle equipment consists
`In-vehicle equipment
`
`
`
`
`
`
`
`of a dead reckoning device, a ROM unit in which map
`data are stored, CRT display, antenna and receiver,
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`The map database was prepared by the Public Works
`
`
`
`
`
`
`
`
`
`Research Institute (PWRI) and comprises twelve files,
`
`
`
`
`
`
`
`
`e.g. link file, node (or intersection) file, railway
`
`
`
`
`file, facility location file etc. The data covers an
`
`
`
`area of approximately 350Km¢including southwestern
`
`
`Tokyo, Kawasaki and northern Yokohama.
`
`
`
`DEVELOPMENT OF IN-VEHICLE EQUIPMENTS
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Fig.2 shows a block diagram of the prototype in-
`
`
`
`
`
`
`vehicle system developed by the authors. The system is
`
`
`
`
`
`
`composed of a dead reckoning device with geomagnetic
`
`
`
`
`
`
`sensor, gyroscope and wheel revolution sensor; a 6
`inch CRT with touch-sensitive switches; a receiver; a
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`map data storage unit and a processing unit which
`
`
`
`
`controls the system. A 16 bit personal computer (NEC
`
`PC9801VM21) was used as the processor.
`
`
`
`
`
`
`
`
`
`The prototype system was installed in an '88
`
`
`
`
`
`model TOYOTA CROWN as a sub-system of the multi-
`
`
`purpobe display unit called ELECTRO MULTIVISION.[1]
`
`
`
`
`140
`
`Page 2 of 7
`
`Unified Patents Exhibit 1011
`
`Page 2 of 7
`
`Unified Patents Exhibit 1011
`
`

`

`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`shown in Figs 5 and 6 respectively.
`overlaps neighbouring maps by 10% so that the driver
`
`
`
`
`
`
`
`
`
`
`
`can easily follow the transition. In addition, a map
`Table 4 Stored map contents
`
`
`
`
`
`
`
`
`of the Tokyo Metropolitan Expressway System and a map
`
`we epee
`
`
`
`
`
`
`of car park locations are provided. All maps are
`
`
`
`
`displayed in the north-up mode, i.e, north is to the
`
`
`
`
`
`
`
`
`
`
`Scale
`Scale: Scale
`Seale
`top of the screen.
`13380,00 i 1:190,00|1:115,00|1:28,500
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Contents Area dis|Area dis|Area dis|Area dis
`
`
`
`
`
`
`played
`played
`played
`played
`
`
`
`
`
`
`
`45*37Km|22*18Km|14*1]Km|3.5%*2.5K
`Type of display|CRT
`
`
`
`
`
`
`
`
`
`No. of
`No. of
`No. of
`No. of
`
`6 inches
`Size
`
`
`
`
`
`
`
`
`Resolutions
`3208240
`
`
`naps 4|maps1 {maps 12! maps 182
`
`
`
`
`
`
`
`Location
`Center of dashboard
`
`
`
`
`
`
`Land
`Oo
`OQ
`oO
`Qo
`|
`
`
`
`
`|
`Type of memory
`IC memory
`+
`+
`|
`
`Memory capacity|8MBytes :
`Sea
`'
`Oo
`oO
`Oo
`°
`
`F
`+
`
`
`
`
`
`
`
`
`
`
`
`
`
` po—_
`
`
`Lakes and narshes |
`-
`Oo
`oO
`Oo
`
`
`
`Rivers
`-
`-
`Oo
`Oo
`
`
`
`
`
`
`
`
`
`Le
`
`Names
`
`-
`
`
`
`-
`
`-
`
`oO
`
`oO
`
`Oo
`
`al
`
`
`
`oO
`
`oO
`
`oO
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Y
`
`
`
`
`Fig.5 Flowchart of dead reckoning
`
`
`
`
`
`
`
`
`
`
`
`
`The control unit compares location
`Error correction
`data received from a beacon with the calculated
`
`
`
`
`
`
`
`
`
`
`location and corrects any errors. Because of the
`intermittent communication and processing time,
`
`
`
`
`
`
`
`
`144
`
`—T-
`
`Page 3 of 7
`
`Unified Patents Exhibit 1011
`
`
`
`Table 3 Display and memory unit specifications
`
`
`
`
`
`
`
`
`
`oO
`Expressways
`Oo
`9
`oO
`
`
`
`
`
`
`Toll roads
`-
`oO
`oO
`oO
`
`
`
`
`
`National roads
`-
`Oo
`Oo
`oO
`
`
`T
`
`
`
`
`
`Prefectual roads
`oO
`-
`-
`Oo
`
`
`
`
`
`
`
`Municipal roads
`-
`-
`-
`oO
`
`
`
`
`
`
`Rail
`-
`-
`oO
`°
`
`
`
`
`ways
`|
`L
`
`
`
`
`Land-}buildings - - - Oo
`
`
`
`
`
`
`
`
`
`
`
`narks
`
`
`Fig.4 Navigation map (1:2850u)
`
`
`
`
`
`beacons
`Detection of Vehicle Location
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`fo-
`Road names
`
`
`
`
`
`
`
`
`The dead reckoning device calculates the present
`fret ned
`ape
`
`
`
`position of the vehicle from directional and distance
`
`
`
`
`
`
`Place names - -
`
`
`
`
`
`
`
`data. The calculated position is displayed on the
`
`navigation map. Accumulated errors in the dead
`
`
`
`
`
`
`
`
`
`
`
`
`reckoning are corrected when the vehicle passes an LB
`
`
`
`
`or IB. Consequently the navigational system operates
`with a high degree of accuracy.
`
`
`
`
`
`
`
`
`
`
`
`
`
`In order to minimize any
`Dual directional sensors
`
`
`
`
`
`
`
`error in directional data, bothaflux
`gate type
`
`
`
`
`
`geomagnetic sensor and vibration type gyroscope are
`
`
`
`
`
`
`
`used to calculate heading. A geomagnetic sensor is an
`
`
`
`
`
`efficient means of detecting heading but its accuracy
`
`
`
`
`
`is affected by regional differences in magnetic
`
`
`
`
`
`
`
`declination and by interference caused by buildings,
`
`
`
`
`
`
`
`tunnels, bridges,
`railways and large vehicles which
`
`
`
`
`
`are travelling alongside. On
`the other hand,
`a
`
`
`
`
`
`gyroscope, although unaffected by magnetic declination
`and interference, accumulates directional errors
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`because it is subjected to drift as time passes.
`
`
`
`
`
`
`the TOYOTA dead reckoning system utilizes data
`Hence,
`from both sources and weights them appropriately.
`
`
`
`
`
`
`
`
`
`
`
`
`Distance sensor Wheel sensors producing 48 pulses
`
`
`
`
`
`
`per revolution were adopted as the distance sensor and
`mounted on the non-driving (i.e.
`front) wheels.
`
`
`
`
`
`
`
`
`
`
`
`Calculation and displayof location Directional and
`
`
`
`
`
`
`
`distance data are continuously input to the control
`unit, which computes
`the movement vector of the
`
`
`
`
`
`
`
`
`
`
`
`
`vehicle at quarter-second intervals and outputs the
`
`
`
`
`
`
`
`location in terms of navigation map co-
`present
`
`
`
`
`
`
`
`ordinates every four intervals, Thus the position of
`
`
`
`
`
`
`
`vehicle location mark on the CRT is updated every
`second. The flowchart and calculation principle are
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Setting of initial location
`
`
`
`
`
`
`
`
`Input of geomagnetic sensor data
`
`
`
`
`
`Input of gyroscope data
`
`
`
`
`
`
`
`
`
`
`
`
`Page 3 of 7
`
`Unified Patents Exhibit 1011
`
`

`

`
`
`
`Pe whereP=Position
`
`
`
`
`
`
`
`
`
`
`
`
`D=Distance Traveled
`
`@ =Heading
`
`
`
`
`Fig. 6 Dead reckoning navigation computation
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`beacon location data is accurate to within +5m, but
`
`
`this error is too small to effect the accuracy of the
`navigation system,
`
`
`
`
`Reception and Display of Transient Information
`
`
`
`
`
`
`
`
`
`
`
`
`The receiver utilizes a
`Receiver
`and
`antenna
`
`
`
`
`
`
`
`digital circuit for modulation and demodulation of the
`
`
`
`
`
`
`
`signal anda control unit including an 8-bit micro-
`
`
`
`
`
`
`computer. The antenna is a ferrite core coil mounted
`
`Pe
`
`
`
`
`
`
`
`on the trunk lid (see Fig.7).
`
`
`
`
`
`
`Fig.7 Inductive radio antenna
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`CRT display As stated above, information received
`
`
`
`
`
`
`from an IB, such as congestion, road works and local
`
`
`
`
`
`
`
`traffic regulations, are displayed on the CRT. Careful
`
`consideration was given to the content and manner of
`
`
`
`
`display.
`
`
`
`
`
`
`The principal features are as follows:
`
`
`
`
`
`
`
`(i) When traffic information is received, words to
`
`
`
`
`
`
`
`this effect are superimposed on the navigation map.
`
`
`
`
`
`
`(ii) The driver may opt to view this information
`
`
`
`
`
`either on the navigation map in use or on the Tokyo
`
`
`
`
`
`Metropolitan Expressway.
`(See Figs 4 and 8.)
`
`
`
`
`
`
`
`
`(iii) The information itself is expressed by a
`
`
`
`
`
`
`
`
`flashing color along the affected part of the road:
`
`
`
`
`
`
`
`
`violet for congestion, black for road or lane closure,
`
`
`
`
`
`
`
`red for an accident and yellow for road works.
`
`
`
`
`
`
`(iv)
`If the navigation map is showing the shortest
`
`
`
`
`
`
`route (see below) and information regarding road or
`
`
`
`
`
`
`
`lane closure or congestion of the route is received,
`
`the driver may select a textual display giving
`details.
`
`
`
`
`
`
`
`
`
`
`
`
`
`Fig.8 Display of congestion on Metropolitan
`Expressway
`
`
`Shortest Route
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`The shortest route between any two given points
`
`
`
`
`
`
`is calculated using data regarding link length and
`
`
`
`
`
`
`
`flow direction at intersection ( e.g. no right-hand
`
`
`
`
`
`
`turn etc.). This route is displayed on the navigation
`
`
`
`
`
`maps in a flashing green color. A feature of the
`
`
`
`
`
`system is that an alternative route is calculated and
`
`
`
`
`
`
`
`
`displayed if signals from an IB advise of congestion
`
`
`
`
`
`
`or closure of the planned route. When data are
`
`
`
`
`the program will be extended to enable the
`available,
`quickest route to be calculated as well.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Input
`The driver inputs the departure point and
`
`
`
`
`
`
`destination on the appropriate navigation maps, using
`
`
`
`
`
`
`
`
`the touch-sensitive switches on the screen to move
`
`
`
`
`
`
`
`
`the cursor. He must also input whether or not toll
`
`
`
`
`
`
`
`roads are to be used. The route is displayed from the
`
`
`
`
`
`
`
`nede of origin (i.e.
`the intersection closest to the
`
`
`
`
`
`
`actual position of the vehicle, determined from the
`
`
`
`departure point coordinates and vehicle heading } to
`the node of destination.
`
`
`
`
`
`
`
`
`
`
`
`
`To minimize computation
`Algorithm of route search
`
`
`
`
`
`time, a practical algorithm adequate for navigation
`
`
`
`
`
`
`
`
`was developed.[2] Based on Nicolson's bidirectional
`
`
`
`
`
`path finding algorithm,
`the method deals with an O-D
`
`
`
`
`
`
`(origin-destination) pair problem and calculates an
`
`
`
`
`
`
`approximate optimum. The main features are:
`
`
`
`
`
`The network for search is restricted to the
`(i}
`
`
`
`
`elliptical area between O and D, the size of which
`
`
`
`
`
`
`
`changes in proportion to the distance.
`
`
`
`
`
`
`A node amount equality method, whereby the
`(ii)
`
`
`
`
`
`
`
`number of nodes on the possible paths from O is
`
`
`
`
`
`equal to the number on the possible paths from D, is
`
`
`
`
`
`used to establish the shortest route.
`
`
`
`
`
`
`(iii) The principle of network degeneration is
`
`
`
`
`
`
`
`applied. The initial search from O and D expands
`
`
`
`
`
`
`along all classes of roads. However the network is
`
`
`
`
`
`degenerated by eliminating any lower grade road if a
`
`
`
`
`
`
`
`higher grade road may be fol lowed.
`
`
`
`
`
`(iv)
`The revised origin method enables fast
`
`
`
`
`
`
`
`calculation of a rerouting should the driver stray
`
`
`
`
`
`
`
`from the planned route. If the vehicle passes an LB
`
`
`
`
`
`
`or IB that is not on the designated route,
`the
`
`
`
`
`
`
`
`shortest route from that point to D is calculated,
`
`
`
`
`
`
`
`making use of the previously computed possible paths
`
`
`
`
`
`
`from D, Figs 9 and 10 respectively show the concept
`
`
`
`
`
`and efficacy of
`the developed algorithm, which
`
`
`
`
`
`achieves a reduction in camputation time of up to 90%
`campared to the single source algorithm
`
`
`
`
`
`
`
`
`
`
`
`
`
`Database for route search The in-vehicle database
`for route search was compiled from the previously
`
`
`
`
`
`
`
`142
`
`
`
`Page 4 of 7
`
`Unified Patents Exhibit 1011
`
`Page 4 of 7
`
`Unified Patents Exhibit 1011
`
`

`

`
`Og
`
`
`
`
`
`
`Dijkstra
`
`Single directinal
`
`distance equality
`
`
`
`
`
`Nicolson
`
`Bidirectinal
`
`distance equality
`
`
`
`
`
`
`
`
`
`
`on the search (e.g. whether or not toll roads are to
`
`
`
`
`
`
`
`be used, road restrictions on vehicle type,
`time-
`
`
`
`
`based traffic regulations etc.).
`
`
`
`
`
`
`(iii) The database is well matched with the stored
`
`
`
`
`
`
`
`
`map data. The network for the field experiment area
`
`
`
`
`
`
`contains 2867 nodes and 4219 links.
`
`
`
`
`
`
`
`
`
`
`
`Detour route search IB data concerning congestion is
`
`
`
`
`expressed as a congestion factor (corresponding to
`
`
`
`
`
`
`
`link flow rate). When such information is received,
`
`
`
`
`
`
`
`the shortest route from the preceding node to Dis
`
`
`
`
`
`
`
`calculated (as above) in terms of total link cost
`
`
`
`
`
`
`{distance x congestion factor) and displayed on the
`CRT.
`
`
`
`
`
`Node amount equality
`
`
`
`ef
`
`
`Elliptical boundary
`
`
`
`
`
`Rerouting area
`
`
`
`
`
`
`
`
`
`Display of Roadside Information
`
`
`
`
`
`
`Roadside information obtained from an IB may be
`
`
`
`
`
`
`
`selected for displayed on the CRT. Fig.11 shows an
`
`
`
`
`
`
`example of car park information. Space availability,
`
`
`
`
`
`
`charge and opening hours are displayed.
`ROAD TEST RESULTS AND EVALUATION
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`The road test area is shown in Fig.12. A total
`
`
`
`
`
`
`
`of 93 beacons including two IBs were installed along
`
`
`
`
`major roads in this area.
`
`
`
`
`
` -
`
`
`
`
`
`
`
`
`
`
`
`77 /
`
`
`
`
`
`
`Fig.12 Field experiment area [3]
`
`Yokohama
`
`
`
`143
`
`
`
`
`
`Network cegeneration
`Rerouting
`
`
`
`
`
`Fig.9 Concept of route search algorithm
`
`
`
`Sec.
`
`
`
`
`.
`Dijkstra
`
`
`
`/ Nicolson
`
`200+
`
`
`feNode equality
`
`
`
`
`
`po
`L
`
`L
`
`'
`
`L
`
`
`
`
`
`
`a
`
`
`100F
`
`
`
`
`
`
`a=
`
`_c
`
`oO
`
`.>
`
`Q=o
`
`O&
`
`
`
`
`
`[
`
`0
`
`
`
`
`NE@DG@EB
`Elliptical
`boundary (EB) S
`
`
`5
`
`
`
`
`
`30
`25
`15
`10
`20
`
`
`
`Route distance between 0-D
`
`
`
`
`
`35
`
`
`
`Km
`
`
`
`
`Fig.10 Comparison of camputation times
`
`
`
`
`
`mentioned digital map database and is characterised
`
`
`as follows:
`
`
`
`
`
`
`(i)
`The file volume is as small as possible.
`
`
`
`
`
`
`
`(ii) The database can meet options of and limitations
`
`
`
`
`
`
`
`Page 5 of 7
`
`Unified Patents Exhibit 1011
`
`Page 5 of 7
`
`Unified Patents Exhibit 1011
`
`

`

`an Qo o
`
`=~ So Q
`
`
`
`w ao o
`
`Locationerror - o ao
`
`
`
`
`Navigation Accuracy
`
`
`
`
`
`
`Tests were conducted along various courses and
`
`
`
`
`
`
`the error in dead reckoning was recorded at each LB.
`
`
`
`
`
`
`
`Fig.13 plots the relationship between navigation error
`
`
`
`
`
`
`
`
`and distance between beacons. As may be seen,
`the
`
`
`
`
`
`average accumulated error is approximately 4% of the
`
`
`
`
`
`
`
`driving distance between beacons, which in the case of
`
`
`
`
`
`
`
`the average beacon interval of 5Km means that
`
`
`
`
`
`
`positional error is 200m or less. In some instances
`
`the accumulated error was more than 7%. This is
`
`
`
`
`
`
`
`
`
`
`
`
`
`thought to be because the gyroscope cannot compensate
`
`
`
`
`
`
`
`for small deviations in compass readings due to local
`
`
`
`
`
`
`
`magnetic sources. However, the results suggest that
`
`
`
`
`
`
`
`with more beacons, especially in the vicinity of local
`
`
`
`
`
`
`magnetic sources, accurate navigation will be possible
`
`
`
`
`
`
`
`the
`even with a simple device. Fig.14 shows
`
`
`
`
`
`differences between car headings as calculated by dead
`
`
`
`
`
`
`reckoning and link headings at beacons. Data such as
`
`
`
`
`
`
`these can be used to further improve navigation
`
`accuracy.
`
`
`
`7% error rate
`
`
`
`
`
`
`“e
`
`4% error rate
`
`
`
`
`
`
`
`
`
`
`Map Legibility
`
`
`
`
`
`
`
`
`Screen size, map scale and colors were judged to
`
`
`
`
`
`be reasonable. To improve man-machine interface, it
`
`
`
`
`
`
`
`
`is thought that functions such as map scroll, map
`
`
`
`
`
`
`
`rotation(to permit heading up mode) and zoom
`
`
`
`capability should be examined.
`
`
`
`Information Data Reception and Content
`
`
`
`
`
`
`
`
`Data from the IBs were received without error.
`
`
`
`
`
`
`
`
`It should perhaps be pointed out that because of the
`
`
`
`
`
`
`inductive radio used in these tests, transmission
`rate is rather slow and the vehicle must be within
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`range of the IB for approximately one second to
`
`
`
`
`
`
`receive total information. For this reason, the IBs
`
`
`
`
`
`
`were located at toll booths. Further development of
`
`
`
`
`RACS will concentrate on microwave transmission to
`
`
`
`
`
`
`enable data to be received while travelling.
`
`
`
`
`
`Because the road/traffic information was
`
`
`
`
`
`
`
`detailed and was updated every five minutes, it was
`
`
`
`
`
`
`
`
`felt that this information is very helpful for city
`
`
`
`
`
`
`
`driving. Furthermore the visual display enable the
`
`
`
`
`
`
`driver to quickly discern whether the information is
`
`
`
`
`
`
`relevant or not. However, a speech mode system
`
`
`
`
`
`
`capable of replay would also be beneficial in many
`circumstances.
`
`
`
`
`Route Search
`
`
`
`
`the route search were most
`The results of
`
`
`
`
`
`
`
`
`
`
`
`
`
`encouraging.
`In most cases,
`the indicated route
`
`
`
`
`
`
`
`
`coincided with the route which the test drivers
`
`
`
`
`
`
`
`selected either from local knowledge or from printed
`
`
`
`
`
`
`
`
`sheet maps, and sometimes drivers conversant with the
`
`
`
`
`
`
`
`test area were made aware of a better alternative to
`
`
`
`
`
`
`
`
`
`the route that they would have chosen. The route
`
`
`
`
`search function is therefore judged to be a
`
`
`
`
`
`considerable aid to drivers who are in an unfamiliar
`
`
`
`
`
`
`
`area. Initial calculation of the shortest route took
`
`
`
`
`
`
`about 20 seconds on average. For practical purposes,
`
`
`
`
`
`
`
`faster algorithms must be developed so that this time
`
`
`
`
`
`
`can be reduced to around five seconds. Because of the
`
`
`
`
`
`
`
`
`
`time needed to apply the congestion factors to the
`
`
`
`
`calculation of
`link costs, computation of an
`
`
`
`
`
`alternative route generally required 90 seconds,
`
`
`
`
`
`
`
`
`which was far from practical as the driver often had
`to make a decision at an intersection before the
`
`
`
`
`
`
`
`
`
`
`
`calculated alternative was available. Also, as
`
`
`
`
`
`
`previously mentioned, search of the quickest route
`
`
`
`
`
`
`
`
`will probably prove: of greater value. Thus for future
`
`
`
`
`
`
`systems,
`improved software and hardware must be
`
`
`
`
`
`
`
`developed and the database must be revised. Further
`
`
`
`
`
`
`consideration should also be paid to the manner of
`
`
`
`
`
`
`presentation. For example, aural guidance in addition
`
`
`
`
`
`
`
`to the visual display would probably be welcomed by
`
`
`many drivers.
`
`CONCLUSIONS
`
`
`
`
`
`
`
`Road/Automobile Communication System (RACS) is
`
`
`
`
`being developed by private corporations in
`
`
`
`
`
`
`
`conjunction with the Public Works Research Institute.
`
`
`
`
`
`
`
`The system is based on roadside beacons which
`
`
`
`
`transmit information to passing vehicles.
`
`
`
`
`
`
`Field testing of the in-vehicle system developed
`
`
`
`
`
`
`
`
`by TOYOTA indicates that the navigation and route
`
`
`
`
`
`search functions are of great benefit to drivers in
`
`
`
`
`
`
`
`an unfamiliar area. However, route search calculation
`
`
`
`
`
`
`
`time must be reduced, especially in the case of route
`
`
`
`
`
`
`
`revision in response to incoming data. In the present
`
`
`
`
`
`system man-machine interface is accomplished visually
`
`
`
`
`
`
`and it is thought that an aural interface is highly
`
`
`
`
`
`desirable, It will therefore be necessary to develop
`
`
`
`
`
`
`a system whereby information can be imparted by a
`
`
`synthesized voice.
`
`
`
`
`
`
`
`300
`
`200
`
`100
`
`
`02 4
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`8&
`6
`16 18 20 22 246 26 Km
`10 12 14
`Distance between beacons
`
`
`
`
`
`
`
`
`Fig.t3 Relationship between navigation error and
`distance interval
`
`
`
`
`
`Incidence
`
`
`
`
`-10
`
`
`144
`
`-5
`
`5
`
`10 Degree
`
`0
`Heading error
`
`
`
`
`
`
`Fig.14 Heading error at beacon points
`
`
`
`Page 6 of 7
`
`Unified Patents Exhibit 1011
`
`Page 6 of 7
`
`Unified Patents Exhibit 1011
`
`

`

`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`To increase data transmission speed and to enable two-
`
`
`
`
`
`way communication to be established,
`a microwave
`
`
`
`
`
`
`
`transmission system is currently under development and
`is scheduled for testing in the near future.
`
`ACKNOWLEDGMENTS
`
`
`
`
`
`
`
`
`
`
`
`
`
`The development in this paper was carried out
`
`
`
`
`
`
`
`in the project "Road/Automobile Communication System",
`
`
`
`
`
`
`
`under a grant from the Public Works Research Institute
`
`
`
`
`
`
`
`of the Ministry of Construction. The authors thank
`
`
`
`
`
`
`
`persons concerned to promote the project and the
`
`
`
`
`
`
`public demonstration. The authors also wish to fully
`
`
`
`
`
`
`
`acknowledge to H. Tsuji of Toyota Central R&D Labs.
`
`
`
`
`
`
`and A. Uzu of Toyota Motor Corporation for their
`
`
`
`
`
`
`support to develop the in-vehicle navigation system
`and for the discussions on the project.
`
`REFERENCES
`
`
`
`
`
`
`1] Y. Shoji et al.,
`"Toyota Electro Multivision"
`SAE880220 , 1988 ,pp. 33-38.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`H. Tsuji et al.,
`"A Fast Shortest Path Method for
`
`
`
`
`
`In-vehicle Navigation System"
`Sth World
`The
`
`Conference of Transport Research (WCIR), Yokohama,
`Japan ,1989.
`
`
`
`
`
`
`
`
`
`S. Takaba et al.,
`"Experimental Study on
`
`
`
`
`
`
`Road/Automobile Communication System in Japan"
`
`
`
`The 18th International
`Symposium on Automobile
`Technology & Automation (ISATA)
`
`
`
`
`
`
`
`
`
`
`4 oa Kk,
`Ishikawa et al.,
`"Digital Map on CD (Called @
`Information)" SAE880221 ,1988,pp. 39-44.
`
`
`
`
`
`
`
`
`
`“An Overview of AMTICS"
`
`
`International Congress
`on Transportation
`Electronics Proceedings,1988 ,pp.219-228.
`
`2
`
`3
`
` 5) H. Okamoto et al.,
`
`
`
`
`
`
`
`
`
`
`
`145
`
`Page 7 of 7
`
`Unified Patents Exhibit 1011
`
`Page 7 of 7
`
`Unified Patents Exhibit 1011
`
`