Search

Motion planning in unstructured and low-speed environments is a fundamental and difficult task for all mobile robotics. If we view motion planning as an optimization problem, the non-convex collision avoidance constraints and the nonlinear vehicle dynamic constraints make motion planning challenging and time-consuming. In this paper, we propose a Successive Linearization in Feasible Set (SLiFS) algorithm to address these two difficulties. SLiFS consists of two steps. The first step is to iteratively construct convex feasible sets around the current trajectory to approximate non-convex collision avoidance constraints. The second step is to successively linearize the nonlinear dynamic constraints along the current trajectory and further penalize them into the objective function to avoid infeasible linearized constraints, so that the current trajectory can be reshaped within the obtained convex feasible sets by iteratively solving the linearized optimization problem. The main innovation of SLiFS algorithm is that we consider the $L_{1}$ norm type penalty function in the second step. We find that the sparsity of the $L_{1}$ norm might help to satisfy the robotic dynamic constraints by numerical experiments. Numerical testing results show that our proposed SLiFS algorithm has a high success rate to find feasible trajectories and costs much less time than the classical interior-point method. [ABSTRACT FROM AUTHOR]

Feature reduction is an important aspect of Big Data analytics on today’s ever-larger datasets. Rough sets are a classical method widely applied in attribute reduction. Most rough set algorithms use the priori domain knowledge of a dataset to process continuous attributes through using a membership function. Neighborhood rough sets (NRS) replace the membership function with the concept of neighborhoods, allowing NRS to handle scenarios where no a priori knowledge is available. However, the neighborhood radius of each object in NRS is fixed, and the optimization of the radius depends on grid searching. This diminishes both the efficiency and effectiveness, leading to a time complexity of not lower than $O(N^2)$ O (N 2) . To resolve these limitations, granular ball neighborhood rough sets (GBNRS), a novel NRS method with time complexity $O(N)$ O (N) , is proposed. GBNRS adaptively generates a different neighborhood for each object, resulting in greater generality and flexibility in comparison to standard NRS methods. GBNRS is compared with the current state-of-the-art NRS method, FARNeMF, and find that GBNRS obtains both higher performance and higher classification accuracy on public benchmark datasets. All code has been released in the open source GBNRS library at http://www.cquptshuyinxia.com/GBNRS.html. [ABSTRACT FROM AUTHOR]

In the Steiner forest problem, we are given a set of terminal pairs and need to find the minimum cost subgraph that connects each of the terminal pairs together. Motivated by the recent work on greedy approximation algorithms for the Steiner forest, we provide efficient implementations of existing approximation algorithms and conduct a thorough experimental study to characterize their performance. We consider several approximation algorithms: the influential primal‐dual 2‐approximation algorithm due to Agrawal, Klein, and Ravi, the greedy algorithm due to Gupta and Kumar, and a randomized algorithm based on probabilistic approximation by tree metrics. We also consider the simplest heuristic greedy algorithm for the problem, which picks the closest unconnected pair of terminals and connects it using the shortest path between the terminals in the current graph. To characterize the performance of the algorithms, we created a new library with more than one thousand Steiner forest problem instances and conducted an extensive experimental analysis on those instances. Our analysis reveals that for the majority of instances the primal‐dual algorithm is the fastest among all the algorithms considered here, and obtains solutions that are very close to the optimal solutions obtained by solving the integer program formulation of the problem. [ABSTRACT FROM AUTHOR]

In order to increase the nonlinear fitting performance of functional link neural network (FLNN), a novel chebyshev functional link spline neural filter (CFLSNF) to apply in system identification is proposed. Compared with the weak nonlinearity and boundedness of the fixed activation function (e.g., $sigmoid$ and $tanh$), CFLSNF has stronger nonlinear approximation ability than FLNN due to the flexible interpolation ability of spline activation function. At the same time, the proposed CFLSNF eliminates the hidden layers by using Chebyshev polynomial to extend the input space into high dimensions, which shows certain computational advantages compared with the artificial neural network (ANN) structures. Moreover, to update the weights of the CFLSNF, the CFLSNF-LMS is also developed. The stability conditions and computational complexity are studied. Besides, in order to make CFLSNF structure suitable for impulsive noise interference environment, a robust algorithm based on maximum versoria criterion is also proposed. Finally, the validity of the proposed architecture and algorithm are verified by experiments. [ABSTRACT FROM AUTHOR]

Self-healing capability is a critical factor for a resilient distribution system, which requires intelligent agents to automatically perform service restoration online, including network reconfiguration and reactive power dispatch. The article proposes the imitation learning framework for training such an agent, where the agent will interact with an expert built based on the mixed-integer program to learn its optimal policy, and therefore significantly improve the training efficiency compared with exploration-dominant reinforcement learning (RL) methods. This significantly improved training efficiency makes the training problem under $N-k$ scenarios tractable. A hybrid policy network is proposed to handle tie-line operations and reactive power dispatch simultaneously to further improve the restoration performance. The 33-bus and 119-bus systems with $N-k$ disturbances are employed to conduct the training. The results indicate that the proposed method outperforms traditional RL algorithms such as the deep-Q network. [ABSTRACT FROM AUTHOR]

Graph summarization is beneficial in a wide range of applications, such as visualization, interactive and exploratory analysis, approximate query processing, reducing the on-disk storage footprint, and graph processing in modern hardware. However, the bulk of the literature on graph summarization surprisingly overlooks the possibility of having edges of different types. In this article, we study the novel problem of producing summaries of multi-relation networks, i.e., graphs where multiple edges of different types may exist between any pair of nodes. Multi-relation graphs are an expressive model of real-world activities, in which a relation can be a topic in social networks, an interaction type in genetic networks, or a snapshot in temporal graphs. The first approach that we consider for multi-relation graph summarization is a two-step method based on summarizing each relation in isolation, and then aggregating the resulting summaries in some clever way to produce a final unique summary. In doing this, as a side contribution, we provide the first polynomial-time approximation algorithm based on the k-Median clustering for the classic problem of lossless single-relation graph summarization. Then, we demonstrate the shortcomings of these two-step methods, and propose holistic approaches, both approximate and heuristic algorithms, to compute a summary directly for multi-relation graphs. In particular, we prove that the approximation bound of k-Median clustering for the single relation solution can be maintained in a multi-relation graph with proper aggregation operation over adjacency matrices corresponding to its multiple relations. Experimental results and case studies (on co-authorship networks and brain networks) validate the effectiveness and efficiency of the proposed algorithms. [ABSTRACT FROM AUTHOR]

We consider the revenue management problem of finding profit-maximizing prices for delivery time slots in the context of attended home delivery. This multistage optimal control problem admits a dynamic programming (DP) formulation that is intractable for realistic problem sizes due to the so-called “curse of dimensionality.” We therefore study three approximate DP algorithms both from a numerical and control-theoretical perspective. Our analysis is based on real-world data, from which we generate multiple scenarios to stress-test the robustness of the pricing policies to errors in model parameter estimates. Our theoretical analysis and numerical benchmark tests indicate that one of these algorithms, namely gradient-bounded DP, dominates the others with respect to computation time and profit-generation capabilities of the pricing policies that it generates. [ABSTRACT FROM AUTHOR]

Computing the Voronoi diagram of a given set of points in a restricted domain (e.g., inside a 2D polygon, on a 3D surface, or within a volume) has many applications. Although existing algorithms can compute 2D and surface Voronoi diagrams in parallel on graphics hardware, computing clipped Voronoi diagrams within volumes remains a challenge. This article proposes an efficient GPU algorithm to tackle this problem. A preprocessing step discretizes the input volume into a tetrahedral mesh. Then, unlike existing approaches which use the bisecting planes of the Voronoi cells to clip the tetrahedra, we use the four planes of each tetrahedron to clip the Voronoi cells. This strategy drastically simplifies the computation, and as a result, it outperforms state-of-the-art CPU methods up to an order of magnitude. [ABSTRACT FROM AUTHOR]

Evolutionary algorithms (EAs) have been recognized as a promising approach for bilevel optimization. However, the population-based characteristic of EAs largely influences their efficiency and effectiveness due to the nested structure of the two levels of optimization problems. In this article, we propose a transfer learning-based parallel EA (TLEA) framework for bilevel optimization. In this framework, the task of optimizing a set of lower level problems parameterized by upper level variables is conducted in a parallel manner. In the meanwhile, a transfer learning strategy is developed to improve the effectiveness of each lower level search (LLS) process. In practice, we implement two versions of the TLEA: the first version uses the covariance matrix adaptation evolutionary strategy and the second version uses the differential evolution as the evolutionary operator in lower level optimization. The experimental studies on two sets of widely used bilevel optimization benchmark problems are conducted, and the performance of the two TLEA implementations is compared to that of four well-established evolutionary bilevel optimization algorithms to verify the effectiveness and efficiency of the proposed algorithm framework. [ABSTRACT FROM AUTHOR]

As one of the most significant applications of nanopositioning technology, the tremendous development of atomic force microscopes (AFMs) has been witnessed these years. Essentially, the scanning motions of AFMs are generally driven by piezoelectric tube scanners (PTSs), whose cross-coupling effect hinders their high speed and high-precision positioning. Therefore, it becomes an urgent yet challenging mission to establish a niche model for the nonlinear cross-coupling dynamics of the PTS. As an emergent pure data-driven learning approach, the Koopman operator sheds some light on the PTS modeling methodology, which is thus adopted in this article to approximate the nonlinear cross-coupling dynamics of PTSs in an infinite-dimensional space. Moreover, an online high-order extended dynamic mode decomposition algorithm is proposed for the finite-dimensional approximation of the Koopman operator online. The merit of the present model lies in updating the identified cross coupling upon the arrival of new data in an incremental way. Finally, experiments are conducted to approximate the X–Y axes cross coupling of PTSs of an NTMDT Prima AFM, which verifies the effectiveness and superiority of the proposed modeling algorithm. This article is expected to pave the way from the Koopman operator learning theory to real applications in dynamics modeling of abundant nanoscale measurement systems. [ABSTRACT FROM AUTHOR]

In Network Function Virtualization (NFV), network functions are implemented as Virtual Network Functions (VNFs), that are software instances running on physical servers or network devices. In this letter, first, the problem of multicast service chain embedding on NFV-enabled substrate networks is formulated as Integer Linear Programming (ILP). Then, an approach based on Source-Destination-VNF (SDV) graph named Two-Stage SDV-based (TSDV) is proposed to solve the problem in a simple but sufficiently efficient way. This approach offers a trade-off between efficiency and complexity of the solution by decomposing the solution into two stages and by using SDV graph. At the first stage, the proper locations for deploying VNFs are determined, while at the second stage, the multicast routing tree is obtained by solving a simplified Linear Programming (LP) problem. The simulation results show that TSDV offers a good trade-off between efficiency and complexity as compared to other multi-stage methods. [ABSTRACT FROM AUTHOR]

We suggest a new optimization technique for minimizing the sum $\sum _{i=1}^n g_i(x)$ ∑ i = 1 n g i (x) of $n$ n non-convex real functions that satisfy a property that we call piecewise log-Lipschitz. This is by forging links between techniques in computational geometry, combinatorics and convex optimization. As an example application, we provide the first constant-factor approximation algorithms whose running-times are polynomial in $n$ n for the fundamental problem of Points-to-Lines alignment: Given $n$ n points $p_1,\ldots,p_n$ p 1 ,... , p n and $n$ n lines $\ell _1,\ldots,\ell _n$ ℓ 1 ,... , ℓ n on the plane and $z>0$ z > 0 , compute the matching $\pi :[n]\to [n]$ π : [ n ] → [ n ] and alignment (rotation matrix $R$ R and translation vector $t$ t ) that minimize the sum of euclidean distances $\sum _{i=1}^n \mathrm{dist}(Rp_i-t,\ell _{\pi (i)})^z$ ∑ i = 1 n dist (R p i - t , ℓ π (i)) z between each point to its corresponding line. This problem is non-trivial even if $z=1$ z = 1 and the matching $\pi$ π is given. If $\pi$ π is given, our algorithms run in $O(n^3)$ O (n 3) time, and even near-linear in $n$ n using core-sets that support: streaming, dynamic, and distributed parallel computations in poly-logarithmic update time. Generalizations for handling e.g., outliers or pseudo-distances such as $M$ M -estimators for the problem are also provided. Experimental results and open source code show that our algorithms improve existing heuristics also in practice. A companion demonstration video in the context of Augmented Reality shows how such algorithms may be used in real-time systems. [ABSTRACT FROM AUTHOR]

Piecewise Linear Approximation (PLA) is one of the most widely used approaches for representing a time series with a set of approximated line segments. With this compressed form of representation, many large complicated time series can be efficiently stored, transmitted and analyzed. In this article, with the introduced concept of “semi-connection” that allowing two representation lines to be connected at a point between two consecutive time stamps, we propose a new optimal linear-time PLA algorithm SemiOptConnAlg for generating the least number of semi-connected line segments with guaranteed maximum error bound. With extended experimental tests, we demonstrate that the proposed algorithm is very efficient in execution time and achieves better performances than the state-of-art solutions. [ABSTRACT FROM AUTHOR]

Recent research has revealed new and unexpected applications of network control science within biomedicine, pharmacology, and medical therapeutics. These new insights and new applications generated in turn a rediscovery of some old, unresolved algorithmic problems. One of these problems is the Structural Target Control optimization problem, known in previous literature also as Structural Output Controllability problem, which is defined as follows. Given a directed network and a target subset of nodes, the task is to select a small (or the smallest) set of nodes from which the target can be independently controlled, i.e., there exists a set of paths from the selected set of nodes (called driver nodes) to the target nodes such that no two paths intersect at the same distance from their targets. Recently, Structural Target Control optimization problem has been shown to be NP-hard, and several heuristic algorithms were introduced and analyzed, both on randomly generated networks, and on biomedical ones. In this paper, we show that the Structural Target Controllability problem is fixed parameter tractable when parameterized by the number of target nodes. We also prove that the problem is hard to approximate at a factor better than O(log n). Taking into consideration the real case formulations of this problem we identify two more parameters which are naturally constrained by smaller bounds: the maximal length of a controlling path and the size of the set of nodes from which the control can start. With these new parameters we provide an approximation algorithm which is of exponential complexity in the size of the set of nodes from which the control can start and polynomial in all the other parameters. [ABSTRACT FROM AUTHOR]

Security is a key problem for the transmission, interchange, and storage process of multimedia systems and applications. In 2018, Li et al. proposed in-depth security analysis on an image encryption algorithm based on a first-order time-delay system (IEATD) and gave a specific chosen-plaintext attack on it. Moreover, an enhanced version called as IEACD was designed to fix the reported security defects. This article analyzes the essential structures of the two algorithms and evaluates their real security performances: 1) no efficient nonlinear operations are adopted to assure the sensibility of keystream; 2) the equivalent secret key of IEATD can be efficiently recovered from one known plain-image and the corresponding cipher-image; and 3) IEACD can still be efficiently cracked with a chosen-plaintext attack. Both rigorous theoretical analyses and detailed experimental results are provided to demonstrate effectiveness of the advanced cryptanalytic methods. [ABSTRACT FROM AUTHOR]

The energy management (EM) of active distribution network (ADN) under uncertainties is a stochastic, nonconvex and nonlinear problem, which cannot be solved by traditional algorithms in acceptable time. In this paper, we decouple this computationally intractable problem into a series of subproblems which are easier to handle, and then solve them successively according to an improved approximate dynamic programming (IADP) algorithm. Different from the existing approximate dynamic programming (ADP) algorithms, which need to update value functions iteratively, IADP obtains approximate value functions directly using Galerkin method. Such that the time of updating approximate value functions can be omitted. Furthermore, the influence of each basis function on the approximate value function is evaluated according to the absolute value inequality principle. Then the unimportant basis functions are removed from the basis function set to speed up the algorithm. The historical data can also be embedded into IADP to facilitate the online decision-making and reduce the dependency of real-time forecast information. Numerical simulations on two modified IEEE test systems and a real 682-bus ADN are given to illustrate the effectiveness of the proposed approach. [ABSTRACT FROM AUTHOR]

Aggregate nearest neighbor (Ann) query in both the euclidean space and road networks has been extensively studied, and the flexible aggregate nearest neighbor (Fann) problem further generalizes Ann by introducing an extra flexibility parameter $\phi$ ϕ that ranges in $(0, 1]$ (0 , 1 ] . In this article, we focus on Fann on road networks, denoted as Fann $_\mathcal {R}$ R , and its keyword-aware variant, denoted as KFann $_\mathcal {R}$ R . To solve these problems, we propose a series of universal (i.e., suitable for both max and sum) algorithms, including a Dijkstra-based algorithm that enumerates $P$ P instead of $\phi |Q|$ ϕ | Q | -combinations of $Q$ Q , a queue-based approach that processes data points from-near-to-far, and a framework that combines incremental euclidean restriction (IER) and $k$ k NN. We also propose a specific exact solution to max-Fann $_\mathcal {R}$ R and a constant-factor ratio approximate solution to sum-Fann $_\mathcal {R}$ R . These specific algorithms are easy to implement and can achieve excellent performance in some scenarios. Besides, we further extend this problem to top- $k$ k and multiple Fann $_\mathcal {R}$ R (resp., KFann $_\mathcal {R}$ R ) queries. We conduct a comprehensive experimental evaluation for the proposed algorithms on real datasets to demonstrate their superior efficiency and high quality. [ABSTRACT FROM AUTHOR]

Measuring similarity among data objects is important in data analysis and mining. SimRank is a popular link-based similarity measurement among nodes in a graph. To compute the all-pairs SimRank matrix accurately, iterative methods are usually used. For static graphs, current iterative solutions are not efficient enough, both in time and space, due to the unnecessary cost and storage by the nature of iterative updating. For dynamic graphs, all current incremental solutions for updating the SimRank matrix are based on an approximated SimRank definition, and thus have no accuracy guarantee. In this paper, we propose a novel local push based algorithm for computing and tracking all-pairs SimRank. Furthermore, we develop an iterative parallel two-step framework for local push to take advantage of modern hardwares with multicore CPUs. We show that our algorithms outperform the state-of-the-art methods. [ABSTRACT FROM AUTHOR]

The minimum dominating set (MDS) of the network is a node subset of smallest size that every node in the network is either in this subset or is adjacent to one or more nodes of this subset. MDS has found wide applications, ranging from network monitoring, routing, to epidemic control, and text processing. However, the majority of existing studies on MDS problem are confined to single networks. In real world, more and more complex systems consist of a set of elements linked up by different types of connections, which are best modeled as multiplex networks with interacting network layers. Though vastly important, the MDS of the multiplex networks has not yet been formally defined and its application and identification remain open issues. In this article, we present the definition of the MDS of the multiplex network and show some of its possible applications. For solving the MDS problem of the multiplex network, we built a spin-glass model and solve it through the belief-propagation (BP) equations under the replica symmetry mean-field theory. As a consequence, we can predict the relative size of the MDS of the multiplex network theoretically and we can propose a BP-guided decimation algorithm to construct an approximate optimal dominating set in practice. Then the algorithm is improved in both accuracy and efficiency by embedding a novel multiplex network-oriented leaf-removal strategy. The effectiveness of the proposed algorithms is finally verified by comparing with other methods on a number of the multiplex network examples. [ABSTRACT FROM AUTHOR]

Mobile edge computing becomes a promising technology to mitigate the latency of various cloud services. In addition, network function virtualization (NFV) has been shown a great potential in reducing the operational cost of cloud services while enhancing the flexibility of virtual network function deployments, by implementing dedicated hardware network functions as pieces of software in generic servers. Recently, the GPU acceleration has been investigated to speed up flow processing in virtual network functions (VNFs), by leveraging the parallelism of GPUs. VNFs that need accelerations prefer to stay at cloudlets (locations) equipped with GPUs. However, little attention has been paid for the VNF placement that takes into account GPU-affinity in cloudlets of mobile edge clouds. In this paper, we consider the affinity-aware throughput maximization problem in a mobile edge cloud via leveraging the parallelism on GPUs for user requests with VNF requirements. We consider two types of affinities in the VNF placement: The soft-affinity that allows VNFs to be executed by either CPUs or GPUs in cloudlets; and the hard-affinity that only allows VNFs to be placed to the GPUs of a specified set of cloudlets. We formulate two corresponding VNF placement problems in a mobile edge cloud. Specifically, we first propose an exact solution to the soft-affinity throughput maximization problem by formulating an Integer Linear Program (ILP). We then propose an efficient algorithm for the problem, by proposing a randomized algorithm with a provable approximation ratio for the hard-affinity-aware throughput maximization problem and extending the proposed approximation algorithm to the soft-affinity throughput maximization problem. Furthermore, assuming that user requests arrive into the mobile edge cloud one by one without the knowledge of future arrivals, we devise an online algorithm with a good competitive ratio for this dynamic hard-affinity-aware throughput maximization problem. Finally, we evaluate the performance of the proposed algorithms, through simulations and implementations in a real test-bed. Experimental results show that the performance of the proposed algorithms outperform their existing counterparts and achieve higher throughput. [ABSTRACT FROM AUTHOR]

This article investigates the design of self-triggered controllers for networked control systems (NCSs), where the dynamics of the plant are unknown a priori. To deal with the unknown transition dynamics, we employ the Gaussian process (GP) regression in order to learn the dynamics of the plant. To design the self-triggered controller, we formulate an optimal control problem, such that the optimal control and communication policies can be jointly designed based on the GP model of the plant. Moreover, we provide an overall implementation algorithm that jointly learns the dynamics of the plant and the self-triggered controller based on a reinforcement learning framework. Finally, a numerical simulation illustrates the effectiveness of the proposed approach. [ABSTRACT FROM AUTHOR]

This article presents a distributed consensus-based successive convex approximation (DSCA) algorithm to solve nonconvex nondifferentiable economic dispatch (ED) problems. The ED model formulated incorporates generation constraints, valve-point effects, and multiple fuel types. A perturbation technique enables the proposed DSCA to tackle such a nondifferentiable and nonconvex optimization, which paves the way to solving more complicated optimization problems that occur in practical applications. The local generation constraint is taken care by a local surrogate convex optimization directly. The global equality constraint is handled based on a consensus protocol, where the local generation–demand mismatch among all dispatchable generators (DGs) is shared in a distributed manner. As a result, the power distribution of DGs is updated, and the generation cost is minimized. Several case studies show that the proposed DSCA algorithm can achieve superior ED solutions and computational efficiency over existing nonconvex optimization algorithms. [ABSTRACT FROM AUTHOR]

The study of Service Function Chains (SFCs) placement problem is crucial to support services flexibly and use resources efficiently. Solutions should satisfy various Quality of Service requirements, avoid edge resource congestion, and improve service acceptance ratio (SAR). This work presents a novel approach to address these challenges by solving a multi-objective SFCs placement problem based on the Pointer Network in multi-layer edge and cloud networks. We design a Deep Reinforcement Learning algorithm, called Chebyshev-assisted Actor-Critic SFCs Placement Algorithm, to overcome the limitations of traditional heuristic and evolutionary algorithms. Then, we run this algorithm iteratively with a set of weights to obtain non-dominated fronts, which have much higher hypervolume values than those obtained from other state-of-the-art algorithms. Moreover, running our algorithm individually with selected weights from non-dominated fronts can avoid edge resource congestion and achieve 98% SARs of low-latency services during high-workload periods. Finally, based on both simulation and real testbed experimental results, it is validated that the proposed algorithm fits for pragmatic service deployment while achieving 100% of SARs in the use cases deployed on the testbed. [ABSTRACT FROM AUTHOR]

The fast development of high-performance and flexible SmartNICs and programmable data plane switches (PDP-SWs) has motivated people to consider the deployment of virtual network functions (vNFs) on them. Hence, together with traditional virtual machines (VMs), SmartNICs and PDP-SWs form heterogeneous network function virtualization (NFV) platforms for realizing vNF service chains (vNF-SCs). In this work, we consider the transition from software-based homogeneous NFV platforms to the heterogeneous ones, and study how to optimize the service upgrade of vNF-SCs. Specifically, the service upgrade is divided into two steps, which are 1) selecting servers/switches in the substrate network (SNT) to upgrade, which is done by adding SmartNICs to servers and replacing traditional switches with PDP-SWs, under a fixed budget, and 2) redeploying the existing vNF-SCs in the updated SNT to maximize the quality-of-service (QoS) improvement on latency reductions. We first formulate an integer linear programming (ILP) model to optimize the overall service upgrade, then design two correlated optimizations for its two steps, and finally propose polynomial-time approximation algorithms to solve the optimizations. The results of extensive simulations confirm that our proposed algorithm outperforms the existing benchmarks in various network scenarios, and achieves better tradeoff between performance and time-efficiency. [ABSTRACT FROM AUTHOR]

Path tracking control of intelligent vehicles has to deal with the difficulties of model uncertainties and nonlinearities. As a class of adaptive optimal control methods, reinforcement learning (RL) has received increasing attention in solving difficult control problems. However, feature representation and online learning ability are two major problems to be solved for learning control of uncertain dynamic systems. In this article, we propose a multi-kernel online RL approach for path tracking control of intelligent vehicles. In the proposed approach, a multiple kernel feature learning framework is designed for online learning control based on dual heuristic programming (DHP) and the new online learning control algorithm is called multi-kernel DHP (MKDHP). In MKDHP, instead of the expert knowledge for selecting and fine-tuning of a suitable kernel function, only a set of basic kernel functions is required to be predefined and the multi-kernel features can be learned for value function approximation in the critic. The simulation studies on path tracking control for intelligent vehicles have been conducted under $S$ -curve and urban road conditions. The results demonstrated that compared with other typical path tracking controllers for intelligent vehicles, such as the linear quadratic regulator (LQR), the pure pursuit controller and the ribbon-based controller, the proposed multi-kernel learning controller can achieve better performance in terms of tracking precision and smoothness. [ABSTRACT FROM AUTHOR]

In a paced aircraft final assembly line, some disturbances can be collected timely on the basis of the cyber-physical production system. In order to reduce the execution deviation, some workers need to switch among stations after a fixed period. Thus, a worker allocation problem with the multistage workstation is introduced first. Then, an integer programming formulation is presented to formulate the problem with the objective of shortest workstation cycle and the workload balance of both stations and workers. Moreover, a modified nondominated sorting genetic algorithm (NSGA-IV) is proposed to solve it, which tradeoff the convergence and the population diversity in the decision space. Finally, the NSGA-IV algorithm compares with five multiobjective evolutionary algorithms in a real-world case. Compared with manual allocation, the takt time of an aircraft final assembly line is reduced by 20.86% by using the NSGA-IV algorithm. [ABSTRACT FROM AUTHOR]

Due to line-of-sight communication links and distributed deployment, Unmanned Aerial Vehicles (UAVs) have attracted substantial interest in agile Mobile Edge Computing (MEC) service provision. In this paper, by clustering multiple users into independent communities based on their geographic locations, we design a 5G-enabled UAV-to-community offloading system. A system throughput maximization problem is formulated, subjected to the transmission rate, atomicity of tasks and speed of UAVs. By relaxing the transmission rate constraint, the mixed integer non-linear program is transformed into two subproblems. We first develop an average throughput maximization-based auction algorithm to determine the trajectory of UAVs, where a community-based latency approximation algorithm is developed to regulate the designed auction bidding. Then, a dynamic task admission algorithm is proposed to solve the task scheduling subproblem within one community. Performance analyses demonstrate that our designed auction bidding can guarantee user truthfulness, and can be fulfilled in polynomial time. Extensive simulations based on real-world data in health monitoring and online YouTube video services show that our proposed algorithm is able to maximize the system throughput while guaranteeing the fraction of served users. [ABSTRACT FROM AUTHOR]

This article investigates the optimal control problem for nonlinear nonzero-sum differential game in the environment of no initial admissible policies while considering the control constraint. An adaptive learning algorithm is thus developed based on policy iteration technique to approximately obtain the Nash equilibrium using real-time data. A two-player continuous-time system is used to present this approximate mechanism, which is implemented as a critic–actor architecture for every player. The constraint is incorporated into this optimization by introducing the nonquadratic value function, and the associated constrained Hamilton–Jacobi equation is derived. The critic neural network (NN) and actor NN are utilized to learn the value function and the optimal control policy, respectively, in the light of novel weight tuning laws. In order to tackle the stability during the learning phase, two stable operators are designed for two actors. The proposed algorithm is proved to be convergent as a Newton’s iteration, and the stability of this closed-loop system is also ensured by Lyapunov analysis. Finally, two simulation examples demonstrate the effectiveness of the proposed learning scheme by considering different constraint scenes. [ABSTRACT FROM AUTHOR]

In this paper, we study an optimal user scheduling with minimum beam alignment overhead in millimeter wave networks. The problem is posed as constrained Markov decision process (CMDP) with the goal of minimizing the average beam alignment overhead subject to the average rate constraint on each user. Under a certain assumption on the rate function of the users, by using a structural result derived from the Lagrangian formulation of the CMDP, we show that the optimal policy should keep scheduling the users that are scheduled in the previous time slot unless an abrupt change in the beam direction occurs. Using this result, the complexity of the problem decreases to polynomial in the number of users. In addition, we provide a heuristic deterministic algorithm that achieves $({1}+\epsilon)$ approximation of the optimal solution, with smaller $\epsilon $ at the cost of longer transmission interval of each user. Lastly, to deal with the case where the assumption on the rate function does not hold due to beam conflicts between the users, we consider a system model that accounts for an angular channel information. A new CMDP is formulated for the problem and a heuristic algorithm based on the age information is proposed. [ABSTRACT FROM AUTHOR]

Wireless Sensor Networks (WSNs) lend themselves to a wide variety of applications in our daily lives, such as environmental monitoring, safety, health-care, animal monitoring, etc. However, one of the key issues in WSN is energy constraints. This makes energy-conservation one of the major keys to the efficient functioning and lifetime of WSN. In this paper, given a network of nodes with heterogeneous energy, our goal is to determine energy-aware disjoint dominating sets (DSs) that work as data collection nodes in each round, to improve overall WSN lifetime. In order to accomplish this goal, we propose an intelligent data collection technique with two phases, the collector nodes selection, and the data gathering path formation and collection phases. In the collector nodes selection phase, an energy-aware algorithm based on swarm intelligence is proposed to construct disjoint dominating sets that work as collector nodes in each round. In the data gathering path formation and collection phase, data gathering path is determined for achieving maximal data collection efficiency and reduced energy consumption. The efficiency of our proposed technique is proved mathematically and through simulations. [ABSTRACT FROM AUTHOR]

When modeling decision-making in autonomous vehicles (AVs), only a fraction of the required information is usually available at the start due to the presence of uncertainty in the knowledge of the state of the system and the environment. This article presents a probabilistic modeling framework based on a combination of partially observable Markov decision-process (POMDP) models and heuristics. In this article, POMDPs are expanded and redefined as expandable-POMDPs to account for uncertainty and unexplainable observations. Specifically, this approach incorporates new hidden states in the model and expands associated probability distributions in the model to account for partial knowledge and unexplainable observations. An online policy estimation algorithm is presented. This algorithm employs heuristic search combined with distance-based clustering to estimate long-term rewards in a finite-horizon look-ahead scheme for expandable-POMDPs. Specifically, heuristics are employed in model design and online policy evaluation to circumvent state-space explosion and reduce high computational complexity. Finally, the expandable-POMDP models are employed for designing multiple context-specific models for tactical planning and decision-making by AVs in simulated scenarios characterized by partial observability and uncertainty. One (or more) expandable-POMDP model is invoked when the contextual pattern of the ongoing scenario fits the objective of the tactical planning model. [ABSTRACT FROM AUTHOR]

In a software defined network, the controller needs to obtain/collect traffic measurement information (i.e., flow statistics) from switches for different applications, such as traffic engineering. Existing solutions seldom consider the per-switch cost, which may lead to heavy statistics collection cost (e.g., high CPU overhead) on some switches. Due to limited computing power on most commodity switches, heavy statistics collection cost on those switches may seriously interfere with the basic rule operations, especially when some switches need to deal with many new-arrival flows or update routes of existing flows. To address this challenge, we design and implement efficient flow statistics collection (FSC) with limited interference on the basic rule operations. We formally propose a cooperative flow statistics collection with per-switch cost constraint (CP-FSC) problem. We prove that the CP-FSC problem is NP-hard and present an efficient algorithm with approximation ratio 1/2, based on dynamic programming. To reduce the time complexity, a greedy-based algorithm with approximation ratio 1/3 is also presented. We implement the proposed FSC algorithms on our SDN platform. The experimental results and the extensive simulation results show 36%-59% performance improvement compared with the existing solutions. [ABSTRACT FROM AUTHOR]

We consider a conflict-free minimum latency data aggregation problem that occurs in different wireless networks. Given a network that is presented as an undirected graph with one selected vertex (a sink), the goal is to find a spanning aggregation tree rooted in the sink and to define a conflict-free aggregation minimum length schedule along the arcs of the tree directed to the sink. Herewith, at the same time slot, each element of the network can either send or receive at most one message. Only one message should be sent by each network element during the whole aggregation session, and the conflicts caused by signal interference should be excluded. This problem is NP-hard and remains NP-hard even in the case when the aggregation tree is given. Therefore, the development of efficient approximation algorithms is very important for this problem. In this paper, we present new heuristic algorithms based on genetic local search and variable neighbourhood search metaheuristics. We conducted an extensive simulation that demonstrates the superiority of our algorithms compared with the best of the previous approaches. [ABSTRACT FROM AUTHOR]

The capacitated vehicle routing problem (CVRP) has been extensively investigated in the past years due to their applications in a variety of real-world scenarios. However, it is still very challenging for most existing algorithms to tackle large-scale CVRPs (LSCVRPs), namely, CVRPs with hundreds or thousands of customers. In this article, we propose a heuristic algorithm, called EMRG-HA, to address LSCVRPs based on the framework of divide and conquer, where an evolutionary multiobjective route grouping (EMRG) method is suggested to decompose an LSCVRP into small subcomponents. The suggested EMRG adopts a multiobjective evolutionary algorithm for route grouping by simultaneously optimizing three well-defined objectives, intragroup distance, intergroup distance, and intergroup balance in size, which can obtain a set of promising decompositions of LSCVRPs. Based on the EMRG, a local search method is suggested to improve the quality of routes in groups, where only routes in one group instead of in all groups are improved which is determined according to the average serving cost of routes in each group. The performance of the proposed EMRG-HA is verified on 42 test instances from three popular benchmark suites. The experimental results show that the EMRG-HA is superior over eight existing algorithms on most test instances of LSCVRPs, in terms of both computational efficiency and solution quality. [ABSTRACT FROM AUTHOR]

Since the late 1980s, temporal difference (TD) learning has dominated the research area of policy evaluation algorithms. However, the demand for the avoidance of TD defects, such as low data-efficiency and divergence in off-policy learning, has inspired the studies of a large number of novel TD-based approaches. Gradient-based and least-squares-based algorithms comprise the major part of these new approaches. This paper aims to combine advantages of these two categories to derive an efficient policy evaluation algorithm with ${O}$ (${n} ^{ {2}}$) per-time-step runtime complexity. The least-squares-based framework is adopted, and the gradient correction is used to improve convergence performance. This paper begins with the revision of a previous ${O}$ (${n} ^{ {3}}$) batch algorithm, least-squares TD with a gradient correction (LS-TDC) to regularize the parameter vector. Based on the recursive least-squares technique, an ${O}$ (${n} ^{ {2}}$) counterpart of LS-TDC called RC is proposed. To increase data efficiency, we generalize RC with eligibility traces. An off-policy extension is also proposed based on importance sampling. In addition, the convergence analysis for RC as well as LS-TDC is given. The empirical results in both on-policy and off-policy benchmarks show that RC has a higher estimation accuracy than that of RLSTD and a significantly lower runtime complexity than that of LSTDC. [ABSTRACT FROM AUTHOR]

Radio access network (RAN) slicing is a virtualization technology that partitions radio resources into multiple autonomous virtual networks. Since RAN slicing can be tailored to provide diverse performance requirements, it will be pivotal to achieve the high-throughput and low-latency communications that next-generation (5G) systems have long yearned for. To this end, effective RAN slicing algorithms must (i) partition radio resources so as to leverage coordination among multiple base stations and thus boost network throughput; and (ii) reduce interference across different slices to guarantee slice isolation and avoid performance degradation. The ultimate goal of this paper is to design RAN slicing algorithms that address the above two requirements. First, we show that the RAN slicing problem can be formulated as a 0–1 Quadratic Programming problem, and we prove its NP-hardness. Second, we propose an optimal solution for small-scale 5G network deployments, and we present three approximation algorithms to make the optimization problem tractable when the network size increases. We first analyze the performance of our algorithms through simulations, and then demonstrate their performance through experiments on a standard-compliant LTE testbed with 2 base stations and 6 smartphones. Our results show that not only do our algorithms efficiently partition RAN resources, but also improve network throughput by 27% and increase by 2× the signal-to-interference-plus-noise ratio. [ABSTRACT FROM AUTHOR]

Jobs in modern computing clusters have highly diverse processing duration and heterogeneous resource requirements. In this paper, we consider the problem of job scheduling for a computing cluster comprised of multiple servers with heterogeneous computation resources, while taking the different resource demands of the jobs into account. Our focus is to achieve a low overall job response time for the system (which is also referred to as the job flowtime) while providing fairness between small and large jobs. Since the job flowtime minimization problem under multiple (even homogeneous) servers are known to be NP-hard, we propose an approximation algorithm to tackle the original online scheduling problem by adopting the recently-proposed notion of fractional job flowtime as a surrogate objective for minimization. For the general online job arrival case with multi-dimensional resource requirements, we apply Online Convex Optimization (OCO) techniques to design the corresponding scheduling algorithm with performance guarantees. In the single-dimensional resource setting, we show that the dynamic fit of the online version of our approximate algorithm grows only sublinearly with respect to time and derive a bound for its dynamic regret when comparing to its offline counterpart. While the baseline version of our proposed scheduling algorithm assumes the possibilities of job preemption and job migration across different servers, we show that the extent of job preemption and migration can be well controlled by augmenting the objective function with the corresponding switching costs. [ABSTRACT FROM AUTHOR]

Spatial crowdsourcing, a human-centric compelling paradigm in performing spatial tasks, has drawn rising attention. Task assignment is of paramount importance in spatial crowdsourcing. Existing studies often use heuristics of various kinds to solve task assignment problems. These schemes usually only apply some specific cases, once the environment changes, the efficiency of the algorithms is significantly reduced. In this paper, we first introduce a taxonomy of task assignment in spatial crowdsourcing. Next, we design an approximation algorithm and get an efficient solution for the important problem, namely, Bounded and Heterogeneous Task Assignment (BHTA), such that the sum of the rewards of workers is maximized subject to multiple constraints. We prove that the BHTA problem is NP-hard. Subsequently, we propose a constant-ratio approximation algorithm based on partition and shifting method to achieve the assignment solution. To meet with the workers’ dynamism, we further devise a greedy algorithm and provide theoretical guarantee. Experiments on synthetic and real datasets demonstrate the efficiency of our strategy over previous methods. So far as we know, this paper is the first attempt to give a constant-ratio approximation for such task assignment problems in spatial crowdsourcing. [ABSTRACT FROM AUTHOR]

This paper proposes Bayes-optimal convolutional approximate message-passing (CAMP) for signal recovery in compressed sensing. CAMP uses the same low-complexity matched filter (MF) for interference suppression as approximate message-passing (AMP). To improve the convergence property of AMP for ill-conditioned sensing matrices, the so-called Onsager correction term in AMP is replaced by a convolution of all preceding messages. The tap coefficients in the convolution are determined so as to realize asymptotic Gaussianity of estimation errors via state evolution (SE) under the assumption of orthogonally invariant sensing matrices. An SE equation is derived to optimize the sequence of denoisers in CAMP. The optimized CAMP is proved to be Bayes-optimal for all orthogonally invariant sensing matrices if the SE equation converges to a fixed-point and if the fixed-point is unique. For sensing matrices with low-to-moderate condition numbers, CAMP can achieve the same performance as high-complexity orthogonal/vector AMP that requires the linear minimum mean-square error (LMMSE) filter instead of the MF. [ABSTRACT FROM AUTHOR]

In the past decades, continuous Doppler radar sensor-based biosignal detections have attracted many research interests. A typical example is the Doppler heartbeat detection. While significant progresses have been achieved, reliable, time-domain accurate demodulation of biosignals in the presence of unavoidable direct current (dc) offsets remains a technical challenge. Aiming to overcome this difficulty, we propose in this article a novel demodulation algorithm that does not need to trace and eliminate dynamic dc offsets based on approximating segmented arcs in a quadrature constellation of sampling data to directional chords. Assisted by the principal component analysis, such chords and their directions can be deterministically determined. Simulations and experimental validations showed full recovery of micrometer-level pendulum movements and strongly noised human heartbeats, verifying the effectiveness and accuracy of the proposed approach. [ABSTRACT FROM AUTHOR]

For strapdown inertial navigation systems (SINSs) equipped with high-precision fiber optic gyroscope whose outputs are angular rate signals, the attitude calculation accuracies of traditional angular-rate-based rotation vector algorithms are limited when the vehicle is in a highly dynamic environment due to the fact that only the compensation of the second-order noncommutativity error is considered. Although the attitude algorithms based on polynomial iteration have higher accuracy, the computational complexity is too large. In order to fully tap the accuracy of the inertial measurement unit (IMU) to reduce the attitude errors, the third-, fourth-, and fifth-order Picard solutions for the equivalent rotation vector differential equation are derived in this article. A new method with a compressed structure to calculate the rotation vector for real-time processing systems is proposed to further reduce the noncommutativity error. In a classical coning motion environment, the frequency-series-based Taylor expansions are utilized for error analysis and design of the new algorithm’s coefficients. The effectiveness of the proposed coning algorithm with eighth-order accuracy is validated by digital simulation and initial alignment experiments in the turntable. In comparison with the traditional algorithms, the proposed algorithm improves the yaw alignment accuracy by 78.5%, the pitch alignment accuracy by 73.8%, and the roll alignment accuracy by 66.9% on average. [ABSTRACT FROM AUTHOR]

Millimeter wave (mmWave) communications and cognitive radio technologies constitute key technologies of improving the spectral efficiency of communications. Hence, we conceive a hybrid secure precoder for enhancing the physical layer security of a cognitive mmWave wiretap channel, where a secondary transmitter broadcasts confidential information signals to multiple secondary users under the interference temperature constraint of the primary user (PU). The optimization problem is formulated as jointly optimizing the analog and digital precoder for maximizing the minimum secrecy rate of all the secondary users under practical constraints. In particular, our design satisfies the constraint on the maximum interference power received by multiple PUs, as well as the secondary users’ minimum quality-of-service (Qos), and the unit-modulus constraint on the analog precoder. Due to the non-convexity of the resultant objective function and owing to the coupling between the analog and digital precoder, the optimization problem formulated is nonconvex and nonlinear, hence it is very challenging to solve directly. Hence, we first transform it into a tractable form, and develop a penalty dual decomposition (PDD) based iterative algorithm to locate its Karush-Kuhn-Tucker (KKT) solution. Finally, we generalize the proposed PDD algorithm to a secure hybrid precoder design relying on practical finite-resolution phase shifters and show that the proposed PDD algorithm can be straightforwardly adapted to handle the scenario, where each PU is equipped with multiple antennas and the CSI of multiple eavesdroppers (Eves) is imperfectly known. Our simulation results validate the efficiency of the proposed iterative algorithm. [ABSTRACT FROM AUTHOR]

As a class of batch-mode reinforcement learning (RL) methods for Markov decision problems with large or continuous state spaces, approximate policy iteration (API) has received increasing attention in the past decades. One open problem in the design of API algorithms is how to construct the basis functions or features for value function approximation (VFA). In this paper, we propose a novel batch-mode RL approach with randomly projected features for VFA. The proposed approach can be viewed as an extension of extreme learning machines (ELMs) to RL problems so it can be called ELM-API. The ELMs have been popularly studied in supervised learning problems, but there is not much work on the extension of ELMs to learning control problems. The proposed approach has advantages over the previous API algorithms in that the features for VFA can be quickly generated without complex parameter selection and the performance will be adaptive to different sample sets in batch-mode RL. In particular, the ELM-API approach can realize fast and efficient feature reconstruction when training sample sets are relatively small. Comprehensive simulation studies on two benchmark learning control problems were carried out to test the performance of API algorithms with different feature construction methods. It is shown that the ELM-API algorithm can obtain comparable or better performance than the previous API approaches. To further show the effectiveness of ELM-API in real-world applications, the simulation results on a more challenging high-dimensional lane-changing decision problem in dynamic traffic environment are also reported, which show the capability of the ELM-API algorithm in learning satisfactory lane-changing policies with high data efficiency. [ABSTRACT FROM AUTHOR]