Modeling and Design of Real-Time Pricing Systems Based on Markov Decision Processes

A real-time pricing system of electricity is a system that charges different electricity prices for different hours of the day and for different days, and is effective for reducing the peak and flattening the load curve. In this paper, using a Markov decision process (MDP), we propose a modeling method and an optimal control method for real-time pricing systems. First, the outline of real-time pricing systems is explained. Next, a model of a set of customers is derived as a multi-agent MDP. Furthermore, the optimal control problem is formulated, and is reduced to a quadratic programming problem. Finally, a numerical simulation is presented.

Robust analysis of discounted Markov decision processes with uncertain transition probabilities

Optimal policies in Markov decision problems may be quite sensitive with regard to transition probabilities.In practice,some transition probabilities may be uncertain.The goals of the present study are to find the robust range for a certain optimal policy and to obtain value intervals of exact transition probabilities.Our research yields powerful contributions for Markov decision processes(MDPs)with uncertain transition probabilities.We first propose a method for estimating unknown transition probabilities based on maximum likelihood.Since the estimation may be far from accurate,and the highest expected total reward of the MDP may be sensitive to these transition probabilities,we analyze the robustness of an optimal policy and propose an approach for robust analysis.After giving the definition of a robust optimal policy with uncertain transition probabilities represented as sets of numbers,we formulate a model to obtain the optimal policy.Finally,we define the value intervals of the exact transition probabilities and construct models to determine the lower and upper bounds.Numerical examples are given to show the practicability of our methods.

Variance minimization for continuous-time Markov decision processes: two approaches

This paper studies the limit average variance criterion for continuous-time Markov decision processes in Polish spaces. Based on two approaches, this paper proves not only the existence of solutions to the variance minimization optimality equation and the existence of a variance minimal policy that is canonical, but also the existence of solutions to the two variance minimization optimality inequalities and the existence of a variance minimal policy which may not be canonical. An example is given to illustrate all of our conditions.

基于MDP的无人机避撞航迹规划研究

无人机(UAV)进行避撞前提下的目标搜索航迹规划是指在复杂且众多的环境障碍约束中通过合理规划飞行路径,以更快、更高效的形式找到目标;研究了无障碍环境条件下有限位置马尔科夫移动的规律,构建了相应的马尔科夫移动分布模型;在借鉴搜索系统航迹规划的前沿研究成果之上,结合马尔科夫决策过程理论(MDP),引入了负奖励机制对Q-Learning策略算法迭代;类比“风险井”的可视化方式将障碍威胁区域对无人机的负奖励作用直观地呈现出来,构建了复杂障碍约束环境下单无人机目标搜索航迹规划模型,并进行仿真实验证明该算法可行,对航迹规划算法的设计具有一定的参考意义。

Variance Optimization for Continuous-Time Markov Decision Processes

This paper considers the variance optimization problem of average reward in continuous-time Markov decision process (MDP). It is assumed that the state space is countable and the action space is Borel measurable space. The main purpose of this paper is to find the policy with the minimal variance in the deterministic stationary policy space. Unlike the traditional Markov decision process, the cost function in the variance criterion will be affected by future actions. To this end, we convert the variance minimization problem into a standard (MDP) by introducing a concept called pseudo-variance. Further, by giving the policy iterative algorithm of pseudo-variance optimization problem, the optimal policy of the original variance optimization problem is derived, and a sufficient condition for the variance optimal policy is given. Finally, we use an example to illustrate the conclusion of this paper.

Adaptive Strategies for Accelerating the Convergence of Average Cost Markov Decision Processes Using a Moving Average Digital Filter

This paper proposes a technique to accelerate the convergence of the value iteration algorithm applied to discrete average cost Markov decision processes. An adaptive partial information value iteration algorithm is proposed that updates an increasingly accurate approximate version of the original problem with a view to saving computations at the early iterations, when one is typically far from the optimal solution. The proposed algorithm is compared to classical value iteration for a broad set of adaptive parameters and the results suggest that significant computational savings can be obtained, while also ensuring a robust performance with respect to the parameters.

Conditional Value-at-Risk for Random Immediate Reward Variables in Markov Decision Processes

We consider risk minimization problems for Markov decision processes. From a standpoint of making the risk of random reward variable at each time as small as possible, a risk measure is introduced using conditional value-at-risk for random immediate reward variables in Markov decision processes, under whose risk measure criteria the risk-optimal policies are characterized by the optimality equations for the discounted or average case. As an application, the inventory models are considered.

Seeking for Passenger under Dynamic Prices: A Markov Decision Process Approach

In recent years, ride-on-demand (RoD) services such as Uber and Didi are becoming increasingly popular. Different from traditional taxi services, RoD services adopt dynamic pricing mechanisms to manipulate the supply and demand on the road, and such mechanisms improve service capacity and quality. Seeking route recommendation has been widely studied in taxi service. In RoD services, the dynamic price is a new and accurate indicator that represents the supply and demand condition, but it is yet rarely studied in providing clues for drivers to seek for passengers. In this paper, we proposed to incorporate the impacts of dynamic prices as a key factor in recommending seeking routes to drivers. We first showed the importance and need to do that by analyzing real service data. We then designed a Markov Decision Process (MDP) model based on passenger order and car GPS trajectories datasets, and took into account dynamic prices in designing rewards. Results show that our model not only guides drivers to locations with higher prices, but also significantly improves driver revenue. Compared with things with the drivers before using the model, the maximum yield after using it can be increased to 28%.

A dynamical neural network approach for distributionally robust chance-constrained Markov decision process

In this paper,we study the distributionally robust joint chance-constrained Markov decision process.Utilizing the logarithmic transformation technique,we derive its deterministic reformulation with bi-convex terms under the moment-based uncertainty set.To cope with the non-convexity and improve the robustness of the solution,we propose a dynamical neural network approach to solve the reformulated optimization problem.Numerical results on a machine replacement problem demonstrate the efficiency of the proposed dynamical neural network approach when compared with the sequential convex approximation approach.

Heterogeneous Network Selection Optimization Algorithm Based on a Markov Decision Model

A network selection optimization algorithm based on the Markov decision process(MDP)is proposed so that mobile terminals can always connect to the best wireless network in a heterogeneous network environment.Considering the different types of service requirements,the MDP model and its reward function are constructed based on the quality of service(QoS)attribute parameters of the mobile users,and the network attribute weights are calculated by using the analytic hierarchy process(AHP).The network handoff decision condition is designed according to the different types of user services and the time-varying characteristics of the network,and the MDP model is solved by using the genetic algorithm and simulated annealing(GA-SA),thus,users can seamlessly switch to the network with the best long-term expected reward value.Simulation results show that the proposed algorithm has good convergence performance,and can guarantee that users with different service types will obtain satisfactory expected total reward values and have low numbers of network handoffs.

一种基于MDP的最优服务功能链长部署策略

随着网络功能虚拟化技术被越来越多的服务提供商应用,许多增值服务被作为虚拟服务功能部署在云数据中心。然而,如何在频繁转变的网络中部署服务功能,使其动态的部署和分配资源仍然是亟待解决的问题。论文提出了基于马尔可夫决策过程创建服务功能实例的部署方案,有效地应对由节点、链路资源使用及用户请求引起的网络动态转换,通过权衡服务质量和服务提供商收益两个目标来最优化部署的链路长度,能够保证服务质量的同时最大化服务提供商的收益。与其他方案相比,仿真结果验证了所提出方案的有效性,面对大量的用户请求时在系统延迟以及吞吐量方面表现更好。

An Optimized Vertical Handoff Algorithm Based on Markov Process in Vehicle Heterogeneous Network

In order to solve the problem the existing vertical handoff algorithms of vehicle heterogeneous wireless network do not consider the diversification of network's status, an optimized vertical handoff algorithm based on markov process is proposed and discussed in this paper. This algorithm takes into account that the status transformation of available network will affect the quality of service(Qo S) of vehicle terminal's communication service. Firstly, Markov process is used to predict the transformation of wireless network's status after the decision via transition probability. Then the weights of evaluating parameters will be determined by fuzzy logic method. Finally, by comparing the total incomes of each wireless network, including handoff decision incomes, handoff execution incomes and communication service incomes after handoff, the optimal network to handoff will be selected. Simulation results show that: the algorithm proposed, compared to the existing algorithm, is able to receive a higher level of load balancing and effectively improves the average blocking rate, packet loss rate and ping-pang effect.

基于POMDP模型的智能雷达干扰决策方法

为了有效提高复杂电磁环境下对非合作方工作模式未知的智能雷达的干扰效率和准确率,提出了一种基于部分可观测马尔可夫决策过程(partially observable Markov decision process,POMDP)的干扰决策方法。首先,根据智能雷达的工作特点构建了智能雷达对抗系统的POMDP模型,采用非参数的、基于样本的信念分布反映智能体对环境的认知,并利用贝叶斯滤波更新智能体对环境的信念。然后,以信息熵作为评估准则,令干扰机选择信息熵最大的干扰样式不断尝试。最后,通过仿真实验与传统Q-学习法和经验决策法的干扰决策性能进行比较,验证所提方法的优越性。结果表明,所提方法能够根据未知雷达状态变化动态地选择最优干扰方式,且能更快实现对智能雷达的干扰决策。

基于MDP-ADMM的数据中心储能系统优化运行方法

为了缓解数据中心综合运行成本高、电网侧负荷峰谷差大的问题,提出一种基于马尔可夫决策过程与交替方向乘子法结合的数据中心储能系统优化运行方法。首先,分析了数据中心的基本结构,并对数据中心主要设备的功耗特性以及数据中心负荷在时间维度上灵活转移的特性进行分析;其次,考虑数据中心供电可靠性、储能系统充放电功率限制、充放电损耗成本等因素,建立以综合运行成本最小和削峰填谷效果最佳为目标的储能系统优化运行模型;然后,针对模型具有多时段耦合的特点,采用马尔可夫决策过程对其解耦重构,利用交替方向乘子法对重构后的问题进行迭代求解;最后,在MATLAB仿真环境下,对某大型数据中心进行仿真分析,仿真结果验证了所提优化运行方法的有效性与合理性。

考虑光伏电源可靠性的新能源配电网数据驱动无功电压优化控制

充分挖掘分布式光伏电源的无功支撑能力,有助于解决光伏高比例接入带来的配电网电压波动、电压越限以及新能源消纳等问题,但光伏电源无功输出会造成其功率器件结温越限或剧烈波动,严重威胁到光伏电源的可靠运行。为此,提出考虑光伏电源可靠性的新能源配电网数据驱动无功电压优化控制策略。首先,提出一种基于数据驱动的光伏电源可靠性评估方法,该方法采用XGBoost机器学习模型计算IGBT结温,提高了IGBT结温计算效率,避免了评估精度对IGBT参数的依赖;进而建立考虑光伏电源可靠性的配电网无功电压优化模型,将IGBT结温均值和结温波动引入模型优化目标;然后,将该模型进行马尔可夫决策过程转化,并基于深度确定性策略梯度强化学习算法完成智能体训练;最后,通过IEEE33节点系统验证所提策略在无功电压快速优化和光伏电源可靠性提升方面的优势。

Analysis of a POMDP Model for an Optimal Maintenance Problem with Multiple Imperfect Repairs

I consider a system whose deterioration follows a discrete-time and discrete-state Markov chain with an absorbing state. When the system is put into practice, I may select operation (wait), imperfect repair, or replacement at each discrete-time point. The true state of the system is not known when it is operated. Instead, the system is monitored after operation and some incomplete information concerned with the deterioration is obtained for decision making. Since there are multiple imperfect repairs, I can select one option from them when the imperfect repair is preferable to operation and replacement. To express this situation, I propose a POMDP model and theoretically investigate the structure of an optimal maintenance policy minimizing a total expected discounted cost for an unbounded horizon. Then two stochastic orders are used for the analysis of our problem.

基于改进MDP的边缘计算任务卸载研究

针对强化学习进行边缘计算任务卸载时,面临大规模动作空间导致的收敛慢,计算速率低的问题,采用改进马尔科夫决策过程(Markov Decision Process, MDP)的移动边缘计算任务卸载算法。首先对信道增益去噪,使用时间卷积网络(Temporal convolutional network, TCN)生成卸载动作,然后根据改进的MDP选择最优卸载动作,引入经验回放机制存储最优卸载动作,依据提出的概率优先级抽样训练TCN,最终得到最佳卸载策略与资源分配。实验对比任务全部本地处理、全部卸载、长短期记忆网络融合改进MDP等基准算法,由结果得出模型可以快速收敛,有效提高计算速率,证明了模型的有效性和可靠性。

基于深度强化学习的多自动导引车运动规划

为解决移动机器人仓储系统中的多自动导引车(AGV)无冲突运动规划问题,建立了Markov决策过程模型,提出一种新的基于深度Q网络(DQN)的求解方法。将AGV的位置作为输入信息,利用DQN估计该状态下采取每个动作所能获得的最大期望累计奖励,并采用经典的深度Q学习算法进行训练。算例计算结果表明,该方法可以有效克服AGV车队在运动中的碰撞问题,使AGV车队能够在无冲突的情况下完成货架搬运任务。与已有启发式算法相比,该方法求得的AGV运动规划方案所需要的平均最大完工时间更短。

基于深度强化学习的综合航电系统安全性优化方法

为解决传统基于人工检查的安全性设计方法难以应对航电系统大规模集成带来的可选驻留方案爆炸问题,构建航电系统分区模型、任务模型以及安全关键等级量化模型,将考虑安全性的综合化设计优化问题模型化为马尔可夫决策过程(MDP)问题,并提出一种基于Actor-Critic框架的柔性动作-评价(SAC)算法的优化方法;为得到SAC算法的参数选择和训练结果之间的相关性,针对算法参数灵敏度开展研究;同时,为验证基于SAC算法的优化方法在优化考虑安全性的综合化设计方面的优越性,以深度确定性策略梯度(DDPG)算法和传统分配算法为对象,开展优化对比试验。结果表明:在最佳的参数组合下,使用的SAC算法收敛后的最大奖励相较于其他参数组合提升近8%,同时,收敛时间缩短近16.6%;相较于DDPG算法和传统分配算法,基于SAC算法的优化方法在相同的参数设置下获得的最大奖励、约束累计违背率、分区均衡风险效果、分区资源利用以及求解时间方面最大提升分别为62%、7464%、8370%、2123%和775%。

支持无线采能及簇间负载均衡的无人机辅助数据调度及轨迹优化算法

该文研究了无人机(UAV)辅助无线传感器网络的数据收集问题。首先提出基于均值漂移算法的传感器节点(SN)初始分簇策略,进而以簇间负载均衡为目标,设计SN切换算法。基于所得成簇策略,将UAV数据收集及轨迹规划问题建模为系统能耗最小化问题。由于该问题是一个非凸问题,难以直接求解,将其分为两个子问题,即数据调度子问题及UAV轨迹规划子问题。针对数据调度子问题,提出一种基于多时隙库恩-蒙克雷斯算法的时频资源调度策略。针对UAV轨迹规划子问题,将其建模为马尔可夫决策过程,并提出一种基于深度Q网络的UAV轨迹规划算法。仿真结果验证了所提算法的有效性。