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.

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%.

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.

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.

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

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

基于MDP框架的飞行器隐蔽接敌策略

基于近似动态规划(approximate dynamic programming,ADP)对空战飞行器隐蔽接敌决策问题进行研究。基于作战飞行器的战术使用原则,提出了隐蔽接敌过程中的优势区域与暴露区域;构建了基于马尔科夫决策过程(Markov decision process,MDP)的隐蔽接敌策略的强化学习方法;通过态势得分函数对非连续的即时收益函数进行修正,给出了基于ADP方法的策略学习与策略提取方法。分别针对对手在有无信息源支持情况下的不同机动对策进行了仿真验证。仿真结果表明,将ADP方法应用于隐蔽接敌策略的学习是可行的,在不同态势下可获得较为有效的接敌策略。

基于HMDP的无人机三维路径规划

路径规划是UAV(Unmanned Aerial Vehicle)自主飞行的重要保障.初步建立了基于MDP(Markov Decision Processes)的全局路径规划模型,把UAV的路径规划看作是给定环境模型和奖惩原则的情况下,寻求最优策略的问题;为解决算法时空开销大、UAV航向改变频繁的缺点,提出一种基于状态聚类方法的HMDP(Hierarchical Markov Decision Processes)模型,并将其拓展到三维规划中.仿真实验证明:这种简单的规划模型可以有效解决UAV的三维全局路径规划问题,为其在实际飞行中的局部规划奠定了基础.

基于POMDP的不稳定心绞痛中西医结合治疗方案优化研究

目的初步优化中西医结合防治不稳定心绞痛(unstable angina,UA)的综合治疗方案。方法基于部分可观察的马尔科夫决策过程模型(Partially Observable Markov Decision Process,POMDP)的方法,选择气虚、血瘀、痰浊3个主要证侯要素,对UA住院患者的诊治情况进行深层次数据挖掘、分析,客观评价UA中西医结合的疗效。结果 UA气虚证、血瘀证、痰浊证患者的推荐治疗方案依次为:硝酸酯类+他汀类+氯吡格雷+血管紧张素Ⅱ受体阻滞剂+肝素类+黄芪+党参+茯苓+白术(ADR=0.85077869);硝酸酯类+阿司匹林+氯吡格雷+他汀类+肝素类+当归+红花+桃仁+赤芍(ADR=0.70773000);硝酸酯类+阿司匹林+他汀类+血管紧张素转换酶抑制剂+栝蒌+薤白+半夏+陈皮(ADR=0.72509600)。结论本研究基于POMDP优化了UA的治疗方案,可作为进一步规范和制定中西医结合治疗UA方案的参考。

基于MDP随机路径模拟的电动汽车充电负荷时空分布预测

针对电动汽车时空转移随机性的问题,计及实时交通与温度,提出了一种基于马尔可夫决策过程随机路径模拟的城市电动汽车充电负荷时空分布预测方法。首先,根据各类车型充电方式与出行特点对各类电动汽车进行分类;其次,根据蒙特卡洛方法建立各类电动汽车的时空转移模型,采用马尔可夫决策理论对出行路径进行实时动态随机模拟;根据电动汽车实测数据建立温度、交通能耗模型,计算得到实时单位里程耗电量。最后,以某典型城区为例,对不同温度、不同交通状况下电动汽车区域充电负荷进行计算。仿真结果表明,区域内快充负荷较大的节点充电波动性较大,环境温度升高或交通拥堵状况恶化会导致充电负荷高峰的持续时间增高。

基于POMDP的信道感知接入算法

在认知无线电中,为了最大化次用户的吞吐量,同时对主用户的干扰低于预定值,提出一种基于POMDP的信道感知接入算法。次用户将主用户信道在时间轴上细分成等间隔的时隙,在每个时隙开始时,次用户从频谱感知、以较高的功率接入信道和以较低的功率接入信道三种可选策略中选择最优的策略。将次用户的选择过程建模成一个POMDP问题,并采用一些相应的最优策略求解。计算机仿真结果验证了算法的有效性。

基于Markov决策过程用交叉熵方法优化软件测试

研究了待测软件某些参数已知的条件下,以最小化平均测试费用为目标的软件测试优化问题.将软件测试过程处理成马尔可夫(Markov)决策过程,给出了软件测试的马尔可夫决策模型,运用交叉熵方法,通过一种学习策略获得软件测试的最优测试剖面,用于优化软件测试.模拟结果表明,学习策略给出的测试剖面要优于随机测试策略,检测和排除相同数目的软件缺陷,学习策略比随机测试能够显著地减少测试用例数,降低测试成本,提高缺陷检测效率.

基于Markov game模型的装备保障信息网络安全态势感知方法研究

为了提升装备保障信息网络的安全态势感知能力,根据装备保障信息网络的特点,提出了基于Markov决策过程和博弈论思想的网络安全态势评估方法。该方法以Markov game模型为核心,通过求解纳什均衡点确定攻守双方的博弈对网络安全造成的影响,并利用4级数据融合实现对装备保障信息网络安全态势的评估。实验证明,该方法能够综合各类基础信息,准确给出装备保障信息网络的安全态势值。

Markov过程理论在发电商报价策略选择中的应用

在电力市场的环境下,发电商在报价策略选择的过程中将面临许多不确定性因素,如各时段的系统负荷、市场边际价格、对手的报价策略、自身发电成本等,本文从发电商的角度出发对竞价策略的选择问题进行研究,将竞价策略选择的过程设计成为Markov决策过程——一种抽象的随机优化方法,先将每个时段的报价简化为报价参数的选择,利用Markov过程理论对不确定性因素的出现进行概率估计,将发电商报价策略的选择问题表示为离散的随机优化过程—— Markov决策过程;通过使期望收益最大来计算最优策略,从而确定了每个时段发电商报价参数的最优选择,并将报价参数还原成为报价结果。

不确定SMDP基于全局优化的鲁棒决策问题

考虑半马尔可夫决策过程(SMDP)在一些系统参数不确定,且性能函数依赖于这些参数时的鲁棒决策问题。这些参数的不确定性不仅导致等价无穷小生成子的不确定性,也导致性能函数的不确定性。论文针对相关参数的情况,分别采用不同的全局优化算法,即填充函数法和模拟退火算法,进行鲁棒控制策略求解。仿真实例说明,全局优化方法的使用保证了平均准则和折扣准则下的计算结果之间当折扣因子趋近于零时的极限关系成立。

预测行人运动的服务机器人POMDP导航

为提高室内动态环境下服务机器人对行人的自然避让能力,对人的运动轨迹模式进行建模,在此基础上引入了将行人运动长、短期预测结合起来的方法.为适应传感器噪声及网络延迟等因素所造成的感知—控制回路中的多源不确定性,将人与机器人的相对位置关系建模为部分可观的马尔可夫状态.采用部分可观的马尔可夫决策过程(POMDP)进行多源不确定性下的概率决策,协调控制机器人全局路径规划、反应式运动及速度控制等行为模块.实验结果验证,它能够实现提前避碰的安全导航,因避免反复的曲折与徘徊运动而提高了机器人导航效率.