`
`BEFORE THE PATENT TRIAL AND APPEAL BOARD
`
`In re U.S. Patent No. 7,268, 703
`
`Filed:
`
`Issued:
`
`Sep. 18,2003
`
`Sep. 11, 2007
`
`Named Inventors:
`
`Darrin W. Kabel, Steven J. Myers
`
`Original Assignee:
`
`Garmin Ltd.
`
`Title:
`
`Methods, systems, and devices for cartographic
`alerts
`
`DECLARATION OF CHRISTINE MIDDLETON
`
`I, Christine Middleton, make this declaration in connection with
`
`the petition for inter partes review submitted by Petitioner for U.S. Patent
`
`No. 7,268,703 (''the 703 Patent"). All statements herein are made of my
`
`own personal knowledge. I am over age 21 and otherwise competent to
`
`make this declaration. I have not received any compensation in return for
`
`making this declaration and have no financial or other interest in the
`
`Petitioner, the Patent Owner, or the outcome of this or any other legal
`
`proceedings relating to the 703 Patent.
`
`1.
`
`I am the Associate Director (Content and Discovery) of
`
`Libraries, Research and Learning Resources at
`
`the University of
`
`Nottingham. I attended the University of Nottingham as an undergraduate
`
`and graduated with a degree in mechanical engineering in 1980.
`
`I have
`
`1
`
`Navico Ex. 1014
`
`
`
`been employed by the University of Nottingham in positions relating to
`
`library and information services continuously since 1993. Specifically, I
`
`served as (1) the Faculty Team Leader (Science and Engineering) for the
`
`Information Services department from 1993 to 2009; (2) the Head of
`
`Academic Services for the Information Services department from 2009 to
`
`2014; and (3) the Associate Director (Content and Discovery) of Libraries,
`
`Research and Learning Resources-my current position-from 2014 to the
`
`present.
`
`2.
`
`As a result of my employment experience, I am intimately
`
`familiar with and have personal knowledge of both the University of
`
`Nottingham's current library policies and procedures and those that were in
`
`place in 2002, including the policies and procedures regarding the receipt,
`
`indexing, and public availability of student theses and dissertations.
`
`3.
`
`The University of Nottingham is a premier global research
`
`institution that originated with the 1881 founding of Nottingham's first civic
`
`college and was officially chartered as the University of Nottingham in
`
`1948. The University has campuses in England, Malaysia (opened 2000),
`
`and China (opened 2004). The University of Nottingham library system has
`
`over one million printed documents and, based upon my personal
`
`experience, has been frequently utilized by researchers in a wide variety of
`
`scientific and technical fields for decades.
`
`4.
`
`According to standard University of Nottingham library
`
`policies and procedures that were in effect in August 2002, student theses
`
`and dissertations are indexed in the library catalogue and are made freely
`
`available to both the faculty and student body of the University, and the
`
`general public. The library catalogue is electronically searchable by subject,
`
`2
`
`2
`
`
`
`author, and keyword, and was searchable in this way in August 2002.
`
`5.
`
`The University of Nottingham possesses a copy of a
`
`dissertation by Wichert J. de Jong entitled Automated Route Planning - A
`
`Network-Based Route Planning Solution for Marine Navigation (the "de
`
`Jong Dissertation"). According to University of Nottingham records, the de
`
`Jong Dissertation was indexed in the University library catalogue and made
`
`available to the public on August 6, 2002, and was removed from public
`
`availability on April 26, 2013. Exhibit A to this declaration is the original
`
`de Jong Dissertation that the University of Nottingham added to its library
`
`catalogue and made available to the public between 2002 and 2013.
`
`6.
`
`Exhibit B to this declaration is a screenshot of the University of
`
`Nottingham library electronic catalogue entry for the de Jong Dissertation
`
`that I generated from University of Nottingham's electronic recordkeeping
`
`system. In accordance with standard University of Nottingham policies and
`
`procedures, the "List of Catalogers" field contains a record of when a
`
`particular resource was added or removed from the catalogue. As is
`
`apparent from Exhibit B, the de Jong Dissertation was added to the
`
`catalogue on "06/08/02" which (under standard European date abbreviation
`
`conventions) corresponds to August 6, 2002.
`
`7.
`
`Accordingly, University of Nottingham
`
`library
`
`records
`
`demonstrate that the de Jong Dissertation was catalogued in the University
`
`of Nottingham library and available to both the University community and
`
`the general public from August 6, 2002 to April 26, 2013.
`
`I affirm and declare under penalty of perjury under the laws of the
`
`United States of America that all statements in this declaration made of my
`
`own knowledge are true and that all statements made on information and
`
`3
`
`3
`
`
`
`belief are believed to be true. I understand that willful false statements and
`
`the like are punishable by fine, imprisonment, or both (18 U.S.C. § 1001),
`
`and may jeopardize the validity of an application or any patent issuing
`
`thereon.
`
`Date
`
`Christine Middleton
`
`Signature, Notary Public
`
`Richard Brian Hammond
`Notary Public
`England and Wales
`2 Kayes Walk
`Nottingham
`NG1 1 PZ
`
`4
`
`4
`
`
`
`teed
`pai:
`
`et
`
`are el
`eee
`
`5
`
`
`
`co
`Heading JONG
`
`11
`Classmark Vem OC?
`|
`
`Book No. CORR!WOT |
`
`
`tf Hweee AM
`@
`
`Crefreen Library
`
`
`ce and Engineering
`
`
`
`
`
`
`
`6
`
`
`
`'I
`
`\h.\siS f"x~6'vt 'A·~-£-~
`~ a.e ct.OJ-c:t.t~ Clf".=cn f1~f:i "<- rA i~
`~ clOlA'lld ~ (WJ_ tkb ('2 tt\ t:::X? ~ ~
`~\' ~~ el C...vt r\"tZ. t:::>
`f5J!. , A rJ wt MM~
`
`I
`
`Richard Brian Hammond
`Notary Public
`England and Wales
`2 Kayes Walk
`Nottingham
`NG1 1PZ
`
`! I . I .
`I f
`I',' '
`
`'.
`.
`
`t
`i
`fl I),
`
`. l,:
`~ '
`
`7
`
`
`
`I
`
`I
`1
`1
`
`AUTOMATED ROUTE PLANNING
`
`A NETWORK-BASED ROUTE PLANNING SOLUTION FOR
`MARINE NAVIGATION
`
`Department of Nautical Sciences, Royal Netherlands Naval College
`
`Institute of Engineering Surveying & Space Geodesy, University of Nottingham
`
`Author:
`Wichert J. de Jong, LTZ3
`
`Supervisor Royal Netheriands Naval College:
`H. Sabelis, KTZ ir.
`Head of the department of Nautical Sciences .
`
`Supervisor University of Nottingham:
`N. Bonnor, Air Commodore
`
`UNl\IERSITY
`\_YB.RARY
`;.;: .::J\\GHAM
`
`Bergen, December 2001
`
`. ·.·I
`< .. ~~
`I
`
`This dissertation is submitted to the Royal Netherlands Naval College in partial fulfilment, of
`the scientific education for naval officers.
`
`This dissertation is submitted to the University of Nottingham in partial fulfilment for the
`degree of Master of Science (Navigation Technology).
`
`8
`
`
`
`I
`
`f
`
`Foreword.
`
`Foreword
`
`This thesis was written as conclusion of my studies at the Royal Netherlands Naval College.
`In addition, this dissertation was submitted to the University of Nottingham, in partial
`fulfilment for the degree of Master of Science in Navigation Technology.
`
`On the 14th of August 1996, I entered the Royal Dutch Navy, in order to fulfil my childhood
`dreams of sailing the seas. As my studies proceeded in the first three years of midshipman at
`the Royal Netherlands Naval College, my interest in especially navigation and its backgrounds
`grew. Therefore, I choose to attend the faculty of Nautical Sciences for the two years of
`specialisation. This choice also gave me the opporhinity of attending the postgraduate MSc(cid:173)
`course in Navigation Technology at the Institute of Engineering Surveying and Space
`Geodesy (IESSG) at the University of Nottingham.
`
`During the lectures at the Royal Netherlands Naval College and the University of
`Nottingham, my interest was aroused in the modernisation of navigation, especially for the
`development of the Electronic Chart Display and Information System (ECDIS). Some
`research at the faculty of nautical sciences focussed on the automation of voyage planning.
`However, this research did not yet result in actual principles and algorithms. Therefore, I
`chose the subject of automation of route planning as the subject for this final project.
`
`In addition to this thesis, Martijn van der Drift wrote his thesis on the same subject, but
`focussed on the exact form and the programming of the route planning algorithm. [Drift, 2001]
`
`Now that my thesis is fmished, I would like to thank a number of people. Iri the first place, I
`thank KTZ Ir. H. Sabelis, for the great enthusiasm he showed during his lectures and during
`the period of supervising my project. In the second place, I would like to thank Air
`Commodore Norman Bonnor for supervising my dissertation overseas. In the third place, I
`thank Martijn van der Drift for the close co-operation during the last months. I would like to
`thank Hanke for her great patience and unlimited support. Finally, I would like to thank my
`parents for their everlasting trust and support. Without all these people, I would never have
`come this far!
`
`Den Helder, September 2001,
`
`Wichert J. de Jong, LTZ3
`
`11
`
`9
`
`
`
`Abstract
`
`Abstract.
`
`In this thesis, a solution is presented for automating a part of the voyage planning process in
`marine navigation, namely route planning. Another, better term, for route planning is route
`selection, since route planning is about selecting an optimal route. The presented principle is a
`network-based route finding solution under multiple criteria.
`
`The voyage planning process is first analysed. A model presented by Sabelis [Sabelis, 1999(ii)],
`provides a good overview on the different phases of voyage planning. Also, it is made clear,
`that voyage planning is a time-consuming and laborious process. Automating the process can
`best be done by first automating the different phases. In that perspective, a principle is
`developed for automating the route planning phase.
`
`Existing routes at sea are historically formed by depth and land. contours, pos1t1ons of
`harbours and international and national regulations. When analysing these, it shows that a
`network is already formed by the existing routes.
`
`The components of the route-network and the structure of the network are meant to provide
`as many options as possible with appropriate coverage of the world. The route-network
`should be fitted into the ECDIS data structure, since ECDIS is the most suitable platform for
`the automation of route planning. Therefore, some recommendations are made to create new
`objects in S-57, the IHO transfer standard for digital hydrographic data. In order to test the
`principle, a chain-node data structure is used, mainly because of the simplicity of the
`structure.
`
`The information that is required during the route planning phase is divided into the sailing
`order and the route characteristics. The sailing order contains the ship's characteristics and
`the mission characteristics. The route characteristics can be divided into dimensions,
`regulations and restrictions, navigational aspects and remaining aspects. The information
`requirements heavily depend on the classification (ocean, coastal or confined) of a passage.
`There are different sources of information but in order to automate the voyage planning
`process, all information should be available in ECDIS via EN Cs or other data bases.
`
`The route characteristics influence the decision process in terms of denial and preference.
`The information that denies passage through a route-segment is implemented as filter criteria
`in the filter algorithm; the information that influences the phase in terms of preference is
`implemented as criteria of preference in the decision algorithm.
`
`The sequence of the presented algorithm is to firstly filter the unnavigable segments; then to
`calculate the shortest possible route; thirdly all possible routes within an interval are
`calculated, whereafter the route-alternatives. are compared by means of the criteria of
`preference.
`
`The presented principle seems to give the desired results, although more tests and new and
`reviewed criteria are required for optimisation of the algorithm. Also more research is needed
`in order to provide the perfect setting of weights.
`
`111
`
`10
`
`
`
`List of contents
`
`1·
`I
`
`I
`I I
`I
`
`List of contents.
`
`Foreword ......................................................................................................................... ii
`Abstract ................................................................................................................. : ........ iii
`List of contents ............................................................................................................... iv
`I
`Preface ...................................................................................................................... 1
`I.1 Setting the scene ............................................................... .-....................................................... 1
`I.2 The project ............................................. ····························.······························ ......................... 2
`I.3 The structure of this dissertation ........................................................................................... 4
`II Voyage planning ...................................................................................................... 6
`II.1 The need for voyage planning ................................................................................................ 6
`II.2 A model of the voyage planning-process ............................................................................. 7
`II.2.1
`International regulations on voyage planning ........................................................................... 7
`II.2.2 The voyage planning-process according to Sabelis .................................................................. 7
`II.2.3 Automating the voyage planning-process ................................................................................. 9
`II.3 Route planning ........................................................................................................................ 10
`II.3.1 The route planning-cycle ............................................................................................................ 10
`II.3.2 Automating the route planning-process .................................................................................. 11
`II.4 Equivalents in the navigation domains ............................................................................... 12
`II.5 Geographic Information Systems (GIS) and Electronic Chart Display and
`Information Systems (ECDIS) ...................................................................................................... 13
`II.5.1 Geographic Information Systems ............................................................................................. 13
`II.5.2 Electronic Chart Display and Information Systems (ECDIS) ............................................. 15
`III Route-network analysis ............................................................... ; ......................... 17
`III.1 Analysing the shipping routes at sea ............................................................................... 17
`III.2 Network and graphs .......................................................................................................... 20
`III.3 Route-network ................................................................................................................... 22
`III.3.1 Different components needed in the route-network. ........................................................... 22
`III.3.2 Positioning of the route-points and -segments ....................................................................... 26
`III.4 Designing the data structure ............................................................................................ 28
`III.4.1 Some basics on data formats ..................................................................................................... 28
`III.4.2 Commonly used data structures ................. .' .............................................................................. 30
`III.4.3 ECDIS: S-57 Transfer Standard for Digital Hydrographic Data [IHO, 1996] ................. 30
`III.4.4 The route-network in S-57 ..... " .................................................................................................. 34
`III.4.5 Chain-node structure .................................................................................................................. 35
`IV Route planning information requirements ............................................................ 38
`IV.1
`Sailing order ........................................................................................................................ 38
`IV.1.1 Mission characteristics needed for route selecting ................................................................. 38
`IV.1.2 Ship's characteristics needed for route selection .................................................................... 40
`Some considerations on the required information for route-planning ..................... .42
`IV.2
`IV.2.1 Sources & availability .................................................................................................................. 42
`IV.2.2 Ocean, coastal and confined passages .................................................................................... .43
`IV.3 Relevant passage information during the route-planning process ............................ .44
`IV.3.1 Dimension characteristics .......................................................................................................... 45
`IV.3.2 Navigational aspects ................................................................................................................... 46
`IV.3.3 Regulations and restrictions ....................................................................................................... 47
`IV.3.4 Remaining aspects ................................................................................... · .................................... 49
`IV.4 Relations between and influence of different kinds of information in the route-
`selection process .............................................................................................................................. 50
`IV.4.1 Testing the passages in terms of suitability and feasibility .................................................... 51
`IV.4.2 Analysing the passages in terms of preferability of characteristics ..................................... 52
`Implementation in the test-environment. ...................................................................... 53
`IV.5
`IV.5.1
`Implementation of Sailing Order characteristics in the test-environment. ........................ 53
`IV.5.2
`Implementation of passage characteristics in the test-environment. .................................. 54
`
`lV
`
`11
`
`
`
`List of contents
`
`V Route planning algorithm . .................................................................................... 56
`V.1 Important considerations when automating route planning ........................................... 56
`V.1.1 What is the optirrial route? ......................................................................................................... 56
`V.1.2 The tirrie-distance problem ........................................................................................................ 57
`V.2 Structure of the route planning algorithm .......................................................................... 58
`· V.3 Preparing the data set for the algorithm ............................................................................. 61
`V.3.1 Collecting the information ......................................................................................................... 61
`V.3.2
`Filtering ......................................................................................................................................... 61
`V.3.3 Calculations .................................................................................................................................. 63
`V.4 Optimal route finding algorithm .......................................................................................... 64
`V.4.1 Dijkstra's algorithm for the shortest path .................................. ~ ............................................ 64
`V.4.2 Generating the K- shortest paths ............................................................................................ 66
`V.4.3 Criteria of preference .................................................................................................................. 66
`V.4.4 Group decision making under multiple criteria for selection of alternatives .................... 70
`VI Testing the route planning algorithm ................................................................... 75
`VI.1 Developing the test environment. ................................................................................... 7 5
`VI.1.1 The goal of testing the algorithm. ............................................................................................. 75
`VI.1.2 Choice for a synthetic test environment... ............................................................................... 75
`VI.1.3 Often occurring situations ......................................................................................................... 76
`VI.1.4 The final area ................................................................................................... : ............................ 77
`VI.2 Test scenarios ..................................................................................................................... 77
`VI.2.1 The test ship ................................................................................................................................. 77
`VI.2.2 Scenario 1: Testing the filter algorithm and Dijkstra's algorithm ........................................ 78
`VI.2.3 Scenario 2: Testing the decision algorithm in limited test areas .......................................... 79
`VI.2.4 Scenario 3: Testing the whole algorithm in larger test areas ................................................ 81
`VII Conclusions and recommendations . ..................................................................... 84
`VII.1 Conclusions ........................................................................................................................ 84
`VII.1.1 The first question: the route-network. ..................................................................................... 84
`VII.1.2 The second question: information requirements ................................................................... 86
`VII.1.3 The third question: the algorithm ............................................................................................. 88
`VII.2 Recommendations ............................................................................................................. 90
`Glossary ......................................................................................................................... 92
`References ..................................................................................................................... 97
`List of figures ............................................................................................................... 103
`Appendices .................................................................................................................. 104
`Appendix A: Traffic density chart: route bound traffic on the North Sea. [Traffic, 2000] 104
`Appendix B: Example of the positioning of route-segments ................................................. 105
`Appendix C: Cargo classification and ice classification ........................................................... 106
`·Appendix D: Attributes and attribute values as used in the test-environment .................... 108
`Appendix E: Final chain-node structure as used in the test-environment ........................... 112
`Appendix F: The synthetic test environment ........................................................................... 115
`Appendix G: Test results of scenario 1 ...................................................................................... 116
`Appendix H: Test results of scenario 2 ...................................................................................... 120
`Appendix I: Test results of scenario 3 ........................................................................................ 127
`
`I I
`f l
`
`v
`
`12
`
`
`
`Chapter I
`
`I
`
`Preface
`
`1.1
`
`Setting the scene.
`
`Preface
`
`The present developments in navigation are especially dealing with automation. Even the
`
`conservative world of marine navigation is at the threshold of the computerised environment.
`
`A great deal of effort is being put into integrating navigation systems, developing the one(cid:173)
`
`man-bridge and using computers as the new medium for publications. A large share of this
`
`effort is ascribed to the Electronic Chart Display and Information System (ECDIS), since the
`
`possibilities for development of this system are endless. In addition to the electronically
`
`displayed nautical chart, with the real-time presentation of the own ship's position and the
`
`projection of radar and ARP A (Automatic Radar Plotting Aid) information on top of the
`
`chart, having other kinds of information, such as sailing directions and lists of lights, at the
`
`users' disposal interactively should be possible in the future. The role of ECDIS should
`
`therefore be supportive in more disciplines than it is now.
`
`A process, which is not always completed with the same accurary and precision as appropriate
`
`as general navigation is the voyage planning-process. The planning of a voyage is rightly
`
`contemplated as a time-consuming and laborious activity. The great diversity of sources of
`
`information that have to be consulted during the planning-process makes the process
`
`cluttered and difficult. Among other possibilities that ECDIS offers, it should be able to
`
`support voyage planning. Research has been undertaken on the various digital storage
`
`methods and the presentation of all the required information, that is not displayed on the
`
`nautical chart [Carol, 1996]. However, the planning of a voyage in ECDIS is still only possible
`
`by clicking and dragging way-points with a mouse or track-ball; it is just a drawing tool. The
`
`only automated function with respect to route planning is checking the drawn track against a
`
`few features within a certain safety-zone around the track. No warning is giving on following
`
`the wrong ti:affic lane, for example. Neither can the optimal route be calculated.
`
`This is remarkable, because in the other two navigation domains, land navigati~n and air
`
`navigation, these processes have been automated already. Widely available (e.g. on internet)
`
`are route planners for car navigation. By giving the start and end position (cities, streets or
`
`postal codes), the software is able to calculate the shortest route, either in length or in
`
`travelling time, using a real road network. It then presents the route on a digital map together
`
`with an information sheet. The same types of systems exist in air navigation, since aircraft use
`
`a network of airways and preferred routes. Spatial analyses are possible too (where is the
`
`1
`
`13
`
`
`
`Chapter I
`
`Preface
`
`nearest gas station?), because these route planners are applications of dedicated Geographical
`
`Information Systems. Is an ECDIS not a special form of GIS? Hence, particularly an ECDIS
`
`forms an ideal environment for automated voyage planning. [Sabelis, 1999(ii)]
`
`The voyage planning-process can be dissected into route planning, navigation planning and
`
`watch preparation. [Sabelis, 1999(ii)] Route planning deals with the selection of the route,
`
`navigation planning deals with the more detailed planning of the track and watch preparation
`
`should provide the officer of the watch with all information needed during his particular
`
`watch. All these steps are feasible for automation in one way or another. An automated tool
`
`for voyage planning should always be supportive, because safety of life and environment is
`
`involved. Decisions should thus always be the navigator's. During the preparation and
`
`execution of the watch, ECDIS should present relevant information dealing with the area the
`
`ship is, and will be, sailing. During the first two sub-processes, the software can generate
`
`route and track options without the active participation of the navigator. Given the fact that
`
`these stages of the voyage planning-process are the most laborious, route planning and
`
`navigation planning are ideal for automation.
`
`This thesis will focus on the first process of voyage planning, route planning or route
`
`selection. Sabelis sketched the functionality of voyage planning software. [Sabelis, 1999(ii)] He
`
`supposed that a route-network should be a robust basis for route planning-algorithms. The
`
`use of such a network enables the developer of these algorithms to use the methods and
`
`knowledge on route planners from the other navigation domains. My thesis is based on the
`
`assumption that using a route-network as a basis for the selection of a route would offer a
`
`reasonable solution for the route planning-problem in marine navigation. I will not discuss
`
`what should be the best solution.
`
`I.2 The project.
`
`The subject of this dissertation is automating the route planning-process. The main goal of
`
`my project is the development of a route planning-tool, which, based on a route-network,
`
`calculates an optimal route from the point of departure to the point of arrival. Within the
`
`route, the navigator can determine his track. In order to develop a route planning-tool as
`
`described above, an inventory of the features of such a tool is required. First, there has to be
`
`some kind of data storage and structure, which is geographically referenced and easy to
`
`access, to allow the system to analyse the information quickly and correctly. The route(cid:173)
`
`network will form the basis for the data structure and information storage. Secondly, an
`
`2
`
`f f· l
`i
`
`14
`
`
`
`Chapter I
`
`Preface
`
`algorithm is needed, which both analyses and combines all information, and which calculates
`
`and optimises route-alternatives. In the third place, a presentation method is required. The
`
`method of presentation will not be an issue in this dissertation. The following two objectives
`
`are defined:
`
`1.
`
`The development of a route-network at sea, which 1s suitable as basis for route
`
`planning-calculations.
`
`2.
`
`The search for a simple shortest path algorithm, with which the route planning(cid:173)
`
`problem can be solved, considering all the relevant information and in such way that
`
`the different options are feasible and navigable.
`
`From these objectives, the following questions and sub-questions are formed and will be
`
`answered in this thesis:
`
`A.
`
`What should be the structure of a route-network, to provide a robust basis for a
`
`shortest route algorithm?
`
`1.
`
`What data structure should be used for such a route-network, in order to
`
`provide
`
`the algorithm with
`
`the relevant information, and to provide
`
`compatibility with the Electronic Chart Display and Information System?
`
`11.
`
`What kinds of real routes can be distinguished at sea and with what kind of
`
`features can they be described adequately?
`
`iii.
`
`How can such a network cover as many parts of the world as possible,
`
`without diminishing the calculation speed and extending disk storage?
`
`B.
`
`Which information is essential when selecting a route and should therefore be
`
`available to the shortest path algorithm?
`
`i.
`
`11.
`
`What are the relevant characteristics of a passage that are essential for the
`
`selection of a route?
`
`How should the characteristics of a route-segment be implemented in the
`
`route-network?
`
`iii.
`
`How should the influence of particular route characteristics be expressed in
`
`terms of preference?
`
`1v.
`
`What are the ship's characteristics that are essential when selecting a route?
`
`c.
`
`How can the optimal route be calculated on the basis of a route-network?
`
`1.
`
`11.
`
`What is the optimal route?
`
`How should the ship's characteristics 'delete' route-segments that can or may
`
`not be used?
`
`3
`
`15
`
`
`
`1 ' I
`
`i l
`
`Chapter I
`
`Preface
`
`111.
`
`How is an 'optimal' route (and alternatives) calculated?
`
`This project is ca