基于蒙特卡洛树搜索的数值目标子群发现算法

MonteCloPi算法是一种基于蒙特卡洛树搜索(Monte Carlo tree search, MCTS)的任意时间子群发现算法,旨在使用MCTS策略构建非对称的最佳优先搜索树来发现高质量的多样性模式集,但是限制了目标为二值变量.为此,本文结合了数值目标的特点,通过为置信度上界(upper confidence bound, UCB)公式选取合适的C值、动态调整各个样本的拓展权重并对搜索树进行剪枝、使用自适应top-k均值更新策略,将MonteCloPi算法拓展到了数值目标.最后,在UCI数据集、全国健康与营养调查(national health and nutrition examination survey, NHANES)听力测试数据集上的实验结果表明本文的算法相比其他算法可以发现更高质量的多样性模式集,并且最优子群的可解释性也更好.     

An intelligent task offloading algorithm (iTOA) for UAV edge computing network

Unmanned Aerial Vehicle (UAV) has emerged as a promising technology for the support of human activities, such as target tracking, disaster rescue, and surveillance. However, these tasks require a large computation load of image or video processing, which imposes enormous pressure on the UAV computation platform. To solve this issue, in this work, we propose an intelligent Task Offloading Algorithm (iTOA) for UAV edge computing network. Compared with existing methods, iTOA is able to perceive the network’s environment intelligently to decide the offloading action based on deep Monte Calor Tree Search (MCTS), the core algorithm of Alpha Go. MCTS will simulate the offloading decision trajectories to acquire the best decision by maximizing the reward, such as lowest latency or power consumption. To accelerate the search convergence of MCTS, we also proposed a splitting Deep Neural Network (sDNN) to supply the prior probability for MCTS. The sDNN is trained by a self-supervised learning manager. Here, the training data set is obtained from iTOA itself as its own teacher. Compared with game theory and greedy search-based methods, the proposed iTOA improves service latency performance by 33% and 60%, respectively.     

混合蒙特卡罗搜索的特征选择算法的优化

特征选择是机器学习和数据挖掘中处理高维数据的初步步骤,通过消除冗余或不相关的特征来识别数据集中最重要和最相关的特征,从而提高分类精度和降低计算复杂度。文中提出混合蒙特卡罗树搜索特征选择算法(HMCTS),首先,根据蒙特卡罗树搜索方法迭代生成一个初始特征子集,利用ReliefF算法过滤选择前k个特征形成候选特征子集;然后,利用KNN分类器的分类精度评估候选特征,通过反向传播将模拟结果更新到迭代路径上所有选择的节点;最后,选择高精度的候选特征作为最佳特征子集。仿真结果表明,对比HPSO-LS和MOTiFS算法,HMCTS算法具有良好的可扩展性,且分类精度高。     

车联网中视频内容理解任务的计算卸载决策研究

视频数据能够为车辆的智能网联化提供丰富的信息,为了更好地提取视频内容并使卸载后的视频中包含更多的有效信息,在时延约束条件下,设计一种内容驱动的计算卸载指导方式并提出基于改进蒙特卡洛树搜索的计算卸载决策算法。在车辆端通过关键帧提取来对视频内容进行预处理,以有效分析视频内容理解任务的重要性,使得更重要的任务能够获得更多的计算资源。采用基于强化学习的启发式搜索算法完成计算卸载决策,并引入深度神经网络预训练先验转移概率,从而优化算法的收敛速度并降低计算复杂度。实验结果表明,该算法能够在时延约束下有效降低能耗并提升视频内容理解精度,相比基于Q-learning、基于模拟退火的算法,其收敛速度更快,计算复杂度更低,在700 ms时延约束下系统总效用达到37%。     

基于蒙特卡洛树搜索的土石方动态调配算法及验证

针对堆石坝填筑进度控制以及土石方动态调运问题,受AlphaGo-Zero的启发,本文提出了一个基于蒙特卡洛树搜索(Monte Carlo tree search,MCTS)的土石方智能动态调配模型。该模型以当前累计填筑工程量、紧邻前一月份完成工程量以及当前月份为状态,用各月填筑工作面对应的填筑可达强度约束动作空间,综合考虑节点工期、总工期、坝面施工机械费用和土石方调运费用等因素构造奖励函数。此外,结合本文研究问题的特点,对MCTS迭代中的上限置信区间算法(upper confidence bound apply to tree,UCT)进行了改进和比较分析,最后以一个工程实例对本文提出模型的有效性进行了验证分析。结果表明,与施工仿真相比,以MCTS为框架的土石方动态调配模型的计算分析时间大大减少,为土石方动态调配问题提供了新的模型与手段。     

基于概率排序的存储约束树形搜索算法的研究*1

鉴于目前MIMO系统中大多数多符号差分检测算法对于大容量存储空间的需求和高计算复杂度的缺点,提出了一种概率排序的存储约束树搜索(Probabilistic Sorting Memory Constrained Tree Search,PSMCTS)算法,利用概率排序的性能优势与MCTS的存储优势来解决此问题。经过理论分析与仿真验证,该算法能够继承MCTS算法的优势,能够动态地适应预设的存储空间,适合硬件实现,而排序算法提高了检测性能,在固定的存储需求下,性能表现更加逼近ML算法,同时能够解决MCTS算法在小存储容量条件下低信噪比区域计算复杂度仍比较高的问题。因此,PSMCTS可以作为一种有效的方案应用在通信系统中。     

ROS2多线程执行器上DAG任务的优先级分配方法

随着机器人操作系统（robot operating system, ROS）的日益普及,系统也变得更加复杂,这类系统的计算平台正逐渐转变为多核心平台. 在ROS中,任务执行的顺序取决于底层任务调度策略和分配给任务的优先级,而最大限度地缩短所有任务的执行时间是并行系统任务调度的一个重要目标. 受强化学习在解决各种组合优化问题的最新研究成果的启发,在考虑ROS2多线程执行器的调度机制和执行约束的前提下,提出了一种基于强化学习的任务优先级分配方法,该方法提取了基于有向无环图形式表示的任务集的时间和结构特征,通过策略梯度和蒙特卡洛树搜索（Monte Carlo tree search, MCTS）方法有效地学习ROS2调度策略并给出合理的优先级设置方案,最终达到最小化并行任务的最大完工时间的目的. 通过模拟平台环境下随机生成的任务图以评估所提方法,结果表明所提方法明显优于基准方法. 作为一种离线分析方法,所提方法可以很容易地扩展到复杂的ROS中,在可接受的时间内找到接近最优的解决方案.

     

An Efficient Viewport-Dependent 360 VR System Based on Adaptive Tiled Streaming

Recent advances in 360 video streaming technologies have enhanced the immersive experience of video streaming services. Particularly, there is immense potential for the application of 360 video encoding formats to achieve highly immersive virtual reality (VR) systems. However, 360 video streaming requires considerable bandwidth, and its performance depends on several factors. Consequently, the optimization of 360 video bitstreams according to viewport texture is crucial. Therefore, we propose an adaptive solution for VR systems using viewport-dependent tiled 360 video streaming. To increase the degrees of freedom of users, the moving picture experts group (MPEG) recently defined three degrees plus of freedom (3DoF+) and six degrees of freedom (6DoF) to support free user movement within camera-captured scenes. The proposed method supports 6DoF to allow users to move their heads freely. Herein, we propose viewport-dependent tiled 360 video streaming based on users’ head movements. The proposed system generates an adaptive bitstream using tile sets that are selected according to a parameter set of user’s viewport area. This extracted bitstream is then transmitted to the user’s computer. After decoding, the user’s viewport is generated and rendered on VR head-mounted display (HMD). Furthermore, we introduce certain approaches to reduce the motion-to-photon latency. The experimental results demonstrated that, in contrast with non-tiled streaming, the proposed method achieved high-performance 360 video streaming for VR systems, with a 25.89% BD-rate saving for Y-PSNR and 61.16% for decoding time.     

基于三元多臂赌博机的树结构最优动作识别

蒙特卡罗树搜索（MCTS）在棋类博弈问题中展现出卓越的性能，但目前多数研究仅考虑胜负两种反馈从而假设博弈结果服从伯努利分布，然而这种设定忽略了常出现的平局结果，导致不能准确地评估盘面状态甚至错失最优动作。针对这个问题，首先构建了基于三元分布的多臂赌博机（TMAB）模型并提出了最优臂确认算法TBBA；然后，将TBBA算法应用到三元极大极小采样树（TMST）中，提出了简单迭代TBBA算法的TBBA_tree算法和通过将树结构转化成TMAB的TMST最优动作识别（TTBA）算法。在实验部分，建立了两个精度不同的摇臂空间并在其基础上构造了多个具有对比性的TMAB和TMST。实验结果表明，相比均匀采样算法，TBBA算法准确率保持稳步上升且部分能达到100%，TBBA算法准确率基本保持在80%以上且具有良好的泛化性和稳定性，不会出现异常值和波动区间。     

多约束复杂环境下UAV航迹规划策略自学习方法

在多约束复杂环境下,多数无人飞行器(UAV)航迹规划方法无法从历史经验中获得先验知识,导致对多变的环境适应性较差.提出一种基于深度强化学习的航迹规划策略自学习方法,利用飞行约束条件设计UAV的状态及动作模式,从搜索宽度和深度2个方面降低航迹规划搜索规模,基于航迹优化目标设计奖惩函数,利用由卷积神经网络引导的蒙特卡洛树搜...