在日常生活中，我們經常會接觸到資料序列。例如機器所作出的每一個動作、模擬下的每一個狀態或是琴譜上的每一個音符，都是各種資料序列。當事情隨時間而不斷產生變化時，這些資料序列中便會有無限多個的資料。一般而言，許多問題都可建模為有限定義域的約束滿足問題。可是對於一些問題中有隨時間而產生變化的量值，在建模時便會面對很多困難。當這些問題被建模為約束滿足問題時，為了配合有限的定義域，我們通常只能把問題限制於一段固定的時間間隔中。然而，在許多情況下，很多有用的資訊會因我們的限制而流失。隨時間而變化的數值猶如一串無窮無盡的資料流。我們為此提出對無限資料串流作約束編程。無限長的資料串流使得在表示、處理和推理時，都產生一定的難度。我們設計了一套建模語育，當中包括用於資料串流的運算子。我們針對兩類資料串流集合:一些具有最終重覆樣式的串流干日一些可構成ω-正規語育的串流。根據這兩類資料串流集合的特性，我們提出兩種求解方法。當問題涉及具有最終重覆樣式的串流時，我們會把問題分割成一系列無限個有限定義域的子問題，並把子問題逐一求解出來。而當問題的所有解可構成ω-正規語言時，我們會以搜尋樹來求解，並在過程中規避一些相等於己搜尋的空間。以這方法得出的搜尋圖，其形狀同構於用以表達所有解的自動機。同時，我們亦透過定義從最終重覆樣式的串流中得出偏好值的函數，以便對無限資料串流作約束優化。在求解中藉由執行一致性概念，我們可以減少搜尋空間。我們實作了一個求解程式，用以把問題從建模語言中建立模形，並且求得解答。從一些以模擬問題及生產音樂的實驗可以印證，我們所提出對無限資料串流作約束編程的建模及解決方法的可行性。 / Sequences of data items can be found in many daily life problems. Examples are the actions of a controller in each step, states of a simulation, and notes in a piece of music. When the problems go on forever, the sequences become infinite. While many problems can be modeled as finite domain constraint satisfaction problems (CSPs), it is difficult to model problems which contain timevarying quantities over discrete time points. The constrained variables thus usually represent only a limited scope of the quantities in a finite time interval. As a result, some useful information may be lost. Time varying-quantities in the problems resemble streams of data over discrete time points. We propose constraint programming on infinite data streams. The infinite nature of streams raises difficulties in representation, manipulation, and reasoning. We design a modeling language to specify the problems. Operators are adopted to manipulate the stream values. We identify two classes of stream sets: streams with ultimately periodic patterns and streams that form an ω-regular language. According to the structure of stream sets, we propose different solution techniques to solve the CSPs. A problem involving ultimately periodic streams is divided into an infinite sequence of finite domain sub-problems. We solve the sub-problems in the sequence iteratively. A problem with solution set forming an ω-regular language is solved by tree search which avoids searching indefinitely in an infinite domain by detecting equivalent visited search space. The resultant search graph is isomorphic to an automaton representing the solution set. Optimization on the problems is made possible with a measurement of preferences on ultimately periodic streams. Consistency notions are enforced during search to reduce search space. We implement a solver to interpret and solve the problems with stream variables. Experiments on problems in some simulations and music generation are conducted to show the feasibility of modeling and solving the stream CSPs. / Detailed summary in vernacular field only. / Siu, Fai Keung. / "October 2012." / Thesis (Ph.D.)--Chinese University of Hong Kong, 2013. / Includes bibliographical references (leaves 115-119). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstract also in Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Constraint Satisfaction and Constraint Optimization --- p.1 / Chapter 1.2 --- Infinite Data Streams --- p.2 / Chapter 1.3 --- Motivations and Goals --- p.3 / Chapter 1.4 --- Overview of the Thesis --- p.4 / Chapter 2 --- Background --- p.6 / Chapter 2.1 --- Constraint Satisfaction Problems --- p.6 / Chapter 2.1.1 --- Backtracking Tree Search --- p.8 / Chapter 2.1.2 --- Consistency Notions --- p.12 / Chapter 2.2 --- Constraint Optimization Problems --- p.15 / Chapter 2.3 --- Regular Languages and Finite State Automata --- p.20 / Chapter 2.4 --- Infinite Data Streams --- p.22 / Chapter 2.4.1 --- Pointwise Operators --- p.23 / Chapter 2.4.2 --- Temporal Operators --- p.24 / Chapter 3 --- Constraint Satisfaction on Ultimately Periodic Streams --- p.26 / Chapter 3.1 --- Stream Constraint Satisfaction Problem --- p.26 / Chapter 3.1.1 --- Stream Variables and Stream Variable Domains --- p.26 / Chapter 3.1.2 --- Stream Constraints --- p.27 / Chapter 3.1.3 --- Stream CSP --- p.28 / Chapter 3.2 --- Ultimately Periodic Streams --- p.31 / Chapter 3.3 --- Solving St-CSPs for UP Solutions --- p.35 / Chapter 3.3.1 --- Translation Scheme --- p.38 / Chapter 3.3.2 --- Excluding Solutions in Non-canonical Form --- p.42 / Chapter 3.4 --- Modeling Examples and Experiments --- p.44 / Chapter 3.4.1 --- The Game of Life --- p.46 / Chapter 3.4.2 --- The n-Puzzle Problem --- p.50 / Chapter 3.4.3 --- The Traffic Light Problem --- p.55 / Chapter 4 --- Stream Constraint Satisfaction for Omega-Regular Solution Sets --- p.60 / Chapter 4.1 --- Stream Constraint Satisfaction Problem --- p.60 / Chapter 4.2 --- Solving St-CSPs for Omega-Regular Solution Sets --- p.63 / Chapter 4.2.1 --- Search Tree --- p.63 / Chapter 4.2.2 --- Instantaneous CSP --- p.64 / Chapter 4.2.3 --- Search Algorithm --- p.65 / Chapter 4.2.4 --- Solution Sets of St-CSPs --- p.66 / Chapter 4.2.5 --- Primitive Stream Constraints --- p.69 / Chapter 4.3 --- Consistency Algorithm --- p.76 / Chapter 4.4 --- Modeling Examples and Experiments --- p.79 / Chapter 4.4.1 --- Simulation of Juggling --- p.79 / Chapter 4.4.2 --- Digit Invader Game --- p.82 / Chapter 4.4.3 --- Towards Generating Jazzy Harmonization --- p.83 / Chapter 5 --- Stream Constraint Optimization --- p.86 / Chapter 5.1 --- Infinite Streams as Domain of Objective Function --- p.86 / Chapter 5.1.1 --- Straight Line Representation of Cumulative Sum of Datons --- p.87 / Chapter 5.1.2 --- Trend Comparison --- p.94 / Chapter 5.2 --- Constraint Optimization on Ultimately Periodic Streams --- p.96 / Chapter 5.3 --- Modeling Examples and Experiments --- p.98 / Chapter 5.3.1 --- The Game of Life --- p.101 / Chapter 5.3.2 --- The n-Puzzle Problem --- p.101 / Chapter 5.3.3 --- The Traffic Light Problem --- p.103 / Chapter 5.4 --- Alternative Objective Functions --- p.105 / Chapter 6 --- Related Work --- p.108 / Chapter 6.1 --- Model Checking --- p.108 / Chapter 6.2 --- Dynamic Constraint Satisfaction Problems --- p.109 / Chapter 6.3 --- Cyclic Scheduling --- p.109 / Chapter 6.4 --- Dataflow Programming Language --- p.110 / Chapter 7 --- Concluding Remarks --- p.112 / Chapter 7.1 --- Contributions --- p.112 / Chapter 7.2 --- Future Work --- p.114 / Bibliography --- p.115
| Identifer | oai:union.ndltd.org:cuhk.edu.hk/oai:cuhk-dr:cuhk_327989 |
| Date | January 2013 |
| Contributors | Siu, Fai Keung., Chinese University of Hong Kong Graduate School. Division of Computer Science and Engineering. |
| Source Sets | The Chinese University of Hong Kong |
| Language | English, Chinese |
| Detected Language | English |
| Type | Text, bibliography |
| Format | electronic resource, electronic resource, remote, 1 online resource (xi, 119 leaves) : ill. (some col.) |
| Rights | Use of this resource is governed by the terms and conditions of the Creative Commons “Attribution-NonCommercial-NoDerivatives 4.0 International” License (http://creativecommons.org/licenses/by-nc-nd/4.0/) |
Page generated in 0.0027 seconds