Enhancing code clone detection using control flow graphs

Received Mar 6, 2019 Revised Apr 7, 2019 Accepted Apr 19, 2019 Code clones are syntactically or semantically equivalent code fragments of source code. Copy-and-paste programming allows software developers to improve development productivity, but it could produce code clones that can introduce non-trivial difficulties in software maintenance. In this paper, a code clone detection framework is presented with a feature extractor and a clone classifier using deep learning. The clone classifier is trained with true and false clones and then is tested with a test dataset to evaluate the performance of the proposed approach to clone detection. In particular, the proposed approach to clone detection uses Control Flow Graphs (CFGs) to extract features of a given code snippet. The selected features are used to compute similarity scores for comparing two code fragments. The clone classifier is trained and tested with similarity scores that quantify the degree of how similar two code fragments are. The experimental results demonstrate that using CFG features is a viable methodology in terms of the effectiveness of clone detection for both syntactic and semantic clones.

INTRODUCTION
Software reuse refers to a series of activities of using existing code for developing new software products. Software reuse has positive aspects of improving development productivity and quality, but simple copy-and-paste reuse can produce redundant and duplicate code (also known as code clones) across a program. Code clones can be defined as syntactically or semantically equivalent code fragments of source code. The presence of the code clone can hinder the consistency of an application in software maintenance such as bug fixes, security updates, and code refactoring. Such code changes can be involved in undesirable consequences due to the code clone. If only part of the code clone is modified without covering the whole of the code clone, potential problems can be introduced during the lifecycle of a software system. Therefore, for better software maintenance, locating and keeping track of code clones are a crucial part when modifying code of an existing program. In this paper, a novel approach to clone detection is presented with a feature extractor and a clone classifier using deep learning. The feature extractor constructs feature vectors to characterize a give code fragment for clone detection. The clone classifier is based on supervised learning which produces a deep learning model through training data consisting of input vectors and desired output values. Therefore, the clone classifier is trained with known true clones and false clones in a training phase. In a testing phase, the clone classifier predicts whether or not two method pairs have a clone relationship. The proposed approach to clone detection extracts input features from the CFGs of a code fragment. The input features are used to compute similarity scores for comparing two code fragments. The clone classifier is trained and tested with the similarity scores that quantify the degree of how similar two code fragments are. The proposed clone detection framework represents a code fragment as control flow graphs to catch semantically similar clones. A control flow graph is a directed graph that represents the control flow of a code fragment (e.g., functions and methods). The CFG consists of a set of nodes (also known as vertices) and edges. A node represents the basic statement of the code fragment such as expressions, if-statements, and forstatements. An edge of the CFG connects one node with another and means a program control flow from between the two nodes. The node could be connected to multiple nodes if it is involved in controlling more than one program control. The CFG has a single entry node where a control flow starts and a single exit node where a control flow ends. There can be multiple control flows between the entry node and the exit node. A path in a CFG is a sequence of directed edges in which all nodes are distinct. For example, 3_Path in this paper means any three distinct nodes are connected in a CFG-based representation. The path represents structural features in code fragments and its length is various in a CFG-based representation. The code fragments are characterized by the length and the occurrence counts of the CFG path.
The first step of clone detection is to determine the scope of a code fragment which is a continuous segment of source code. Some clone detection tools take a function or a method as the code fragment. In some cases, a portion of the function can be considered as the code fragment. The code fragment is identified with three elements such as a source file, a starting line number, and an ending line number. If a whole method is considered as the code fragment, the starting line number and the ending line number of the code fragment will be the same as those of the method. The proposed clone detection approach takes each method in Java source files as the code fragment. Code clones are a pair of code fragments of source code that are syntactically or semantically equivalent. There are four types of code clones: Type-1 (T1), Type-2 (T2), Type-3 (T3), and Type-4 (T4). Type-1 clones are syntactically identical code fragments, except for differences in white space, layout and comments [1]. Type-2 clones are syntactically identical code fragments, except for differences in identifier names, literal values, white space, layout and comments [1]. Type-3 clones are syntactically similar code fragments that differ at the statement level. Fragments have statements added, modified and/or removed with respect to each other [1]. Finally, Type-4 clones are syntactically dissimilar code fragments that implement the same functionality [2]. The proposed approach to clone detection uses BigCloneBench [3] which is one of the popular benchmarks of code clones. The BigCloneBench data are categorized by separating Type-3 and Type4 clone pairs into four categories based on their syntactical similarity: Very-Strongly Type-3 (VST3) clones with a similarity in range 90% (inclusive) to 100%, Strongly Type-3 (ST3): 70-90%, Moderately Type-3 (MT3): 50-70%, and Weakly Type-3 or Type-4 (WT3/4): 0-50% [4]. Deep learning is a specific kind of machine learning and allows computational models that are composed of multiple processing layers to learn representations of data with multiple levels of abstraction [5]. Deep learning algorithms have been applied to solve problems of artificial intelligence fields and have produced promising results for some specific tasks such as natural language processing, computer vision, and image processing [6]. These advanced learning algorithms can also contribute to solving software engineering problems that are the analogous ones in artificial intelligence. Figure 1 shows the deep neural network architecture that consists of three layers-input layer, hidden layer, and output layer. The input features (e.g., similarity scores) are given to input nodes in the input layer. The nodes in the different layers are connected with connection weights and biases. The deep learning network model can possess multiple hidden layers so to improve the performance of the code clone classifier. In the clone classifier model, the Rectified Linear Unit (ReLU) is an activation function for the hidden layers and the softmax function is used as activation function for the output layer. As two nodes reside in the output layer, the prediction result of the clone classifier is either "Clone" or "Non-Clone" on the given method pairs. The rest of this paper is organized as follows. Section 2 overall describes the proposed approach to detect code clones using control flow graphs. Section 3 presents experimental results to demonstrate the effectiveness of the CFG-based clone detection. Section 4 summarizes related studies and Section 5 finally remarks conclusions and future research directions. Figure 2 illustrates the overall workflow of the proposed code clone detection framework. The clone detection system has the training and testing phase. The solid arrows show the flow of the training phase which produces a trained clone classifier from a list of features. The clone classifier determines if pairwise methods are clones to each other in the testing phase which is shown the dashed arrows in Figure 2. The clone detection system used BigCloneBench which is one of the popular benchmarks of code clones and has been used for clone-related studies. The BigCloneBench data are separated into the training and test datasets. The clone classifier model in the detection system is trained and optimized by the training dataset and then is evaluated by the test dataset. The first step of the training phase is to identify method modules from the given Java source files through lexical analysis and syntactic analysis. Pairwise method modules are constructed from the separate methods. The pairwise methods are used to train or test the deep learning model. The proposed clone detection system extracts syntactic and semantic features of code fragments from CFGs of the identified methods. A CFG is generated for each method. CFG features are generated from the CFG. The CFG feature sets are represented by feature vectors that could be computed effectively in the deep learning model. Similarity scores are used to quantify the degree of how similar two methods are. The similarity score of the pairwise method is calculated and is given to the input layer of the clone classifier. The range of similarity score is [0, 1] through the normalization step. The trained clone classifier can be produced after the training phase. In the testing phase, the similarity scores of the pairwise methods are created from the test dataset. The steps for generating the similarity score are the same as those of the training phase. The clone classifier can tell whether the given method pairs are clones or not using the similarity scores.

APPROACH
The proposed clone detection framework is based on a deep learning network model which is a clone classifier and determines the semantic similarity of the method using its corresponding control flow graph. A CFG is a directed graph and represents all possible execution paths of a method. It also encodes the behavior of the method at a higher level of abstraction. A set of features are extracted from the control flow graphs. Such a feature set includes node information and path information of the control flow graph. For the comparison of two methods, the pairwise feature sets are used to compute the similarity score. Figure 3 shows an example of Java source code and its corresponding control flow graph. In this example, the class Sample has only one method main and the control flow graph of the main method is presented on the right side of Figure 3. The node of the CFG is known as a basic block and represents expressions, if-statements, for-statements, etc. The edge of the CFG represents a possible control flow from the end of one block to the beginning of the other. As seen in Figure 3, CFGs also have a single entry and a single exit point.  Figure 3. Example of control flow graph A path in a CFG is a sequence of directed edges which connect a sequence of distinct nodes. For example, 2_Path means any two distinct nodes are connected in the control flow graph. The proposed clone detection framework considers 1_Path, 2_Path, 3_Path, and 4_Path to compare pairwise methods. Table 1 lists the feature paths which are extracted from the control flow graph shown in Figure 3. The first column shows the type of paths and the second column is the total frequency of each path type in the control flow graph. The last column shows the distinct instances of each path type and their frequency. The summation of the frequency of each path instance should be equal to the total number in the second column.

EVALUATION
A set of features can impact seriously the performance of the clone classifier. Therefore, extracting the meaningful features of a dataset is one of the key steps to develop an acceptable deep learning model. Figure 4 shows the CFG feature extraction algorithm to identify a set of CFG features from a given method. Such CFG features of each method will be used to compute the similarity score for the method comparison. Given a target method in a program, the proposed clone detection system extracts a set of CFG features from the corresponding control flow graph of the method. After creating the corresponding CFG of the input method, the detection system finds all paths on the control flow graph. The next step is to count the frequency of the CFG features. If the label of a CFG node on a CFG path is found in the feature set, the frequency of the CFG feature node increases by one. If the CFG node is found newly, it is added to the feature set. The frequency of the newly added feature node is one. The counting of the frequency of the CFG feature nodes is performed until all CFG paths are considered. Finally, through the feature extraction algorithm, the CFG feature set is produced that holds a pair of the feature node type and its frequency.
Input: Let MED be a target method in a program. Output: Let FeatureSet be a set of CFG features. FeatureSet = {(f 1 , feq 1 ), · · ·, (f n , feq n )} 1: aCFG  generateCFG(MED) //Creating CFGs by calling CFG generator on MED 2: allPaths  findAllPaths(aCFG) //Finding all paths on the control flow graph 3: foreach path i from allPaths do 4: foreach node j from path i do 5: if node j  FeatureSet then //Getting the frequency to which node j is mapped in FeatureSet 6: feq j  getFequency(FeatureSet, node j ) 7: feq j  feq j + 1 // Increase the frequency by one 8: else //Adding node j to FeatureSet if node j is new 9: FeatureSet = FeatureSet  {(node j , 1) } //Assigning one to frequency of node j 10:  The proposed clone detection system needs to train a binary-class classifier for code clone detection which uses training and test dataset for both true clone pairs and false clone pairs. For the training of the classifier, the similarity scores of each feature vector and its label are provided from the training dataset. The true clones are labelled to '1' while the false clones are labelled to '0'. Keras [7]-an open source machine learning library for deep learning-is used to train a clone classifier. Four input nodes and two output nodes are configured for the input layer and the output layer respectively. Since the proposed clone detection approach considers four features of the control flow graph, the input layer holds four nodes which independently take in four feature values. The output layer contains two nodes because the clone detection problem is the binary classification task to check whether two methods are clones or not. The proposed clone detection system configures the deep learning model to include eight hidden layers and to run 200 iterations for training. Table 2 lists the node types of the control flow graph that should be considered to detect code clones. The node type is the construct of Java programs such as expressions, control constructs, conditional constructs, and exception handling constructs. The Java syntax of the node type is represented in the last column and follows BNF-style conventions: [expr] means zero or one occurrences of expr, {expr} means zero or more occurrences of expr, and (x | y) denotes one of either x or y. The proposed clone detection system will extract node types from methods and then generate edges and paths which are made up of the nodes. Table 3 shows the datasets of training and testing for the clone classifier. Folder #4 in BigCloneBench is used as the training dataset since it has the largest number of true and false clone pairs. The true clone pairs in the training dataset include T1, T2, VST3, and ST3 clones and the total number of true clones is 13,399 which is equal to the total number of false clones. MT3 and WT3/4 clones are intentionally excluded from the training dataset because they could contain noisy data which may produce false alarms on detecting code clones.
For the testing of the clone classifier, the test dataset is made from Java source files in the four folders of BigCloneBench such as #2, #3, #7, and #10. The source files in the folder #4 are excluded because they are used as the training dataset. Unlike the training dataset, the test dataset contains only true clone pairs without false clone pairs. The similarity scores on the pairwise methods are computed through the same procedures as the training phase. These procedures include the CFG construction, the CFG path generation, the CFG feature extraction, and the similarity score computation.   Figure 5 shows the experimental result on the test dataset. The proposed clone classifier has been evaluated with different similarity thresholds in order to check how the similarity threshold affects the performance of the clone detection. The classifier finds clones when the likelihood value is greater than or equal to the similarity threshold. In these experiments, the clone classifier is configured with 8 hidden layers and 200 epochs. The proposed detection system effectively identified T1, T2, and VST3 clones-the recall results are close to 100% (except the folder #2 dataset) with the different similarity thresholds: 0.95, 0.96, 0.97, and 0.98. The proposed classifier also detects effectively ST3 clones on the datasets #2 and #10-the recall values are greater than 90%. With the datasets #3 and #7, the performance of the clone detection goes down a little bit as the detection thresholds become larger. The detection system did not show desirable detection performance on the MT3 and WT3/4 clones. It is still challenging to detect semantic clone types even though the proposed approach is based on control flow graphs which may represent more abstract perspectives of semantically similar code blocks than token-based approaches.
Deep neural network models may be affected by hyperparameters such as hidden layer and epoch. Tables 4 and 5 Table 5 shows the number of epochs impacts on the performance of the clone detection. The proposed clone classifier works best when the number of epochs is 200.

RELATED WORK
Many studies have been conducted to overcome research challenges in detecting code clones across source code. Most of existing clone detection methodologies can be categorized into five types: text-based [8], token-based [9], tree-based [10], graph-based [11], and metrics-based [12] approaches. One of the emerging research trends is to leverage deep learning algorithms to enhance the performance of the existing clone detection strategies. The promising outcomes of deep learning affect many other fields beyond artificial intelligence communities. Software engineers have been involved in actively applying deep learning to solve typical problems in software engineering such as clone detection, bug prediction, and security prediction.
Sheneamer and Kalita's clone detection approach [13] uses typical machine learning algorithms so to detect semantic code clones. They use a supervised learning approach where semantic features are extracted from ASTs and PDGs and training data are labelled with clones or non-clones. Their approach is based on machine learning algorithms, not deep learning algorithms. White et al. [14]  approach to detect code clones by combining recurrent neural network with recursive neural network at method and file levels. The experimental results show their methodology is feasible in some cases, but they still need to conduct more case studies on popular clone benchmarks. Li et al. [15] provide a token-based clone detection approach using deep learning-based clone classifier. They extract feature vectors by tokenizing method pairs and then compute similarity scores of the feature vectors. The clone classifier is trained with eight similarity scores of known true clones and false cones. In the testing phase, the trained clone classifier predicts code clones in a codebase of unknown clones. This approach still has room for improvement on finding semantic clones like Type-3 and Type-4 clones. Saini et al. [16] propose a clone detection approach to focus on harder-to-detect semantic clones. Their approach is based on a deep neural network with Siamese architecture where information retrieval and metric-based methods are combined.
To detect semantic clones, their approach excludes semantically dissimilar clones using a semantic filter instead of using semantic features. Phan et al.'s work [17] show CFG-based deep learning can be used for software defect prediction as well as clone detection. They apply convolutional neural networks for predicting software defect using control flow graphs. Control flow graphs are built from assembly files and then are represented as vectors which are given to convolutional neural networks. The convolutional neural network explores the behavior of target code using vector representations and reports software defects in unseen datasets after being trained with training datasets.

CONCLUSIONS AND FUTURE WORK
This paper presents a code clone detection framework to find effectively clone types with a deep learning-based clone classifier. The proposed approach to clone detection is based on the extraction of features from CFGs of given code fragments. The CFG features are represented as feature vectors so that they can be compared to determine whether code fragments are similar or dissimilar. The clone detection classifier is trained and tested with similarity scores that are computed from the feature vectors. The proposed detection framework effectively found syntactic clone types such as T1, T2, and VST3 clones. It also identified ST3 clones with the acceptable but not excellent recall results. In the case of sematic clone types such as MT3 and WT3/4 clones, the detection performance still needs to be improved. Although the proposed approach to clone detection needs to be improved further, the promising experimental results suggest that deep learning-based clone detection classifiers can be effective in finding code clones. In the future, more code clones will be explored to enhance functions of the proposed clone detection on semantic clone types. Furthermore, unsupervised deep learning algorithms can be considered to improve the weakness of the clone classifier using supervised learning. The clone detection framework will be applied for other programming languages to extend the generality of the proposed clone detection methods.


Live Reconstruction of Large-Scale Dynamic Outdoor Worlds

Standard 3D reconstruction pipelines assume stationary world, therefore suffer from ``ghost artifacts'' whenever dynamic objects are present in the scene. Recent approaches has started tackling this issue, however, they typically either only discard dynamic information, represent it using bounding boxes or per-frame depth or rely on approaches that are inherently slow and not suitable to online settings. We propose an end-to-end system for live reconstruction of large-scale outdoor dynamic environments. We leverage recent advances in computationally efficient data-driven approaches for 6 DoF object pose estimation to segment the scene into objects and stationary ``background''. This allows us to represent the scene using a time-dependent (dynamic) map, in which each object is explicitly represented as a separate instance and reconstructed in its own volume. For each time step, our dynamic map maintains a relative pose of each volume with respect to the stationary background. Our system operates in incremental manner which is essential for on-line reconstruction, handles large-scale environments with objects at large distances and runs in (near) real-time. We demonstrate the efficacy of our approach on the KITTI dataset, and provide qualitative and quantitative results showing high-quality dense 3D reconstructions of a number of dynamic scenes.

Introduction
The world around us represents an inherently dynamic 3D environment. Hence all robots operating in this complex environment need not just to recognise the stationary parts of it, but also continuously perceive and reason about all other dynamically moving agents or objects. For instance, autonomous cars need to understand geometric and spatial extent of all other moving cars, pedestrians or bicyclists, and reason about their actions and interactions in order to move safely around them. At the core of this understanding lies accurate 3D reconstruction of each object (and stationary background) -a fundamental computer vision problem called "multi-body dynamic scene reconstruction". * Equal contribution. Figure 1. Static 3D reconstruction suffers from "ghost artifacts" caused by dynamic objects (top). Our system (middle) explicitly models each object instance as a separate volume (bottom). Live output of our system, as seen from a moving platform on-the-fly.
Most early approaches to (dense) Structure-from-Motion (SfM) or Visual SLAM focused on 3D reconstruction of static parts of the scene [2,28]. In other words, the dynamic component of the scene was considered to be noise which had to be (explicitly) suppressed to prevent the wellknown ghost artifact that generally appears whenever dynamic content is fused into the stationary volume [5,36]. This approach is useful for reconstruction of (largely) stationary worlds such as museums or galleries [38,41] where the goal is to produce a dense static 3D model which is not corrupted by moving objects. However, discarding dynamic information is absolutely unacceptable for decision making of any agent operating in dynamic environments.
Recent approaches have stopped treating dynamic parts of a scene as noise and started considering them as targets for 3D reconstruction or at least 2D tracking to preserve all present information. For instance, Dou et al. [13] proposed method for dense non-rigid reconstruction, however, it was too slow for any real-time application. This has been addressed by similar systems [27,12], however, such ap- proaches are typically limited to very small-scale indoor environments. Kundu et al. [22] proposed to reconstruct the static part of the scene and track all dynamically moving objects, however, bounding-box object tracking provide only partial information about these objects; instead we would like to maintain full 3D information of the object over time.
The key step for dynamic multi-body 3D reconstruction is deciding which parts of the scene should not be fused into the static volume and estimation of their 6DoF poses. Approaches relying solely on motion segmentation [31] are prone to "delayed" decisions, thus they often fuse objects that are not moving at the moment into the static volume, which requires special care when they eventually move. Vineet et al. [36] used semantic segmentation to avoid fusing all scene parts belonging to movable class (e.g. cars, cyclists, . . . ) into the static volume and simply visualised per-frame depth in the current camera view instead, hence they only suppressed the ghosting artifact but did not reconstruct full 3D models of dynamic objects. Recently, Barsan et al. [3] used stereo scene flow. However, such methods work reliably only in the very near proximity of the car since the depth error grows quadratically with the distance [24] which represents major limitation for selfdriving scenarios where we need to perceive objects at tens or even hundreds of meters. Replacing stereo scene flow by its lidar-based counterpart is not straightforward due to the missing appearance information and complicated data association caused by non-uniformity and sparsity of the lidar measurements [4]. Moreover, the state-of-the-art methods typically take several minutes or even hours to predict.
In this paper, we propose an end-to-end system for live dense reconstruction of large-scale outdoor dynamic environments, which recovers full dense 3D information for each object. We represent the dynamic environment using a time-dependent map. We decompose the scene into the background volume corresponding to static parts of the environment and a set of independently moving objects (can be seen as analogy to "things and stuff" [1]). Each object is explicitly reconstructed in its separate and independent volume, for which we maintain relative 6DoF poses with respect to the camera at each time-step. Our system operates in an incremental manner (no batch processing), handles large-scale outdoor environments with objects at large distances, and uses computationally efficient subsystems running in (near) real-time. Thus, it produces the outputs onthe-fly, as the robot is moving throughout the environment which is essential to enable real-time decision making.
To address the key challenges, i.e. decomposing the scene into background and independent objects, estimating their 6DoF poses and dense depth prediction, we leverage recent advancements in data-driven approaches (supervised CNNs). More specifically, given a stereo video (Fig. 2 A), we use a 2D object detector (Fig. 2 D) to generate bounding boxes for objects present in the current frame. Then we use sparse lidar measurements and Frustum PointNet [30] ( Fig. 2 E) to estimate 3D bounding box, its dimensions and relative 6DoF pose with respect to the current camera frame in each proposal. The 2D proposals are fed in parallel into multi-object tracker [23] to produce long-term tracklets for data-association. Since we use stereo camera, we predict dense depth using PSMNet [8] (Fig. 2 B) and estimate camera poses using visual odometry [15] (Fig. 2 C). Finally, the dense depth maps are segmented within each 3D box, and resulting "masked" depth maps are fused into corresponding (background or object) volumes. We use memory efficient sparse data structures to enable dense 3D reconstruction of large-scale dynamic environments (Fig. 2 F).
Note, that our data-driven approach does not require establishing multi-frame dense per-pixel correspondences, and is able to predict 3D boxes independently in each frame. Our approach also does not make any differences between objects that are currently moving or standing still -this has twofold advantage: i) static map is not cluttered by spurious objects, ii) we do not need to introduce any additional mechanism converting objects from static volume into an independent one, when the previously stationary object moves.

Related work
There is a large body of literature on incremental largescale outdoor 3D reconstruction. We will focus on approaches addressing dense 3D reconstruction using stereo or lidar data for outdoor scenes with rigidly moving objects.
Live Static Scene Reconstruction. KinectFusion [28] represents an early approach to real-time fusion of depth data from Kinect over time to recover accurate high-quality surfaces, however, it used regular voxel grid and hence was limited to small-scale environments. Many methods have utilized the fact that large parts of 3D environments are empty to resolve these scalability and memory inefficiency issues. Some notable approaches are voxel block hashing [29], voxel hierarchy [9] or elastic reconstruction [40] for indoor environments, and incremental dense stereo reconstruction system of Vineet et al. [36] for outdoor scenes. Recently, McCormac et al. [25] proposed objectlevel SLAM, however, they assume static environments.
Dynamic Scene Reconstruction. Vineet et al. [36] proposed hash-based approach for reconstruction of large-scale dynamic environments from stereo camera. They used semantic segmentation to avoid fusing dynamic objects in the static map and hence reduced the ghost artifact that generally appears when fusing dynamic content into the stationary volume. In contrast to our work, their approach is essentially not reconstructing dynamic objects in separate volumes, rather only visualises their per-frame depth in the current camera view. Therefore all information from previous frames is lost and it is impossible to recover full spatial extend of moving objects or reason about their actions.
Similarly, Reddy et al. [32] first perform motion segmentation to separate static and moving objects and then enforce semantic constraints in bundle adjustment for individual object reconstruction. This system demonstrated promising results, however, it is not able to reach (near) real-time rates and cannot scale to large environments due to expensive CRF-based optimization performed during motion segmentation and bundle adjustment. Jian et al. [18] use sparse subspace clustering to segment dynamically moving objects, however this approach is also slow to be deployed in any real-world application. Finally, co-fusion [35] and MID-fusion [39] utilize motion and semantic information to track and reconstruct static and dynamic objects from a sequence of RGBD data. However, most of their experiments were conducted in indoor environments using Kinect data; it needs to be shown if such methods handle large outdoor environments where distances between objects are often in tens of meters and noise present in stereo based system.
Kochanov et al. [19] uses stereo-based semantic segmentation and scene flow to propagate dynamic content of the scene in the map, however, such objects are not reconstructed. Moreover, this system relies on scene flow approach of Vogel et al. [37] which takes around 300 seconds per frame, thus making the whole system unsuitable for any real-time setup. Barsan et al. [3] recently presented a similar approach, relying on sparse scene flow and RANSAC to estimate rigid body motion of each dynamically moving object. However, at the core of this method lies (sparse) feature matching which could pose problems for highly reflective and specular objects such as cars. Further, stereo scene flow methods are typically unable to estimate object pose accurately due to lack of parallax motion at distance. They are also more susceptible to noise in depth and most state-of-the-art approaches are too slow.
Object Pose Estimation. A popular approach for estimating 6 DoF object poses involves first performing motion segmentation, followed by sparse feature matching and robust RANSAC-based pose estimation [18] In this work, we instead follow a learning based approach. Random forestbased approaches typically required hypothesis sampling and/or were shown to work only with Kinect-like depth maps in very near distances (indoor environments) [6,20,7]. In recent years, several methods based on convolution neural network (CNN) have been proposed. These methods typically directly generate oriented 3D boxes from single RGB image [26,10], using RGB and point-cloud [21] or just based on point cloud [30]. In this work, we use pointcloud based Frustum PointNet model [30] due to its efficiency and accuracy on 3D object detection task.

Live Reconstruction of Dynamic Worlds
Our system uses a combination of a stereo camera and lidar sensors. The stereo cameras are intrinsically calibrated and stereo rectified to simplify disparity evaluation. We also assume that extrinsic calibration between the two cameras and lidar is known. Hence, we first can project the sparse lidar measurements into the camera coordinate system in each frame. In order to decompose the scene into static background and independent (dynamic) objects, we run 2D object detector which produces "proposals" for estimation of 3D bounding boxes, their dimensions and 6DoF poses from sparse lidar measurements. The 2D proposals are also used to establish long-term data association through multi-object tracker, which runs in parallel to 3D detector, as well as dense depth and camera pose estimation. Finally, we "segment" the depth maps and fuse them into their respective volumes. The following subsections describe these parts of our reconstruction system in more detail.

Dynamic map representation
We represent the world using a dynamic map. The state of our map is at each time-step t encoded using the tuple of W t = {P cw sponding to background (static) part of the environment at time t. In other words, this part of the map corresponds to standard kinect fusion-like approaches.
The dynamic content of the scene is encoded using sets of object poses P co t and corresponding relative volumes V o t . Each of N independent (dynamic) volumes is assigned a unique ID by the multi-object tracker. Then, set N } represents associated relative object poses (Fig. 2 F). Note, that we describe the objects using unique IDs assigned to all N objects to avoid clutter in notation, however at each timestep t only objects visible in the current view frustum are present in the dynamic map. Fig. 3 illustrates different coordinate systems and their relationships for transforming points between them. Note, that the global reference frame can be attached to camera pose of the first frame.

Depth estimation
The task of dense depth estimation involves disparity prediction from calibrated and rectified stereo image pairs. Then, we can convert disparity to depth as d i = bf zi , where d i is depth at pixel i corresponding to disparity value z i , baseline b and camera focal length f . Standard disparity estimation methods typically use some form of a prior over per-pixel matching along the scan-line and CRF-based optimization, however, more recent data-driven CNN-based approaches started providing more accurate results at faster run-times. Thus we use in this work pyramid stereo matching network (PSM Net) [8], which represents one of the most accurate and efficient methods for disparity estimation on the KITTI benchmark. Since data-driven methods trained on the KITTI dataset typically predict non-zero (non-invalid) values also for regions corresponding to sky (models are not penalized for such predictions during the training), we form a convex hull of lidar measurements and explicitly invalidate all depth data outside the hull.

Camera pose estimation
Given a sequence of stereo image pairs, we estimate 6DoF camera pose P cw t describing rotation and translation of the camera with respect to the global reference frame at each time t. Precise camera pose estimation is important for high quality static scene reconstruction V bg t . In this paper, we use LIBVISO2 library [15], which minimizes reprojection error of sparse feature matches. In particular, this approach tiles the images into buckets to ensure the detected features are uniformly distributed across the images. At the same time, this procedure significantly speeds-up and robustifies the matching process. Then, the detected features are matched along epipolar lines with circular consistency check, and sporadic outliers are removed by Delaunay triangulation. The final pose is obtained by minimising repro- Figure 3. Coordinate systems: the camera frame is attached to the world in the first frame and data from lidar as well as recognized objects are represented using the current camera frame. jection error using Gauss-Newton optimiser wrapped into RANSAC to increase robustness against outliers. This procedure is combined with standard constant velocity Kalman filter. Note, that our pipeline is general and any other camera pose estimation method can be used instead.

2D object detection
We pose estimation of independent objects present in frame t as 2D object detection problem, where the goal is to describe objects of interest such as cars using tight axis-aligned 2D bounding boxes. Several CNN-based methods such as Faster RCNN model [34], MobileNet [17] or YOLO [33] have been proposed. We use popular Faster RCNN model [34], which at a high level consists of three parts: feature network, region proposal network and object detection network. First, the feature network, which we implement using ResNet-101 [16], applies a series of convolutions and ReLU non-linearities to generate a high level feature representation of input image. Given this feature representation, a class agnostic region proposal network (RPN) generates a set of proposals that could potentially contain objects of interest. This typically reduces the search space to only 300 regions. In the final stage, the object classes, confidence scores and bounding box locations are predicted for each of these 300 boxes and non-maxima suppression is applied to generate the final set of independent objects.

Object pose estimation
The task of volumetric reconstruction of each dynamic object requires estimating accurate pose of each object. Let P o t,i ∈ SE(3) be the pose of i th object with respect to camera at time t. Here, pose P o t,i is composed of the rotation matrix R o t,i ∈ SO(3) and translation vector t o t,i ∈ R 3 expressed in the camera reference frame (shown in Fig. 3).
We formulate the problem of 6 DoF object pose estimation as 3D object detection problem that encloses the object of interest inside tight 3D bounding box. These 3D bounding boxes then provide both rotation and translation vectors with respect to the current camera frame. In this work, we use popular CNN-based Frustum Point Net (FPointNet) method [30] which estimates 3D bounding boxes from lidar measurements in each input 2D bounding box.
At high level, FPointNet model consists of frustum proposal, 3D instance segmentation and 3D object detection modules. Frustum proposal module carves out a frustum in 3D where the object of interest could be present. The points lying inside the frustum are segmented into objects or background using 3D instance segmentation module. Then, 3D box estimation module fits a tight 3D bounding box around the segmented points corresponding to the object of interest. Finally, object pose information P o t,i for i th object at time t is recovered from these 3D bounding boxes.

Object tracking
We use multi-object tracking-by-detection paradigm to associate object instances across time with unique IDs. At the core of this approach lies associating detected 2D boxes in the current frame t to the existing tracks. This is typically formulated as a labeling problem in maximum-a-posteriori (MAP) estimation framework. Though the problem is NPhard, an approximate solution to the MAP problem can be found by min-cut/max-flow, however, this approach is too slow for any online setting. Our pipeline is based on the method of Lenz et al. [23] that provides an efficient solution to this MAP problem, suitable for online / streaming applications. In particular, this method restricts the number of past frames for data association and develops an online successive shortest-path algorithm that handles streaming data without significantly affecting tracking accuracy.

Large-Scale Dynamic Scene Reconstruction
Our dynamic scene reconstruction first decomposes the scene at time t into static background and N t objects (here, N t denotes a subset of objects that are present in frame t). Then, these individual RGB-D slices are integrated into the respective volumes of our dynamic map.
Scene decomposition. We take a dense RGB-D map as an input, and our goal is to split it into (N t + 1) RGB-D slices (N t detected objects at time t and static background). To this end, depth data D t is first "backprojected" into the actual 3D points. Then, points lying inside space carved out by the i-th 3D bounding box are considered to be part of the i-th object. This is typically sufficient to decompose the scene into N t objects, however, this procedure could be enhanced e.g. using segmentation output from FPoint-Net. Note that the points that do not belong to any of N t objects are automatically assigned to the static background.
It should be noted that the 3D boxes are not always accurate (tight). While presence of such noise may not degrade reconstruction quality of N t objects (we do not need to integrate depth map corresponding to full object at each time t), inclusion of points belonging to the (moving) objects into the static volume would lead to "ghosting aritifacts".
To avoid such issues, we approach it in a conservative way and simply invalidate the whole 2D bounding box when "masking out" objects for the static depth map to ensure no object points would get accidentally fused into the static volume. Alternatively, one could rather invalidate 3D bounding box with synthetically enlarged dimensions e.g. by 15%. It is true that such strategies could introduce more holes into the reconstructed scene, however, this does not seem to represent a major problem in practice since these holes get automatically filled-in from other camera and/or object views available across the sequence.
Hash-based TSDF fusion. At the core of our dynamic reconstruction lies hash-based elastic fusion, which was originally developed for static scene reconstruction [40,41]. It provides an efficient and scalable approach for integration of RGB-D data to the volumentric 3D scene representation. In order to handle large-scale environment, elastic fusion allocates space only for voxels that are within small distance from the perceived surface, which is measured by truncated signed distance function (TSDF) [11]. Each voxel stores color and TSDF measurements. These values are updated over time by taking running average over the newly arrived color and TSDF measurements.
Management of a dynamic map. As we have mentioned in §3.1, our dynamic map W t is represented by two components. First, it incorporates information about static volume V bg t , and camera poses P cw t at each time t forming a camera trajectory. Second, it also consists of a set of N t independent volumes V o t corresponding to objects and their associated relative poses P co t in camera frame reference. Reconstruction process starts by allocating the static volume. At each time t, the masked depth map for the static scene is integrated into the static volume V bg t using camera pose P cw t (estimated in §3.3). The dynamic map W t is updated with the static volume and camera pose at time t.
In order to reconstruct each object present at time t, we begin by checking if the object volume exists in the dynamic map W t . If such a volume is not found in the dynamic map, we first allocate a new volume V o t for this object. Then, we integrate a segmented RGB-D slice for the object into the volume V o t using object pose P co t (recovered in §3.5). Note that this pose P co t is always relative to the current camera reference frame. Therefore the objects are reconstructed directly without need to explicitly compute position and rotation in the global coordinate frame. Hence potential drift of camera pose estimation does not influence quality of dense 3D reconstruction of dynamic objects (of coarse, the absolute pose of an object in the global coordinate frame is still dependent on camera trajectory).
Visualisation. At each time t, the current state of the dynamic map W t is being visualised by first placing dynamic objects into their respective locations within the world coordinate system. This involves expressing points in the object frame to the world frame by applying projection using P ow t = P cw t P o t . The current state of dynamic map W t then can be visualised from arbitrary camera, we typically use camera-pose P cw t at time t to get the actual live view. We could also visualise not just the "on-the-fly" live view, as seen from the moving camera, but also the virtual (off-line) "fly through the reconstructed scene" (i.e. the final state of volumes). This can be done simply by using the final state of all volumes in all frames of the sequence.

Results
We use KITTI dataset [14] to evaluate our approach. The KITTI dataset contains a variety of challenging outdoor sequences containing many moving objects such as cars. These sequences were captured in residential, city and highway areas. Imaging sensors include two colour and two grayscale PointGrey Flea2 cameras and Velodyne HDL-64E lidar. All sequences were captured at a resolution of 1241 × 376 pixels using both camera and lidar. Both sensors scan the environment at 10 Hz and cameras trigger when the spinning lidar is oriented in the same direction as cameras. We use stereo inputs from colour stereo cameras and lidar data for all experiments. Cameras were intrinsically and extrinsically calibrated, all images stereo rectified and lidar to cameras mapping is known.
We demonstrate both the qualitative and quantitative results on four diverse sequences from the KITTI tracking data. For quantitative evaluation, we use per-frame sparse lidar measurements as ground-truth data (note that is not perfect as we cannot "untwist" the measurements of spinning lidar for moving objects, but it is the best available real-world data for evaluation). We report the standard mean relative error (MRE) metric, which is defined as Here, d i and d gt i are respectively reconstructed and ground truth depth normalized over M valid lidar points. The MRE error measures relative perpixel error, i.e. an error of 0.1m at depth of 1m is penalized equally to an error of 1m at a depth of 10m. We compare our approach with a standard fusion based reconstruction method that does not explicitly handle multi-body dynamic objects. To make the comparison fair, we have adapted the baseline to large-scale outdoor environments, i.e. it uses the very same visual odometry, dense depth and parameters as our approach. We have used voxels of 4.68cm for the background volume and 1.56cm for objects. The depth considered for reconstruction was truncated at 40m. Our system is implemented on top of the Open3D library [42] and we will release the full source code upon acceptance.
Qualitative Evaluation. We qualitatively illustrate the impact of our approach in recovering high quality reconstruction of scenes with multiple moving objects. In all figures, we show "on-the-fly" output, that is the output as seen from the camera view as it is moving (c.f . §3.7).
In Fig. 7, we show more examples of how our approach accurately reconstructs moving objects along the static scene. Note the objects marked inside rectangular boxes, and how they are properly reconstructed using our multi-body dynamic fusion approach (right column), compared to standard non-dynamic fusion where both the static and dynamic objects are fused in the same map, which leads  . Typical outputs of our system: (left) input images with detected bounding boxes associated over time (trajectories coded by different colours), (middle) Phong-shaded textured output, (right) in our approach, each object is explicitly treated as an independent instance reconstructed in a separate volume; here we visualise it by using colour-coding corresponding to a particular tracklet ID. Figure 8. Failure cases: whenever the detector misses an object, this part of the image would get fused into the static volume, hence would lead to "ghosting artifact" for objects which are moving.  Fig. 7. It should be emphasized, that even if the output of non-dynamic fusion and our approach look the same when cars are not moving, the key difference between the two is that we explicitly reconstruct each instance it its own volume which i) simplifies reasoning about object actions and ii) does not require any extra mechanism when the car starts moving. To better illustrate quality of reconstructed objects, we show multiple examples in Fig. 6 and also the surface normals in Fig. 5. Finally Fig. 8 illustrates most common failure cases, i.e. situation when the object detector misses some cars present in the scene. Full sequences are shown in the supplementary video. Quantitative Evaluation. Here we provide the quantitative evaluation for non-dynamic and proposed dynamic approaches. We consider pixels with ground-truth depth within 10m, 20m, 30m and 40m for quantitative evaluation. In Tab. 1, we report the standard mean relative error (MRE) evaluated across the whole image. In order to better highlight the quality of reconstructed objects, we also evaluate our method on points lying inside the 2D object bounding boxes as shown in Tab. 2. On most of the sequences, we can see that our dynamic reconstruction approach achieves a significant improvement of almost 2× reduced error on estimated depth for dynamic objects compared to the baseline method with non-dynamic fusion. Overall, the presented approach for multi-body reconstruction achieves almost 5% to 25% improvement in depth accuracy over the baseline method on different sequences. This suggests that the dy- namic reconstruction is important for alleviating ghost artifact in the reconstruction. The only sequence, on which do not achieve better results is Scene 3, which is mostly static. Therefore it is not surprising our method achieves slightly worse results, however, it should be noted that our method treats individual objects as independent instances in contrast to non-dynamic fusion approach. Timing details. The presented approach runs at around 2fps. The main limiting factor is PSMNet based stereo estimation which takes around 410ms for every stereo pair. The other parts of the pipeline are relatively faster to evaluate; in particular visual odometry runs at 50ms, MOT tracker at 10ms, Faster-RCNN at 79ms and FPointNet at 170ms. Further, these components run in parallel to PSMNet.

Conclusion
We have presented an end-to-end system for live reconstruction of large scale dynamic scenes. The key observation is that the 6 DoF object pose estimation for dynamic scene reconstruction can be framed within 3D object detection framework. Such framework helped to represent whole scene using a time-dependent dynamic map, in which each object is explicitly reconstructed in its own independent volume. We have demonstrated high quality reconstruction of static and dynamic objects on various KITTI sequences.
The presented approach could benefit from improvements in efficiency and accuracy of depth estimation, 2D and 3D detection or multi-object tracking. Further, temporal smoothness in object pose estimation would help to regularize reconstruction of each individual object.


extfieldsofstudy:
Computer Science
Mathematics

text:
Deep Model Predictive Control with Online Learning for Complex Physical Systems

The control of complex systems is of critical importance in many branches of science, engineering, and industry. Controlling an unsteady fluid flow is particularly important, as flow control is a key enabler for technologies in energy (e.g., wind, tidal, and combustion), transportation (e.g., planes, trains, and automobiles), security (e.g., tracking airborne contamination), and health (e.g., artificial hearts and artificial respiration). However, the high-dimensional, nonlinear, and multi-scale dynamics make real-time feedback control infeasible. Fortunately, these high-dimensional systems exhibit dominant, low-dimensional patterns of activity that can be exploited for effective control in the sense that knowledge of the entire state of a system is not required. Advances in machine learning have the potential to revolutionize flow control given its ability to extract principled, low-rank feature spaces characterizing such complex systems. We present a novel deep learning model predictive control (DeepMPC) framework that exploits low-rank features of the flow in order to achieve considerable improvements to control performance. Instead of predicting the entire fluid state, we use a recurrent neural network (RNN) to accurately predict the control relevant quantities of the system. The RNN is then embedded into a MPC framework to construct a feedback loop, and incoming sensor data is used to perform online updates to improve prediction accuracy. The results are validated using varying fluid flow examples of increasing complexity.

Introduction
The robust and high-performance control of fluid flows presents an engineering grand challenge, with the potential to enable advanced technologies in domains as diverse as transportation, energy, security, and medicine. The control of fluid flows is challenging due to the confluence of strong nonlinearity, high-dimensionality, and multi-scale physics (e.g., turbulence), thus typically leading to an intractable optimization problem. However, recent advances in machine learning (ML) are revolutionizing computational approaches for these traditionally intractable optimizations by providing principled approaches to feature extraction methods with improved optimization algorithms. We develop a deep learning model predictive control framework that leverages ML methods to achieve robust control performance in a complex fluid system without recourse to the governing equations, and with access to only a few physically realizable sensors. This sensor-based, data-driven learning architecture is critically important for practical implementation in control-based engineering applications.
Model predictive control (MPC) [Garcia et al., 1989, Lee, 2011 is among the most versatile and widely used model-based control approaches, which involves an online optimization of the control strategy over a predictive receding horizon. Generally, improved models result in better control performance [Weisberg Andersen and Kümmel, 1992], although the online iterative optimization requires relatively inexpensive models [Xi et al., 2013, Mohanty, 2009]. The challenge of MPC for controlling fluid flows is centered on the the high-dimensional nature of spatio-temporal flow fields. Fortunately, these systems often exhibit dominant patterns of low-dimensional activity. Indeed, it is observed that flying insects, birds, and bats are able to harness these dominant patterns to execute exceptional control performance. Thus, there is a vibrant field in reduced-order models that balance accuracy and efficiency to capture essential physical mechanisms, while discarding distracting features. The MPC architecture, like much of ML, can be trained to exploit the dominant, low-dimensional patterns of dynamic activity in order to achieve significant gains in performance.
Among machine learning algorithms, deep learning [Krizhevsky et al., 2012, LeCun et al., 2015, Goodfellow et al., 2016 has seen unprecedented success in a variety of modeling tasks across industrial, technological, and scientific disciplines. It is no surprise that deep learning has been rapidly integrated into several leading control architectures, including MPC and reinforcement learning. Deep reinforcement learning [Mnih et al., 2015, Rezende et al., 2014 has been widely used to learn games [Silver et al., 2016, Mnih et al., 2015, and more recently for physical systems, for example to learn flight controllers [Kim et al., 2004, Tedrake et al., 2009 or the collective motion of fish [Verma et al., 2018]. DeepMPC [Verma et al., 2018] has also emerged as a leading control strategy that combines the representational power of deep neural networks with the flexible optimization framework of MPC. There exist various approaches for using data-driven surrogate models for MPC (e.g., based on the Koopman operator [Korda and Mezić, 2018, 2018, Nair et al., 2018, Peitz and Klus, 2019, Peitz, 2018), and DeepMPC has considerable potential [Baumeister et al., 2018, Morton et al., 2018. [Morton et al., 2018] recently demonstrated the ability of DeepMPC to control the flow past a laminar circular cylinder; the flow considered in this work is nearly linear, and may be well approximated using more standard linear modeling and control techniques, although this study provides an important proof of concept.
In this work, we extend DeepMPC for flow control in two key directions: (1) we apply this architecture to control significantly more complex flows that exhibit broadband phenomena; and (2) we develop our architecture to work with only a few physically realizable sensors, as opposed to earlier studies that involve the assumption of full flow field measurements. There is a significant gap between academic flow control examples and industrially relevant configurations. The present work takes a step towards complexity and importantly develops a data-driven, sensor-based architecture that is likely to scale to harder problems. Importantly, one rarely has access to the full flow field, and instead control must be performed with very few measurements [Manohar et al., 2018]. Biological systems, such as flying insects, provide proof by existence that it is possible to enact extremely robust control with limited flow measurements [Mohren et al., 2018]. In this work, we design our learning approach to leverage time histories of limited sensors (i.e., measurable body forces), providing a more direct connection to engineering applications. Finally, we provide a physical interpretation for the learned control strategy, which we connect to the underlying symmetries of the dynamical system.

Model predictive control of complex systems
Our main task is to control a complex nonlinear system in real-time. We do this by using the wellknown MPC paradigm, in which an open-loop optimal control problem is solved in each time step using a model of the system dynamics: Here, f (y) = z is the observation of the time (and potentially space) dependent system state y that has to follow a reference trajectory z ref , and α and β are regularization parameters penalizing the control input as well as its variation. Φ is the time-T map of the system dynamics, i.e., it describes how the system state evolves over one time step given the current state and control input. Problem (1) is then solved repeatedly over a fixed prediction horizon N and the first entry is applied to the real system. As the initial condition in the next time step, the real system state is used such that a feedback behavior is achieved. Note that u −1 is the control input that was applied to the system in the previous time step. The scheme is visualized in Fig. 1, where the MPC controller based on the full system dynamics is shown in green. MPC has successfully been applied to a very large number of problems. However, a major challenge is the real-time requirement, i.e., (1) has to be solved within the sample time ∆t = t i+1 − t i . In order to achieve this, linearizations are often used. Since even these can be too expensive to solve for large systems, we will here use a surrogate model which does not model the entire system state but only the control relevant quantities. In a flow control problem, these can be the lift and drag coefficients of a wing, for instance. Such an approach has successfully been used in combination with surrogate models based on Dynamic Mode Decomposition [Peitz and Klus, 2019] or Clustering [Nair et al., 2018]. We thus aim at directly approximating the dynamics Φ for the observable z = f (y) and replacing the constraint in Problem (1) by the surrogate model: The resulting MPC controller is visualized in Fig. 1 in orange.

DeepMPC: model predictive control with a deep recurrent neural network
In order to solve (2), the surrogate model Φ for the control relevant system dynamics is required. For this purpose, we will use a deep RNN architecture which is implemented in TensorFlow [Abadi et al., 2016]. Once the model is trained and can predict the dynamics of z (at least over the prediction horizon), the model can be incorporated in the MPC loop.

Design of the RNN
As mentioned previously, the surrogate model is approximated using a deep neural network similar to [Baumeister et al., 2018]. The RNN consists of an encoder and a decoder (cf. Fig. 2a), where the decoder performs the actual prediction task and consists of N cells -one for each time step in the prediction horizon. The encoder only predicts a latent state and this way takes the long term dynamics into account. Consequently, the encoder cells contain only the part of the decoder cells responsible for predicting the latent variable, cf. Fig. 2b.
In order to capture the system dynamics using few observations only, we use delay coordinates, an approach which has been successfully applied to many systems ( ). Consequently, each RNN cell takes as input a sequence of past observations as well as the current control input. The cells are divided into three functional parts capturing different parts of the dynamics, i.e., long term and current dynamics as well as the influence of the control inputs (see Fig. 2b). Therefore, the input of each cell k is divided into a time series (z, u) k−2d−1,...,k of the observable and the corresponding control input and a second sequence of control inputs u k−d,...,k , where d is the number of delays. The RNN based MPC problem (2) is solved using a gradient based optimization algorithm like gradient descent or BFGS. The required gradient information with respect to the control inputs can be calculated using standard back-propagation through time. Since the RNN model needs at least temporal information from M + 2d time steps (M encoder cells and input sequence of length 2d) to predict future states, there is an initialization phase in the MPC framework during which the control input is fixed to 0.

Training of the RNN
The RNN is trained in an offline phase using time series data ((z 0 , u 0 ), . . . , (z n , u n )). For the data collection, the system is actuated with random yet continuously varying inputs. In order to overcome difficulties with exploding and vanishing gradients as well as problems with the effect of nonlinearities when iterating from one time step to another, we use the three-stage approach for learning as was proposed in [Lenz et al., 2015] and used in [Baumeister et al., 2018]. First, a Conditional Restricted Boltzmann Machine is used to compute good initial parameters for the RNN according to the work by Taylor et al. [2007]. In a second step, only the prediction of a single time step is trained. In the final step, another training phase is performed, this time for the RNN with N decoder cells that yield predictions for the system state over N time steps.

Results
In order to study the performance of the proposed MPC framework, four flow control problems of increasing complexity are considered. Instead of a real physical system, we here use a numerical simulation of the full model as our plant. In all four cases, the flow around one or multiple cylinders (cf. Fig. 3) is governed by the incompressible 2D Navier-Stokes equations with fluid entering from the left at a constant velocity y in . The Reynolds number Re = y in /νD (based on the kinetic viscosity ν and the cylinder diameter D) ranges from 100 to 200, i.e., we are in the laminar regime. The full system is solved using a finite volume discretization and the open source solver OpenFOAM, cf. [Jasak et al., 2007]. The control relevant quantities are the lift and drag forces (i.e., the forces in x 2 and x 1 direction) acting on the cylinders. These consist of both friction and pressure forces which can be computed from the system state (or easily measured in the case of a real system).

One Cylinder
The first example is the flow around a single cylinder, cf. Fig. 3a, which was also studied in [Morton et al., 2018]. At Re = 100, the uncontrolled system possesses a periodic solution, the so called von Kármán vortex street. On the cylinder, the fluid and the cylinder velocity are identical (no-slip condition) such that the flow can be steered by rotating the cylinder. The control relevant quantities are the forces acting on the cylinder -the lift C l and drag C d . We thus set z = (C l , C d ), and the aim is to control the cylinder such that the lift follows a given trajectory, e.g., a piece-wise constant lift.
In order to create training data, a time series of the lift and the drag is computed from a time series of the full system state with a random control sequence. To avoid high input frequencies, a random rotation between −2 and 2 is chosen every 0.5 sec. The intermediate control inputs are then computed using a spline interpolation on the grid of the time-T map, where ∆t = 0.1 sec. For the RNN training, a time series with 110 000 data points is used which corresponds to a duration of 11 000 sec.
In a first step, the quality of the RNN prediction is evaluated on the basis of an exemplary control input sequence. As one can see in Fig. 4a, the prediction is very accurate over several time steps for many combinations of observations z and control inputs u. There are only small regions where the predictions deviate stronger from the real lift and drag. The good prediction quality enables us to use the RNN in the MPC framework, where the aim is to force the lift to +1, 0 and −1 for 20 sec, respectively. This results in the following realization of (2): The parameter β is set to 0.01 in order to avoid too rapid variations of the input. Furthermore, the control is bounded by the minimum and maximum control input of the training data (i.e., ±2). We solve the optimization problem (3) over a prediction horizon of length N = 5, and we use a BFGS method for the optimization. As shown in Fig. 4b, the DeepMPC scheme shows very good performance. Due to the periodic fluctuation of the uncontrolled system, a periodic control is expected to suppress this behavior which is what we observe.

Fluidic Pinball
In the second example, we control the flow around three cylinders in a triangular arrangement, as shown in Fig. 3b. This configuration is known as the fluidic pinball; see [Deng et al., 2018] for details. The control task is to make the lift of the three cylinders (C l,1 , C l,2 and C l,3 ) follow given trajectories by rotating the rear cylinders while the cylinder in the front is fixed. We thus want to approximate the system dynamics of the forces acting on all three cylinders, i.e., z = (C l,1 , C l,2 , C l,3 , C d,1 , C d,2 , C d,3 ). Similar to the single cylinder case, the system possesses a periodic solution at Re = 100. When increasing the Reynolds number, the system dynamics become chaotic (cf. [Deng et al., 2018]) and the control task is much more challenging. We thus additionally study the chaotic cases Re = 140 and Re = 200. As we now have two inputs and three reference trajectories, we obtain the following realization of problem (2): where the value of β is set to 0.1. The prediction horizon is N = 5 for Re = 100 and N = 10 for Re = 140 and Re = 200, respectively.
For all three Reynolds numbers, the training data is computed by simulating the system with random yet smoothly varying control inputs as before, i.e., random values between −2 and 2 for each cylinder every 0.5 sec. Due to the significantly smaller time step of the finite volume solver for the fluidic pinball, the control is interpolated on a finer grid with step size 0.005 sec. Since the control input has to be fixed over one lag time due to the discrete-time mapping via the RNN, the mean over one lag time (i.e., over 20 data points) is taken for u. Time series with 150 000, 200 000 and 800 000 data points are used for Re = 100, Re = 140 and Re = 200, respectively.
At Re = 100, where the dynamics are quasi-periodic, the control is quite effective, almost comparable to the single cylinder case, cf. Fig. 5a. In comparison, the error e mean for the mildly chaotic case Re = 140 (Fig. 5b) is approximately one order of magnitude larger. The reference is still tracked, but larger deviations are observed. However, since the system is chaotic, this is to be expected. It is more difficult to obtain an accurate prediction and -more importantly (cf. [Peitz, 2018]) -the system is more difficult to control. In order to improve the controller performance, we incorporate system knowledge, i.e., we exploit the symmetry along the horizontal axis. Numerical simulations suggest that this symmetry results in two attracting regions in the observation space and that the system changes only occasionally from one region to the other, analogous to the Lorenz attractor . Therefore, we symmetrize (and double) the training data as follows: This step is not necessary at Re = 100, since the collected data is already nearly symmetric. Nevertheless, the amount of training data can be doubled by exploiting the symmetry and therefore, the simulation time to generate the training data can be reduced.
In Fig. 5c, the results for Re = 140 with symmetric training data is shown. In this example, the tracking error is reduced by nearly 50%. In particular, the second lift is well-controlled. This indicates that it is advisable to incorporate known physical features such as symmetries in the data, assimilation process. However, we still observe that the existence of two attracting regions results in a better control performance for one of the cylinders, depending on the initial condition. For the final example, the Reynolds number is increased to Re = 200 in order to further increase the complexity of the dynamics, and symmetric data is used again. Due to the higher Reynolds number, switching between the two attracting regions occurs much more frequently, and the use of symmetric data yields less improvement. The results are presented in Fig. 5d, and we see that even though tracking is achieved, the oscillations around the desired state are larger.
In Fig. 6a the mean and the maximal error for the three Reynolds numbers are shown. Since the system dynamics become more complex with increasing Reynolds number, both the prediction by the RNN and the control task itself become more difficult and the tracking error increases.
In order to study the robustness of the training process as well as the influence of the amount of training data on the tracking error, 5 identical experiments for Re = 200 have been performed for different amounts of training data (10%, 50% and 100% of the symmetrized data points), respectively, see Fig. 6b. We observe no trend with respect to the amount of training data, in particular considering that the standard deviation is approximately 0.03 for the average and 0.15 for the maximal error. Short time series already cover large parts of the dynamics and are thus sufficient to train the model. In order to further improve performance, the size of the RNN as well as the length of the training process would have to be increased significantly and also, significantly smaller lag times would be required.
Since we want to avoid this further increase in computational effort and data collection, we instead use small amounts of data sampled in the relevant parts of the observation space, i.e., close to the desired state. To this end, we perform online updates using the incoming sensor data. In our final experiment, we study how the control performance can be improved by performing online updates of the RNN using the incoming data. In the feedback loop, a new data point is collected from the real system at each time step, and our strategy is to collect new data over 25 sec for each update. By exploiting the symmetry as proposed in (4), we obtain 500 points within each interval that are used for further training of the RNN. In the right plot of Fig. 7, we compare the tracking error over several intervals, and we see that the error can be decreased very efficiently in a short time by using online learning (see also Fig. 5a for a comparison). Besides reducing the tracking error, the control cost ||u|| 2 decreases, which further demonstrates the importance of using the correct training data. Significant improvements of both the tracking performance as well as the controller efficiency are obtained very quickly with comparably few measurements.

Conclusion and Further Work
We present a deep learning MPC framework for feedback control of complex systems. Our proposed sensor-based, data-driven learning architecture achieves robust control performance in a complex fluid system without recourse to the governing equations, and with access to only a few physically realizable sensors. In order to handle the real-time constraints, a surrogate model is built exclusively for control relevant and easily accessible quantities (i.e., sensor data). This way, the dimension of the RNN-based surrogate model is several orders of magnitude smaller compared to a model of the full system state. On the one hand, this enables applicability in a realistic setting since we do not rely on knowledge of the entire state. It further allows us to address systems of higher complexity, i.e., it is a sensor-based and scalable architecture. The approach shows very good performance for high-dimensional systems of varying complexity, including chaotic behavior. To avoid prohibitively large training data sets and long training phases, an online update strategy using sensor data is applied. This way, excellent performance can be achieved for Re = 100. For future work, it will be important to further improve and robustify the online updating process, in particular for chaotic systems. Furthermore, it is of great interest to further decrease the training data requirements by designing RNN structures specifically tailored to control problems. The deep learning MPC is a critically important architecture for real-world engineering applications where only limited sensors are available to enact control authority.