A Gradient-Aware Search Algorithm for Constrained Markov Decision Processes.

The canonical solution methodology for finite constrained Markov decision processes (CMDPs), where the objective is to maximize the expected infinite-horizon discounted rewards subject to the expected infinite-horizon discounted costs' constraints, is based on convex linear programming (LP). In this brief, we first prove that the optimization objective in the dual linear program of a finite CMDP is a piecewise linear convex (PWLC) function with respect to the Lagrange penalty multipliers. Next, we propose a novel, provably optimal, two-level gradient-aware search (GAS) algorithm which exploits the PWLC structure to find the optimal state-value function and Lagrange penalty multipliers of a finite CMDP. The proposed algorithm is applied in two stochastic control problems with constraints for performance comparison with binary search (BS), Lagrangian primal-dual optimization (PDO), and LP. Compared with the benchmark algorithms, it is shown that the proposed GAS algorithm converges to the optimal solution quickly without any hyperparameter tuning. In addition, the convergence speed of the proposed algorithm is not sensitive to the initialization of the Lagrange multipliers.

Node Deployment of Marine Monitoring Networks: A Multiobjective Optimization Scheme.

The increasing demands for real-time marine monitoring call for the wide deployment of Marine Monitoring Networks (MMNs). The low-rate underwater communications over a long distance, long propagation delay of underwater acoustic channel, and high deployment costs of marine sensors in a large-scale three-dimensional space bring great challenges in the network deployment and management of MMN. In this paper, we first propose a multitier, hierarchical network architecture of MMN with the support of edge computing (HMMN-EC) to enable efficient monitoring services in a harsh marine environment, taking into consideration the salient features of marine communications. Specifically, HMMN-EC is composed of three subnetworks, i.e., underwater acoustic subnetwork, the sea-surface wireless subnetwork, and the air wireless subnetwork, with a diversity of network nodes with different capabilities. We then jointly investigate the deployment diverse network nodes with various constraints in different subnetworks of HMMN-EC. To this end, we formulate a Multiobjective Optimization (MO) problem to minimize the network deployment cost while achieving the maximal network lifetime, subject to the limited energy of different marine nodes and the complex deployment environment. To solve the formulated problem, we present an Ant-Colony-based Efficient Topology Optimization (AC-ETO) algorithm to find the optimal locations of nodes in different subnetworks of MMN in a large-scale deployment. The time complexity of the proposed algorithm is also analyzed. Finally, extensive simulations are carried out to validate the superior performance of the proposed algorithm compared with some existing solutions.