精华内容
下载资源
问答
  • 此方法同源借鉴于ICIA一篇强化学习paper 源码github地址:https://github.com/a7b23/Autonomous-MazePathFinder-using-DQN 该程序将由几个封锁(由块颜色表示)组成的图像作为输入,起始点由蓝色表示,目的地由绿色...

    感谢知乎搬砖的旺财博主;此方法同源借鉴于ICIA一篇强化学习paper
    源码github地址:https://github.com/a7b23/Autonomous-MazePathFinder-using-DQN

    该程序将由几个封锁(由块颜色表示)组成的图像作为输入,起始点由蓝色表示,目的地由绿色表示。 它输出一个由输入到输出的可能路径之一组成的图像。 下面显示的是程序的输入和输出。

    在这里插入图片描述

    在这里插入图片描述
    输入图像被馈送到由2个conv和2个fc层组成的模型,其输出对应于底部和右侧动作的Q值。 代理根据哪个Q值更大而向右或向下移动,并且使用代理的新位置生成的相应新图像再次被馈送到模型。获得输出状态并反馈新图像的过程保持重复 直到代理到达到达目的地的终端阶段。

    总体思路:

    • 获取image(map)
    • Agent处理image
    • Mobile Robot得到向前还是向右的指令
    • 实现了对无人车end-to-end的路径规划。

    在这里插入图片描述

    Data Generation

    代码DataGeneration.py为任务生成必需的数据。 它在25X25大小的图像中随机分配1X1像素大小的块。同时生成对应于每个不同起始位置的所有625个图像并将其存储在文件夹中。具有变化的阻塞位置的200个不同的这样的游戏的图像是 生成,因此总训练图像达250 * 625。 还生成与每个不同状态(图像)相关联的分数并将其存储在txt文件中,其中起始点与阻塞碰撞的状态获得-100的分数,当起始点与目的地碰撞时,其获得分数 100和所有剩余的状态得分为0。
    在这里插入图片描述

    Training

    InitialisingTarget.py生成与每个训练图像相关联的初始Q值,并将它们存储在txt文件-Targets200_New.txt中。生成的Q值只不过是随机初始化模型的输出。 training2.py开始训练模型。从trainig数据中选择随机批量大小的图像集并将其馈送到模型。根据损失更新模型权重,该损失是输出Q值和预期Q值之间的平方差异。预期的Q(s,a)= r(s,a)+ gamma * max(Q1(s1,a)),其中max取2个动作。这里Q1对应于存储在’Targets200_New.txt’文件中的q值。奖励r也是下一个州和当前州之间得分的差异。几个训练Q1值的时期再次更新并存储在相同的txt文件中,输出来自训练模型。新的Q1值再次用于训练模型。生成目标Q值和训练模型的步骤重复几个步骤,直到模型学习所需特征。
    在这里插入图片描述

    Testing

    就像DataGeneration.py一样,TestDataCollection.py也以相同的格式生成图像,除了它不是200个游戏,而是在单独的文件夹中生成仅对应20个游戏的图像。 对于20个游戏中的每个游戏,testing.py获取对应于代理位于0,0位置的图像,并将单个最终路径的图像输出到单独的文件夹中的目的地。 对于由于与阻塞冲突而无法找到路径的游戏,不会生成图像。

    initialisingtarget.py生成每个训练图像对应的初始Q值,保存在TXT文件targets200_new中,产生的Q值只是随机初始化模型的输出。

    一、定义函数

    定义一个函数,用于初始化所有的权值W

    def weight_variable(shape):
        initial = tf.truncated_normal(shape, stddev=0.05)
        return tf.Variable(initial)
    

    定义一个函数,用于初始化所有的偏置项b

    def bias_variable(shape):
        initial = tf.constant(0.05, shape=shape)
        return tf.Variable(initial)
    

    定义一个函数,用于构建卷积层

    def conv2d(x, W):
        return tf.nn.conv2d(x, W, strides=[1, 1, 1, 1], padding='SAME')
    

    x为input,[batch, in_height, in_width, in_channels] ,[训练时一个batch的图片数量, 图片高度, 图片宽度, 图像通道数];
    W为卷积核,它要求是一个Tensor,[filter_height, filter_width, in_channels, out_channels],[卷积核的高度,卷积核的宽度,图像通道数,卷积核个数],要求类型与参数input 相同,有一个地方需要注意,第三维 in_channels,就是参数input的第四维;
    strides,卷积时在图像每一维的步长;
    padding:string 类型的量,只能是"SAME" , “VALID” 其中之一,这个值决定了不同的卷积方式。

    二、网络

    2.1 input layer

    x = tf.placeholder(tf.float32, shape=[None, imageSize[0], imageSize[1], imageSize[2]])
    

    shape=[None, imageSize[0], imageSize[1], imageSize[2]]
    shape转换成了4D tensor,第二与第三维度对应的是照片的宽度与高度,最后一个维度是颜色通道数
    2. tf.placeholder(dtype, shape=None, name=None)

    dtype:数据类型。常用的是tf.float32 , tf.float64 等数值类型;
    shape:数据形状。默认是None,就是一维值,也可以是多维,比如[2,3] , [None, 3] 表示列是3,行不定;
    name:名称。

    2.2 卷积层

    2.2.1 卷积神经网络之训练算法

    同一般机器学习算法,先定义Loss function,衡量和实际结果之间差距
    找到最小化损失函数的w和b,CNN中用的算法是SGD(随机梯度下降)
    卷积运算是为了提取输入的不同特征,第一层可能只能提取到一些简单的特征,例如边缘,层数越高提取的特征越复杂。

    卷积层有两个关键操作:

    局部关联。每个神经元看做一个滤波器(filter)
    窗口(receptive field)滑动,filter对局部数据计算

    由于卷积层的神经元也是三维的,所以也具有深度
    卷积层的参数包含一系列过滤器,每个过滤器训练一个深度,有几个过滤器输出单元就具有多少深度
    对于输出单元不同深度的同一位置,与输入图片连接的区域是相同的,但是参数(过滤器)不同

    2.2.2 卷积神经网络之优缺点

    优点
    共享卷积核,对高维数据处理无压力
    无需手动选取特征,训练好权重,即得特征分类效果好
    2. 缺点
    需要调参,需要大样本量,训练最好要GPU
    物理含义不明确(也就说,我们并不知道每个卷积层到底提取到的是什么特征,而且神经网络本身就是一种难以解释的“黑箱模型”)

    2.2.3 第1个卷积层

    如下图所示,展示了一个3×3的卷积核在5×5的图像上做卷积的过程。每个卷积都是一种特征提取方式,就像一个筛子,将图像中符合条件(激活值越大越符合条件)的部分筛选出来。
    在这里插入图片描述

    # network weights
    # 第1、2个参数是窗口的大小,第3个参数是channel的数量,第4个参数定义了我们想使用多少个特征
    W_conv1 = weight_variable([2, 2, 3, 10])
    b_conv1 = bias_variable([10]) 
    
    # hidden layers
    h_conv1 = tf.nn.relu(conv2d(x, W_conv1) + b_conv1)
    

    分析程序的第一个卷积层,可以发现输入照片大小为25 * 25,窗口为2 * 2,会产生第一层隐藏层中25 * 25排列的神经元,这是因为我们需要从上到下移动窗口25次,从左到右移动窗口25 次来覆盖整个输入图片。在这里是假设窗口每次只移动一个像素,所以新窗口与上次的窗口会有重叠。

    padding=‘SAME’
    输入矩阵W×W,W = 25;
    filter矩阵F×F,卷积核,F = 2;
    stride值S,步长,S = 1;
    1.计算:

    new_height = new_width = W / S = 25 / 1 = 25 #结果向上取整
    

    含义:new_height为输出矩阵的高度
    说明:对W/S的结果向上取整得到W"包含"多少个S
    2. pad_needed_height = (new_height – 1) × S + F - W = (25-1)X 1 + 2 - 25 = 1

    含义:pad_needed_height为输入矩阵需要补充的高度
    说明:因为new_height是向上取整的结果,所以先-1得到W可以完全包裹住S的块数,之后乘以S得到这些块数的像素点总和,再加上filer的F并减去W,即得到在高度上需要对W补充多少个像素点才能满足new_height的需求
    3. pad_top = pad_needed_height / 2 = 1 / 2 = 0 #结果取整

    含义:pad_top为输入矩阵上方需要添加的高度
    说明:将上一步得到的pad_needed_height除以2 作为矩阵上方需要扩充0的像素点数
    4. pad_bottom = pad_needed_height - pad_top = 1 - 0 =1

    含义:pad_bottom为输入矩阵下方需要添加的高度
    说明:pad_needed_height减去pad_top的剩余部分补充到矩阵下方
    同理:

    pad_needed_width = (new_width – 1) × S + F - W = (25-1)X 1 + 2 - 25 = 1
    pad_left = pad_needed_width / 2 = 0
    pad_right = pad_needed_width – pad_left = 1

    在这里插入图片描述
    基于我们研究的样例,我们需要1个bias b与1个2*2的矩阵W来连接输入层与隐藏层的神经元。

    CNN的一个关键特性是这个权重矩阵W与bias b是隐藏层中所有神经元间共享的。

    本程序中是24 * 24 (576) 个神经元。你将会发现与全连接的神经网络相比,这会大大减少权重参数的数量。具体来说,由于共享了权重矩阵W,参数数量会从2304(2 * 2 * 24 * 24) 降到4(2 * 2)。

    这个共享的矩阵W与bias b在CNN中经常被叫作kernel或filter。这些filters与图像处理程序中润色图片的那些是类似的,此处是用来找出有鉴别性的feature。

    一个矩阵与bias定义了一个kernel。一个kernel仅仅只检测图像中一个特定相关的feature,所以建议使用多个kernels,每个想检测的特征一个kernel。这就意味着CNN中一个完整的卷积层包含了很多kernels。描述这些kernels的一个常用方法如下:
    在这里插入图片描述
    隐藏层的第一层包含了多个kernels。此处,我使用了10 个kernels,每一个定义了2*2的权重矩阵W和bias b,这两个参数也是隐藏层间共享的。

    ReLU(Rectified Linear unit)激活函数最近变成了神经网络中隐藏层的默认激活函数。这个简单的函数包含了返回max(0,x),所以对于负值,它会返回0,其它返回x。

    代码中首先对输入图像x(image) 计算卷积,计算得到的结果保存在2D tensor W_conv1中,然后与bias求和,接下来应用ReLU激活函数。

    2.2.4 第2个卷积层

    # network weights
    W_conv2 = weight_variable([2, 2, 10, 20])
    b_conv2 = bias_variable([20])
    
    # hidden layers
    h_conv2 = tf.nn.relu(conv2d(h_conv1, W_conv2) + b_conv2)
    

    分析程序的第二个卷积层,窗口为2 * 2,20个filters,此时我们会需传递10个channels,因为这是前一层的输出结果。

    2.2.5 卷积神经网络的时间复杂度分析

    在这里插入图片描述
    2.2.5.1 单个卷积层的时间复杂度
    在这里插入图片描述
    M:每个卷积核输出特征图的边长
    K:每个卷积核的边长
    C_{in} :每个卷积核的通道数,也即输入通道数,也即上一层的输出通道数
    C_{out} :本卷积层具有的卷积核个数,也即输出通道数
    注:严格来讲每层应该还包含1个Bias参数,这里为了简洁就省略了。
    在这里插入图片描述
    在这里插入图片描述
    2.2.5.2 卷积神经网络整体的时间复杂度

    在这里插入图片描述
    D :神经网络所具有的卷积层数,也即网络的深度。
    l :神经网络第 l 个卷积层。
    C_l :神经网络第 l 个卷积层的输出通道数 C_{out} ,也即该层的卷积核个数。对于第 l 个卷积层而言,其输入通道数 C_{in} 就是第 l-1 个卷积层的输出通道数。

    在这里插入图片描述
    2.2.5.3 时间复杂度对模型的影响
    时间复杂度决定了模型的训练/预测时间。如果复杂度过高,则会导致模型训练和预测耗费大量时间,既无法快速的验证想法和改善模型,也无法做到快速的预测。

    2.2.6 卷积神经网络的空间复杂度分析

    空间复杂度包括模型的参数数量(模型本身的体积)和每层输出的特征图大小(会影响模型运行时的内存占用情况)。

    2.2.6.1 空间复杂度
    在这里插入图片描述
    可见,网络的参数量只与卷积核的尺寸K、通道数C、网络的深度D相关。而与输入数据的大小无关。当我们需要裁剪模型时,由于卷积核的尺寸通常已经很小,而网络的深度又与模型的能力紧密相关,不宜过多削减,因此模型裁剪通常最先下手的地方就是通道数。
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    2.2.6.2 空间复杂度对模型的影响
    空间复杂度决定了模型的参数数量。由于维度诅咒的限制,模型的参数越多,训练模型所需的数据量就越大,而现实生活中的数据集通常不会太大,这会导致模型的训练更容易过拟合。

    2.2.7 神经元的运算

    在这里插入图片描述
    以conv1为例:
    在这里插入图片描述
    卷积核实际上有2X2个神经元,每个神经元的厚度为3,所以1个卷积核有2X2X3个w参数,由于共有10个卷积核,所以共有2X2X3X10个w参数和10个b参数。连接数量为((2X2+1)X10)X25X25=31250。

    卷积核输出组成一个25×25的矩阵,称为特征图。

    第一个神经元连接到图像的第一个2×2的局部,第二个神经元则连接到第二个局部。(注意,有重叠!就跟你的目光扫视时也是连续扫视一样)如果应用参数共享的话,实际上每一层计算的操作就是输入层和权重的卷积。

    下面展示2(输出层的厚度)个3X3X3(卷积核的厚度)的卷积核在7X7X3(输入层的深度)的输入层上做卷积的过程,求出对应输出层的第一个元素(注意有厚度):
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    注释: \bullet 代表矩阵做内积。

    2.2.8 卷积神经网络的参数共享

    给一张输入图片,用一个filter去扫这张图,filter里面的数就叫权重,这张图每个位置是被同样的filter扫的,所以权重是一样的,也就是共享。

    对于一张输入图片,大小为WH,如果使用全连接网络,生成一张XY的feature map,需要WHX*Y个参数,如果原图长宽是 10^2 级别的,而且XY大小和WH差不多的话,那么这样一层网络需要的参数个数是 10^8 ~ 10^{12} 级别。

    这么多参数肯定是不行的,对于输出层feature map上的每一个像素,他与原图片的每一个像素都有连接,每一个连接都需要一个参数。但注意到图像一般都是局部相关的,那么如果输出层的每一个像素只和输入层图片的一个局部相连,那么需要参数的个数就会大大减少。

    假设输出层每个像素只与输入图片上FF的一个小方块有连接,也就是说输出层的这个像素值,只是通过原图的这个FF的小方形中的像素值计算而来,那么对于输出层的每个像素,需要的参数个数就从原来的WH减小到了FF。

    如果对于原图片的每一个FF的方框都需要计算这样一个输出值,那么需要的参数只是WHFF,如果原图长宽是 10^2 级别,而F在10以内的话,那么需要的参数的个数只有10^5 ~ 10{6}级别,相比于原来的108 ~ 10^{12}小了很多很多。这还不够。

    图片还有另外一个特性:图片的底层特征是与特征在图片中的位置无关的。比如说边缘,无论是在图片中间的边缘特征,还是在图片边角处的边缘特征,都可以用过类似于微分的特称提取器提取。那么对于主要用于提取底层特称的前几层网络,把上述局部全连接层中每一个FF方形对应的权值共享,就可以进一步减少网络中参数的个数。也就是说,输出层的每一个像素,是由输入层对应位置的FF的局部图片,与相同的一组FF的参数(或称权值)做内积,再经过非线性单元计算而来的。这样的话无论图片原大小如何,只用FF个参数就够了,也就是几个几十个的样子。当然一组F*F的参数只能得到一张feature map,一般会有多组参数,分别经过卷积后就可以有好几层feature map。

    高级特征一般是与位置有关的,比如一张人脸图片,眼睛和嘴位置不同,那么处理到高层,不同位置就需要用不同的神经网络权重,这时候卷积层就不能胜任了,就需要用局部全连接层和全连接层。
    在这里插入图片描述
    网上找的一张图,示意了局部连接,每一个W只与输入的一部分连接,如果W1和W2是相同的,那么就是卷积层,这时参数W1和W2相同,因此说共享。

    2.3 全连接层

    全连接层的每一个结点都与上一层的所有结点相连,用来把前边提取到的特征综合起来。在前向计算过程,也就是一个线性的加权求和的过程,全连接层的每一个输出都可以看成前一层的每一个结点乘以一个权重系数W,最后加上一个偏置值b得到。

    2.3.1 第1个全连接层

    我们使用包含100个神经元的一层来处理整个图片。权重与bias的tensor如下:
    network weights
    W_fc1 = weight_variable([25 * 25 * 20, 100])
    b_fc1 = bias_variable([100])
    tensor的第一维度表示第二层卷积层的输出,大小为25*25带有20个filters,第二个参数是层中的神经元数量,我们可自由设置。

    那么,全连接层fc1,输入有252520=12500个神经元结点,输出有100个结点,则一共需要252520*100=1250000个权值参数W和100个偏置参数b。
    在这里插入图片描述
    在这里插入图片描述
    接下来,我们将tensor打平到vector中。通过打平后的vector乘以权重矩阵W_fc1,再加上bias b_fc1,最后应用ReLU激活函数后就能实现

    # hidden layers
    h_conv2_flat = tf.reshape(h_conv2, [-1, 25 * 25 * 20])
    h_fc1 = tf.nn.relu(tf.matmul(h_conv2_flat, W_fc1) + b_fc1)
    # tf.matmul(a, b) 将矩阵a乘于矩阵b
    

    2.3.2 第2 个全连接层

    我们使用包含2个神经元的一层来处理整个图片。权重与bias的tensor如下:

    # network weights
    W_fc2 = weight_variable([100, 2])
    b_fc2 = bias_variable([2])
    
    # Q Value layer
    y_out = tf.matmul(h_fc1, W_fc2) + b_fc2
    

    2.4 网络结构

    在这里插入图片描述

    三、读取图像

    inputs = np.zeros([totalImages, imageSize[0], imageSize[1], imageSize[2]])
    print('reading inputs')
    for i in range(totalImages):
        temp = imageSize[0] * imageSize[1]
        inputs[i] = cv2.imread('trainImages/image_' + str(int(i / temp)) + '_' + str(i % temp) + '.png')
    print('inputs read')
    

    四、获取Q值

    4.1 iterations

    imageSize = [25, 25, 3]
    batchSize = 100
    games = 200
    totalImages = games * imageSize[0] * imageSize[1]
    
    iterations = int(totalImages / batchSize)
    

    images一共是25 * 25 * 200 = 125000,然后125000 / 100 = 1250,输出:

    number of iterations is 1250
    

    4.2 getBatchInput

    每次读取一个batchSize的inputs:

    batchInput, start = getBatchInput(inputs, start, batchSize) 
    
    def getBatchInput(inputs, start, batchSize):
        first = start
        start = start + batchSize
        end = start
        return inputs[first:end], start
    

    4.3 batchOutput

    batchOutput = sess.run(y_out, feed_dict={x: batchInput})
    

    其中feed_dict也即把batchInput一个一个赋给x,

    然后把x feed给我们搭好的网络。

    最后把batchOutput赋值给initialTarget:

    for j in range(batchSize):
        initialTarget.append(batchOutput[j])
    

    五、指数衰减

    首先使用较大学习率(目的:为快速得到一个比较优的解);
    然后通过迭代逐步减小学习率(目的:为使模型在训练后期更加稳定)。

    learningRate = 0.001  # 事先设定的初始学习率;
    lr_decay_rate = 0.9  # 衰减系数
    lr_decay_step = 2000  # 衰减速度
    

    生成学习率:

    lr = tf.train.exponential_decay(learningRate,
      global_step,
      lr_decay_step,
      lr_decay_rate,
      staircase=True)
    

    每隔lr_decay_step步,learningRate要乘以lr_decay_rate;
    staircase = True,每decay_steps次计算学习速率变化,更新原始学习速率。

    六、损失函数

    loss = tf.reduce_mean(tf.square(y_out), 1)  # tf.reduce_mean(x, 1)指定第二个参数为1,则第二维的元素取平均值,即每一行求平均值
    
    avg_loss = tf.reduce_mean(loss)  # tf.reduce_mean(x)如果不指定第二个参数,那么就在所有的元素中取平均值 
    

    七、训练模型

    我们已经定义好模型和训练用的损失函数,那么用TensorFlow进行训练就很简单了。因为TensorFlow知道整个计算图,它可以使用自动微分法找到对于各个变量的损失的梯度值。TensorFlow有大量内置的优化算法。我们用Adam优化算法让avg_loss下降,步长为lr。

    train_step = tf.train.AdamOptimizer(lr).minimize(avg_loss)
    

    这一行代码实际上是用来往计算图上添加一个新操作,其中包括计算梯度,计算每个参数的步长变化,并且计算出新的参数值。

    返回的train_step操作对象,在运行时会使用梯度下降来更新参数。因此,整个模型的训练可以通过反复地运行train_step来完成。

    八、运行TensorFlow的InteractiveSession

    sess = tf.InteractiveSession()
    

    Tensorflow依赖于一个高效的C++后端来进行计算。与后端的这个连接叫做session。一般而言,使用TensorFlow程序的流程是先创建一个图,然后在session中启动它。

    这里,我们使用更加方便的InteractiveSession类。通过它,你可以更加灵活地构建你的代码。它能让你在运行图的时候,插入一些计算图,这些计算图是由某些操作(operations)构成的。这对于工作在交互式环境中的人们来说非常便利,比如使用IPython。如果你没有使用InteractiveSession,那么你需要在启动session之前构建整个计算图,然后启动该计算图。

    九、记录信息

    运行整个程序,在程序中定义的summary node就会将要记录的信息全部保存在指定的logdir 路径中了,训练的记录会存一份文件,测试的记录会存一份文件。

    checkpointFile = 'NewCheckpoints/Checkpoint3.ckpt'
    
    saver = tf.train.Saver()  # 生成saver
    sess.run(tf.initialize_all_variables())  # 先对模型初始化
    

    训练完以后,使用saver.save来保存

    sess.run(tf.initialize_all_variables())
    
    展开全文
  • 桔妹导读:滴滴的路线引擎每天要处理超过400亿次的路线规划请求,路径规划是滴滴地图输出的核心服务之一。不同于传统的路径规划算法,本文主要介绍的是一次深度强化学习路径规划业务场景下的探索...

    桔妹导读:滴滴的路线引擎每天要处理超过400亿次的路线规划请求,路径规划是滴滴地图输出的核心服务之一。不同于传统的路径规划算法,本文主要介绍的是一次深度强化学习在路径规划业务场景下的探索,目标是为用户规划出最符合司乘双方习惯的路线,降低偏航率。

    当我们打开滴滴使用网约车服务时,出发前我们往往会关注要走哪条路,这条路要花多长时间,要花多少钱,有多少个红绿灯,路况是否拥堵......这些都与路径规划密切相关。路径规划对滴滴来说十分重要,它是网约车服务的重要一环,与用户体验直接相关,一次糟糕的“绕路”可能会引起一次投诉进线,甚至影响用户留存;而良好的路径规划不仅可以显著提升司乘双方的使用体验,还能让司机少堵在路上,进一步提升整体出行效率。

    1. 

    滴滴路径规划的背景

    以及业务逻辑的复杂性

    类似于语言任务中的token,物理世界的道路会被建模成一段一段的link,这些link都具有唯一的id以及对应的道路属性,比如长度,方向,道路等级等。对于路口来说,进入路口的link和出路口的link往往都有多个。拿北京举例,北京的路网包含大约200W个link,网约车订单可能会包含数十甚至上百个路口,在如此庞大且复杂的路网中和较为苛刻的时间限制下,规划出高质量的路线绝非易事。

    图中每一个带箭头的红色线段表示一个link,可以看出不同link之间的长度差别是比较大的。

    此外,我们知道物理世界的道路是会发生改变的,这种改变可能是永久的,比如修路,也可能是临时的,比如交通管制。所以路网数据也是动态的,实际上目前我们地图的路网数据是天级更新的,这也加大了路径规划任务的复杂度。

    从实际业务来看,和自驾推荐走更快,更通畅的路线不同,由于网约车会基于里程、时长计费,我们需要同时考虑时间、距离、价格、安全因素,推荐相对快又相对便宜的路线。考虑用户的偏好,让用户在安全、快速到达目的地的同时,让行驶距离尽量短,总花费尽量少,是我们路径规划的核心原则。但很多时候“快”和“近”很难同时满足。距离更短的路往往是次干路或者支路,红绿灯多,堵车可能性更大;而绕远的高速路或者环路,通行能力更强,只要不极拥堵,车速通常更快,反倒用时更短。

    有乘客希望更快,也有乘客希望不绕远。为了尽量平衡,从去年3月起,我们率先在网约车上线了“选择路线”功能,充分考虑乘客的出行偏好,提供最多三条路线供乘客选择(拼车、一口价订单司机需按照平台指定路线行驶);并联动司机服务部鼓励司机主动询问乘客是否有常走路线。今年8月,我们还进一步在北京、杭州、深圳、南京、西安、厦门等28个城市试行“行前多路线选择”功能。乘客实时呼叫网约车,发单前可以根据路线标签、预估里程、行驶时长等信息选择最合适的路线,系统自动同步至司机端导航。

    综上,想要做好让司乘双方都满意的路径规划是一件极具挑战的事情,但是这也为我们进一步提高出行服务质量提供了机遇。

    2. 

    路径规划算法和AI技术的融合 

    路径规划是指给定起终点的情况下,规划出一条或多条由起点到终点的路线。传统的路径规划是一个图论问题,当路网中的权值都是静态的时候,使用dijkstra等算法就可以求出权值之和最小的路线,比如求出两点之间距离最短的路线是容易的。然而在很多场景需要动态权值,调整权值大小也需要大量经验,目前线上采用的方式是先使用基于图论的算法生成一批低权值的路线,然后再经过基于机器学习算法的排序模型的筛选,这个过程涉及到粗排,精排,rerank,最后将排名靠前的路线透出给用户选择。这个路线规划系统涉及的链路还是比较长的,不同于基于图论算法生成高权值的路线,我们尝试探索一种基于AI算法的路线生成方式。

    得益于滴滴海量的出行数据尤其是高质量的轨迹数据,我们可以利用深度学习技术去挖掘和学习司机的驾驶行为以及用户对路线的偏好,借助训练出的深度模型在短时间内为用户规划出满意的路线,降低线上的偏航率。

    我们这里可以把寻路的过程和AlphaGo下围棋的场景进行类比,司机在路网中行驶犹如棋手在棋盘上落子,初级棋手往往通过记忆棋谱来获取暂时的领先,而最终赢棋往往要求棋手有“大局观”,每一步的落子考虑到之后棋局的演变,关键在于最终赢棋,而不在于一时的得失。寻路过程也是需要往后多看几步的,因为在某个路口的选择眼前可能看是最优的,放在全局看则不一定是最好的选择。我们探索路线生成的过程是和AlphaGo“进化”过程是相似的[1],是一个从监督学习到强化学习的过程。

    3. 

    规划最符合司乘习惯的路线:

    从监督学习到强化学习 

    3.1 “克隆”高质量的历史轨迹

    我们最先想到的是使用行为克隆(behavior clone)的方式解决寻路问题,这里可以将寻路看作一个连续决策的过程,把用户的历史真实轨迹当做专家轨迹,在每个路口(对应一个状态)用户作出的选择看作是一个近似最优的动作(action),接下来我们就可以在每个决策点做分类,专家行为作为正样本,非专家行为作为负样本,让分类模型去判断某个决策是否符合用户习惯,分类器会对一个状态和动作对输出一个概率值,这个概率越大代表用户越有可能在该状态采取对应的动作。这点与AlphaGo中的走子网络是类似的:通过专业棋手的棋谱数据来训练模型,让它学习专业棋手的下棋行为。

    在实际处理中,因为路线是被建模成连续的link序列,所以我们在网络结构中引入了在序列预测上表现强大的lstm,用lstm可以更好地建模用户从起点到当前位置的状态信息,在经过百万量级条轨迹训练后,我们的模型在每个路口的决策准确率达到了98%+,我们将这个能够在每个路口输出决策概率的模型称作寻路agent,它已经基本可以模拟用户的真实选择。

    如果在每一次决策都选择概率最大的那一个link(即贪心搜索)往往只能找到局部最优解,比如一条路前半段看起来更优,但是后半段可能不是最佳的。为了尽可能找到最符合用户习惯(即整条路线的概率最大),我们使用了beam search搜索策略,其主要思想就是在寻路过程中维护若干个(即beam size)最优的候选集,这种方式相比穷举法大大缩减了需要探索的空间,相比于贪心搜索考虑的情况更多,往往能够找到得分更高的路线,在自然语言处理领域,比如机器翻译任务中被大量使用。可以通过下面简单的例子理解beam search的过程。

    图中移动的小车展示了beam search在路径规划中的应用,在小车前进的过程中,我们可以给不同的路线打分,维护得分最高的topK路线,直到小车抵达终点。红色的路线表示最终得分最高的路线,也是最符合用户习惯的路线。

    3.2 行为克隆的问题

    行为克隆实际上属于监督学习的范畴,在AlphaGo中如果让agent纯粹的去学习棋谱中的走法,它很难打败更加专业的棋手,所以AlphaGo引入了强化学习并搭配MCTS这一搜索策略,从而大大提升了对弈的胜率。同样的,纯粹的拟合专家轨迹是存在问题的:当寻路agent在某个路口判断错误,那么就会进入到没有遇到过的状态,在这种状态下agent的判断容易出错,而错误的累积会容易导致寻路过程演变成“一步错步步错”的结果。虽然我们的模型具有一定的泛化能力,寻路agent也可以找到终点,但由于我们没有显式的引入偏航后的监督信号,寻路agent往往需要更多不必要的“绕路”才能回到理想的路线上来。图中蓝色轨迹是小车偏航后所致,小车既有可能回到demo轨迹(红色路线)上来,也有可能越来越远,偏离demo轨迹,因为模型并没有学习到发生偏航后该如何快速纠正。

    3.3 强化学习的应用

    强化学习是近年来解决行为克隆带来的问题的热门方向。在文本生成领域,seqGAN通过判别器(简称D)来指导生成器(简称G)的训练,在G生成下一个单词时,使用MCTS和D来评估这个单词的好坏,通过reward作为反馈,使用Policy Gradient来更新G的参数,从而增加reward大的单词的生成概率。与此方法类似的还有在游戏系列数据集上表现优秀的GAIL,AIRL,这些方法的主要思想是另外训练一个能够指导生成网络更新的评估网络,缺点在于略显复杂,训练难度和计算量较大。

    AlphaGoZero通过“自己与自己对弈”的过程大大增强了棋力,类似的,我们想要通过生成学习的方式来增强路线引擎的能力。这里我们采用Q-learning的方式来学习一个寻路策略,为了加速模型收敛的速度,我们这里先使用前文提到的行为克隆的方式训练一个能够容易走到目的地的基础模型,然后使用该基础模型在路网上寻路,生成大量的采样轨迹,如果在某个状态,模型采取的动作与用户一致,则给该状态-动作对以+1的reward,相反如果在该状态模型采取的动作与用户不一致,则给该状态-动作对的reawrd为0。这种人为设定reward的方式既没有引入对抗学习的过程,也不要额外学一个reward函数,计算量大幅度减小,同时它可以有效克服行为克隆带来的状态分布偏移的问题。

    图中大致展示了我们的训练流程,通过老模型的self-play获取新的轨迹数据,将采样得到的新轨迹和真实轨迹融合训练,更新我们的策略模型,该过程是可以不断迭代的。经过多轮迭代后,路线生成模型的分类准确率虽然没有明显提升,但是生成轨迹质量更高:与真实轨轨迹的重合率明显提高,偏航后返回到demo轨迹的速度更快。这是让人惊喜的结果。

    4. 

    总结

    滴滴的路线引擎每天需要处理超过400亿次的路线规划请求,我们致力于为平台用户提供安全,快捷的路线服务。本文介绍的路线生成方式是深度强化学习在路径规划业务上落地的一次探索,主要用来降低偏航率。考虑到路径规划业务的复杂性,我们会从更多的方向(比如躲避拥堵)来打磨我们的路线引擎,让它变得更加智能。

    当然目前路线引擎还有它不完善的地方,还需要持续的迭代和优化,也欢迎大家给我们提供宝贵的意见。我们团队将会持续优化路线引擎系统的性能,迭代路线规划的算法,为司机和乘客创造更大的用户价值。

    引用

    1. Mastering the game of Go with deep neural networks and tree search[J]. Nature, 2016, 529(7587):484-489.

    本文作者

    团队招聘

    滴滴地图与公交事业群定位团队负责为滴滴平台上的司乘双方提供精准的定位服务,构建出行基础设施,发挥平台的大数据优势,应用概率统计、机器学习、深度学习等技术,在GPS质量优化、网络定位、惯导推算、融合定位等细分方向上持续深耕,以技术驱动用户体验的提升。

    团队长期招聘算法工程师,包括机器学习、惯导推算等方向,欢迎有兴趣的小伙伴加入,可投递简历至 diditech@didiglobal.com,邮件请邮件主题请命名为「姓名-应聘部门-应聘方向」。

    扫描了解更多

    延伸阅读


    
    内容编辑 | Charlotte联系我们 | DiDiTech@didiglobal.com
    
    
    展开全文
  • README This is a project about deep reinforcement learning autonomous obstacle avoidance algorithm for UAV. The whole project includes obstacle avoidance in static environment and obstacle avoidance

    地址:https://github.com/ZYunfeii/UAV_Obstacle_Avoiding_DRL

    README

    This is a project about deep reinforcement learning autonomous obstacle avoidance algorithm for UAV. The whole project includes obstacle avoidance in static environment and obstacle avoidance in dynamic environment. In the static environment, Multi-Agent Reinforcement Learning and artificial potential field algorithm are combined. In the dynamic environment, the project adopts the combination of disturbed flow field algorithm and single agent reinforcement learning algorithm.

    Static environment

    There are four methods to solve:

    1. MADDPG
    2. Fully Centralized DDPG
    3. Fully Decentralized DDPG
    4. Fully Centralized TD3

    The third and the fourth methods perform better than others.

    Dynamic environment

    There are four methods to solve:

    1. PPO+GAE(with multi-processing )
    2. TD3
    3. DDPG
    4. SAC

    The first three methods perform just the same. PPO convergence needs less episodes. TD3 and DDPG converge fast. Though Soft Actor-Critic is an outstanding algorithm in DRL, it has no obvious effect in my environment.

    Traditional methods for UAV path planning

    Three traditional methods are written with MATLAB:

    1. A * search algorithm*
    2. RRT algorithm
    3. Ant colony algorithm

    C++:

    1. D star algorithm

    The experiments show that A* search algorithm is much better than others but it is less effective than reinforcement learning path planning.

    Artificial potential field algorithm

    This project provides the MATLAB and Python realization of artificial potential field algorithm.

    Python realization: ./APF/APFPy2.py ./APF/APFPy3.py ./APF/ApfAlgorithm.py (two-dimensional and three-dimensional)

    Matlab realization: ./APF/APF_matlab (two-dimensional)

    IFDS and IIFDS algorithm

    This is an obstacle avoidance planning algorithm based on flow field. I realize it with matlab. The code is in folder IIFDS_and_IFDS.

    How to begin trainning

    For example, you want to train the agent in dynamic environment with TD3, what you need to do is just running the main.py, then test.py, finally open matlab and run the test.m to draw.

    If you want to test the model in the environment with 4 obstacles, you just need to run Multi_obstacle_environment_test.py.

    Requirements

    numpy

    torch

    matplotlib

    seaborn==0.11.1

    Files to illustrate

    calGs.m: calculate the index Gs which shows the performance of the route.

    calLs.m: calculate the index Ls which shows the performance of the route.

    draw.py: this file includes the Painter class which can draw the reward curve of various methods.

    config.py: this file give the setting of the parameters in trainning process of the algorithm such as the MAX_EPISODE, batch_size and so on.

    Method.py: this file concludes many important methods such as how to calculate the reward of the agents.

    static_obstacle_environment.py: there are many static obstacle environments’ parameters in this file.

    dynamic_obstacle_environment.py: there are many dynamic obstacle environments’ parameters in this file.

    Multi_obstacle_environment_test.py: this file test the dynamic model in the environment in dynamic_obstacle_environment.py.

    data_csv: this file save some data such as the trace of UAV and the reward in trainning.

    AntColonybenchmark.m: ACO algorithm realized by MATLAB.

    Astarbenchmark.m: A* algorithm realized by MATLAB.

    RRTbenchmark.m: RRT algorithm realized by MATLAB.

    A simple simulation example

    • 见github

    all rights reserved.

    展开全文
  • 云平台环境下基于深度强化学习的物流配送路径规划研究,葛茂根,李岩,随着现代化工业生产的发展,智能配送系统的重要性与日剧增,配送任务规模的扩大,配送单元的路径规划任务会变得非常困难,传统的
  • 深度强化学习系列(1): 深度强化学习概述

    万次阅读 多人点赞 2018-03-30 20:45:33
    深度强化学习及其在自动驾驶中的应用( DRL & ADS ) 专栏系列文章规划 DRL&ADS系列之(1): 强化学习概述 DRL&ADS系列之(2): 深度强化学习及算法讲解 DRL&ADS系列之(3): ADS软...

    机器学习是人工智能的一个分支,在近30多年已发展为一门多领域交叉学科,涉及概率论、统计学、逼近论、凸分析、计算复杂性理论等的学科。强化学习(RL)作为机器学习的一个子领域,其灵感来源于心理学中的行为主义理论,即智能体如何在环境给予的奖励或惩罚的刺激下,逐步形成对刺激的预期,产生能获得最大利益的习惯性行为。它强调如何基于环境而行动,以取得最大化的预期利益。通俗的讲:就是根据环境学习一套策略,能够最大化期望奖励。由于它具有普适性而被很多领域进行研究,例如自动驾驶,博弈论、控制论、运筹学、信息论、仿真优化、多主体系统学习、群体智能、统计学以及遗传算法。

    ** RL和监督式学习, 非监督学习之间的区别:**
    ,其主要分为监督学习、非监督学习、深度学习和强化学习(见图1),其中三个之间的区别在于以下三点:

    • (1)、RL并不需要出现正确的输入/输出对,也不需要精确校正次优化的行为。它更加专注于在线规划,需要在探索(在未知的领域)和遵从(现有知识)之间找到平衡,其学习过程是智能体不断的和环境进行交互,不断进行试错的反复练习。
    • (2)、RL的不同地方在于:其中没有监督者,只有一个reward信号;反馈是延迟的,不是立即生成的;时间在RL中具有重要的意义。
    • (3)、 RL并不需要带有标签的数据,有可以交互的环境即可。

    这里写图片描述
    基于此,普通机器学习方法和强化学习之间的的关系已描述清楚。我们知道机器学习算法和深度学习可以做分类,回归、时间序列等经典问题,这已经在很多应用场景,例如语音、文字语义等基础性的人类认知方面取得非常大的突破,但是为什么还要学习强化学习呢?不得不从其应用场景说起。

    RL目前的应用场景:

    • 自动驾驶: 自动驾驶载具(self-driving vehicle)
    • 控制论(离散和连续大动作空间): 玩具直升机、Gymm_cotrol物理部件控制、机器人行走、机械臂控制。
    • 游戏: Go, Atari 2600(DeepMind论文详解)等
    • 理解机器学习: 自然语言识别和处理, 文本序列预测
    • 超参数学习: 神经网络参数自动设计
    • 问答系统: 对话系统
    • 推荐系统: 阿里巴巴黄皮书(商品推荐),广告投放。
    • 智能电网: 电网负荷调试, 调度等
    • 通信网络: 动态路由, 流量分配等
    • 物理化学实验: 定量实验,核素碰撞,粒子束流调试等
    • 程序学习和网络安全: 网络攻防等

    说了这么多,都是关于其背景和应用场景的话题(相关论文见RL-an overview中),那么到底什么是RL, 又是怎么工作的? 以及工作过程中会受那些因素的影响呢? 下文继续回到Rl主题上.

    一、强化学习基本组成及原理

    1.1、RL结构图:

    RL是一种智能体和环境之间不断试错的方法, 通过不断的交互以取得最大的累计期望奖励,它由环境, 智能体和奖励尺度三部分组成,见图:
    这里写图片描述

    在图中, 大脑部分代表智能体(Agent), 地球代表环境(Environment)
    执行过程: 智能体(Agent)通常从环境中获取一个OtO_{t}, 然后Agent根据OtO_{t}调整自身的策略做出一个行为(Action:AtA_{t})反馈给环境, 环境根据Agent的动作给予Agent一个奖励RtR_{t},经过这样,智能体和环境之间进行连续的交互学习,得到了一个{O,A,RO,A,R}的交互历史序列。通常历史序列由观测、行为、奖励三部分组成,被定义为:
    Ht=O1,A1,R1,,Ot,At,Rt H_{t} = O_{1},A_{1},R_{1},\dots, O_{t},A_{t},R_{t}
    同时状态被定义为函数f()f(\cdot)的映射: St=f(Ht)S_{t} = f(H_{t}),接下来将会对序列通过MDP进行描述:

    1.2、马尔科夫决策过程(MDP)

    马尔科夫决策过程是一个序列决策问题,它由很多的马尔科夫过程元组组成。 首先了解几个名词:
    马尔科夫性: 指系统的下一个状态St+1S_{t+1} 仅与当前状态 sts_{t}有关,表示为:
    P[St+1St]=P[St+1s1,s2,...,st](1)P[S_{t+1}|S_{t}] = P[S_{t+1}|s_{1},s_{2},...,s_{t}] \tag{1}
    ** 马尔科夫过程:** 它是一个二元组(S,P)(S, P), 其中SS为有限状态机,PP为状态转移概率。且状态转移概率矩阵为:

    P=[P11P1n....Pn1Pnn](2) P=\left[ \begin{matrix} P_{11} & \dots & P_{1n} \\ . & & . \\ . & & . \\ P_{n1} & \dots & P_{nn} \end{matrix} \right] \tag{2}
    举个例子说明一下(如图):如果给定状态转移概率矩阵P,即每个点到下一个点的状态转移概率,那么从Start出发到End结束存在多条马尔科夫链(多条路径),其中每个链上就是马尔科夫过程的描述。但马尔科夫过程中并不存在action和奖励。因此,从Start开始到end是一个序列决策问题,需要不断的选择路线,以取得最大收益。接下来是MDP

    **马尔科夫决策过程(MDP):** 通常情况马尔科夫决策过程用元组<$S,A,P,R,\gamma$>描述: $S$: 有限状态集 $A$:有限动作集 $P$:状态转移概率 $R$:回报函数 $\gamma$:折扣因子,用来计算累计回报。

    上述是MDP的组成,而我们关心的是它如何工作,继续前面的走方格例子,从Start开始,有两个行为(向右走,向南走),走不通的方向都有P=14P= \frac{1}{4}的概率且有不同的奖励,一直反复的走,直到走到End结束,在这个过程中会形成不同的序列,例如序列1:
    {(Start,Right,P,R1),(A,Right,P,R2),(B,South,P,R3),(E,South,P,R4),(End,South,P,R5)} \left\{(Start,Right,P,R1),(A,Right,P,R2),(B,South,P,R3),(E,South,P,R4), (End,South,P,R5)\right\}
    这只是其中一条路径,那从Start到End那条路劲带来的收益最大呢?就需要每一步进行决策,而决策就需要用到策略。下文继续:

    1.3、强化学习的目标及Agent的要素:

    目标: 根据环境状态序列,找到一套最优控制策略,以实现最大累计期望奖励。

    1.3.1 第一要素 ---- 策略

    那么什么是策略呢? 通常情况下被定义为是从状态到行为的一个映射,直白说就是每个状态下指定一个动作概率,这个可以是确定性的(一个确定动作),也可以是不确定性的。
    (1)非确定策略: 对于相同的状态,其输出的状态并不唯一,而是满足一定的概率分布,从而导致即使是处在相同的状态,也可能输出不同的动作,表示为:
    π(as)=P[At=aSt=s](3)\pi(a|s) = P[A_{t}=a|S_{t}=s] \tag{3}
    (2)确定行策略: 在相同的状态下,其输出的动作是确定的,表示为:
    a=π(s)(4)a = \pi (s) \tag{4}

    如果给定一个策略,就可以计算最大化累计期望奖励了,通常奖励分为及时奖励和长久累计期望奖励,
    **及时奖励:**实时反馈给Agent的奖励rtr_{t},举例:当玩具直升机根据当前的作态做出一个飞行控制姿势时,好坏会立即得到一个奖励。
    **累计期望奖励:**通常指一个过程的总奖励的期望,比如直升机从飞起到降落整个过程。
    通常累计期望奖励被定义为:
    Gt=R1+γR2+γ2R3++γk1Rk=k=0γkRt+k+1(5) G_{t} = R_{1}+\gamma R_{2}+\gamma^{2}R_{3}+\cdots+\gamma^{k-1}R_{k}=\sum_{k=0}^{}\gamma^{k}R_{t+k+1} \tag{5}

    假如在策略π\pi下,从前文的Start出发,则有不同的路径
    StartABEEndStartCDGEnd.... Start \rightarrow A \rightarrow B \rightarrow E \rightarrow End \\ Start \rightarrow C \rightarrow D \rightarrow G \rightarrow End \\ ....

    每个路径的累计回报GtG_{t}不同,且在随机策略下GtG_{t}是随机变量,但它们的期望是一个确定值,因此而被用作值函数的估计。

    1.3.2 第二要素 ---- 值函数

    当Agent采用某个策略π\pi时,累计回报服从一个分布,通常将状态S处的期望定义为** 状态值函数**,数学表示为:
    Vπ(s)=Eπ[R1+γR2+γ2R3++γk1RkSt=s](6) V_{\pi}(s) = E_{\pi}[R_{1}+\gamma R_{2}+\gamma^{2}R_{3}+\cdots+\gamma^{k-1}R_{k}|S_{t}=s] \tag{6}
    其中γ[0,1)\gamma \in [0, 1) 是折扣因子,用来估算未来对现在的影响,如果γ=0\gamma=0,即短视,只看当前的,不关注长期的回报。

    仅仅在状态值函数下求解期望奖励是不够的,我们还需要在某一个状态下,采取某个行为带来的期望回报。用状态-行为值函数衡量当前行为的好坏,其数学表达为:
    qπ(s,a)=Eπ[t=0γkRt+k+1St=s,At=a](7) q_{\pi}(s,a)=E_{\pi}[\sum_{t=0}^{\infty}\gamma^{k}R_{t+k+1}|S_{t}=s,A_{t}=a] \tag{7}

    为了能够计算在某个状态S下的值函数或者在状态S下采取行为的状态-行为值函数评估累计期望奖励,我们根据下图列出公式组:

    这里写图片描述
    Vπ(s)=aAπ(as)qπ(s,a)(8) V_{\pi}(s) = \sum_{a \in A} \pi(a|s)q_{\pi}(s, a) \tag{8}
    注:根据公式(7),从状态s处施加行为a有两种操作,在不同的策略下来估计未来的期望奖励,故采用求和均差得到公式(8),同时从第一幅图左下角得到公式(9),从第二幅图左下角得到公式(10)
    qπ(s,a)=Rsa+γaAPssavπ(s)(9) q_{\pi}(s, a) = R_{s}^{a}+\gamma\sum_{a \in A}P_{ss^{'}}^{a}v_{\pi}(s^{'}) \tag{9}
    vπ(s)=aAπ(as)qπ(s,a)(10) v_{\pi}(s^{'}) = \sum_{a^{'} \in A} \pi(a^{'}|s^{'})q_{\pi}(s^{‘}, a^{’}) \tag{10}
    将等式(9)代入等式(8),得到等式(11);将(10)代入(9)得到(12)
    vπ(s)=aAπ(as)(Rsa+γsSPssaVπ(s))(11) v_{\pi}(s) = \sum_{a \in A}\pi(a|s)\left( R_{s}^{a}+\gamma\sum_{s^{‘} \in S}P_{ss^{'}}^{a}V_{\pi}(s^{'}) \right) \tag{11}

    qπ(s,a)=Rsa+γsSPssaaAπ(as)qπ(s,a)(12) q_{\pi}(s, a) = R_{s}^{a}+ \gamma\sum_{s^{‘} \in S}P_{ss^{'}}^{a}\sum_{a \in A}\pi(a^{'}|s^{'})q_{\pi}(s^{'},a^{'}) \tag{12}
    由上文公式我们可以总结出:状态值函数和状态-行为值函数的Bellman方程:
    v(st)=Eπ[Rt+1+γv(st+1)]q(st,at)=Eπ[Rt+1+γq(st+1,at+1)(13) v(s_{t}) = E_{\pi}[R_{t+1}+\gamma v(s_{t+1})] \\ q(s_{t},a_{t}) = E_{\pi}[R_{t+1}+ \gamma q(s_{t+1},a_{t+1}) \tag{13}

    通常计算值函数的目的是为了构建学习从数据中得到最优策略,每个策略对应一个值函数,最优策略对应最优值函数。当且仅当:ππ\pi \geq \pi^{*} and Vπ(s)V(s)V_{\pi}(s)\geq V^{*}(s)时,最优状态值函数V(s)V^{*}(s)为所有策略中值函数最大的,表示为:
    v(s)=maxπvπ(s)(14) v^{*}(s) = \max\limits_{\pi}v_{\pi}(s) \tag{14}
    最优状态-行为值函数是所有策略中状态-行为值最大的,表示为:
    q(s,a)=maxπqπ(s,a)(15) q^{*}(s, a) =\max\limits_{\pi}q_{\pi}(s,a) \tag{15}

    同理得到(推导省略),最优的状态值函数和状态-行为值函数如下:
    Vπ(s)=maxaRsa+γsSPssaV(s)(16) V_{\pi}(s) = \max\limits_{a} R_{s}^{a}+\gamma\sum_{s^{‘} \in S}P_{ss^{'}}^{a}V^{*}(s^{'}) \tag{16}

    qπ(s,a)=Rsa+γsSPssamaxaq(s,a)(17) q_{\pi}(s, a) = R_{s}^{a}+ \gamma\sum_{s^{‘} \in S}P_{ss^{'}}^{a} \max\limits_{a^{'}}q^{*}(s^{'},a^{'}) \tag{17}

    最后,如果已知最优状态-行为值函数,最优策略可以直接通过最大化q(s,a)q^{*}(s,a)得到。
    KaTeX parse error: No such environment: equation at position 8: \begin{̲e̲q̲u̲a̲t̲i̲o̲n̲}̲ \pi^{*}(a|s) =…


    总结: 到目前为止,关于强化学习的序列问题和贝尔曼方程已经描述完毕,并且上文所有的均是针对小规模MDP过程的求解{在程序中怎么使用也没有讲解(实际编程单独用一节讲解)),且所有的序列都采用表的形式存储,但是针对大规模空间或者连续性动作空间的问题,由于空间存储资源浪费和检索速率低下而无法适用!接下来的三种方法则可以解决该问题,特别是TD方法。


    三、大规模MDP的三种解决方法

    注: 关于部分公式详细的推导过程不详解,具体参David课程或者参考文献[8]

    3.1 动态规划法(Dynamic progarmming)

    动态规划是一种在数学、管理科学、计算机科学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。它常常适用于有重叠子问题和最优子结构性质的问题,在解决子问题的时候,其结果通常需要存储起来被用来解决后续复杂问题。当问题具有下列特性时,通常可以考虑使用动态规划来求解:第一个特性是一个复杂问题的最优解由数个小问题的最优解构成,可以通过寻找子问题的最优解来得到复杂问题的最优解;子问题在复杂问题内重复出现,使得子问题的解可以被存储起来重复利用。
    马尔科夫决定过程(MDP)具有上述两个属性:Bellman方程把问题递归为求解子问题,价值函数就相当于存储了一些子问题的解,可以复用。因此可以使用动态规划来求解MDP。

    这里的规划一般包括两个步骤:“Prediction”和“Control

    • Prediction是指根据当前的MDP和策略输出一个当前策略下的值函数:
      ** ++Input:++ ** MDP<S,A,P,R,γS,A,P,R,\gamma>和策略π\pi
      ** ++ Output:++ ** VπV_{\pi}
    • Control是指根据给定MDP找到最优VV^{*}π\pi^{*}
      ** ++Input:++ ** MDP<S,A,P,R,γS,A,P,R,\gamma>
      ** ++Output: ++** VV^{*}π\pi^{*}
    3.1.1、策略评估

    在一个序列中每一步决策都需要一个策略,即每一步都有值函数。
    V1,V2,V3,V4,,VπV_{1},V_{2},V_{3},V_{4},\dots,V_{\pi}
    策略评估需要解决的问题是对给定的策略π\pi进行评估,找到:** optimal policy **, 在策略评估过程中,我们通常采用迭代法进行策略评估。
    ** 解决的方法 **:反向迭代应用状态值函数Bellman期望方程
    ** 具体过程 **:同步反向迭代,即在每次迭代过程中,对于第 k+1 次迭代,所有的状态s的价值用vs(s)v_{s}(s^{'}) 计算并更新该状态第 k+1 次迭代中使用的价值vk(S)v_{k}(S) ,其中ss^{'}是s的后继状态。此种方法通过反复迭代最终将收敛至 VπV_{\pi}
    Vk+1(s)=Rπ+γPπVk(s)(19) V^{k+1}(s) = R^{\pi}+\gamma P^{\pi}V^{k}(s) \tag{19}
    首先我们在一个给定的策略下迭代更新价值函数,为了能够优化策略,贪婪选取行为是一种比较常见的方法。
    π=greedy(Vπ)(20) \pi^{'} = greedy(V_{\pi}) \tag{20}
    基于给定策略的价值迭代最终收敛得到的策略就是最优策略,但通过一个回合的迭代计算价值联合策略改善就能找到最优策略不是普遍现象。通常,还需在改善的策略上继续评估,反复多次多次迭代。不过这种方法总能收敛至最优策略$ \pi^{*} $,接下来是策略迭代。

    3.1.2、策略迭代

    在当前策略上迭代计算V值,再根据V值贪婪地更新策略,如此反复多次,最终得到最优策略 π\pi^{*} 和最优状态价值函数 VV^{*}, 如下图:

    这里写图片描述
    上图是大神David Sliver的slide,

    3.1.3 值迭代

    问题:寻找最优策略π
    解决方法:从初始状态价值开始同步迭代计算,最终收敛,整个过程中没有遵循任何策略。
    注意: ++与策略迭代不同,在值迭代过程中,算法不会给出明确的策略,迭代过程其间得到的价值函数,不对应任何策略。++

    一个最优策略可以被分解为两部分:从状态s到下一个状态s’采取了最优行为 AA^{*} ;在状态s’时遵循一个最优策略。
    定理: 一个策略能够使得状态s获得最优价值,当且仅当:对于从状态s可以到达的任何状态s’,该策略能够使得状态s’的价值是最优价值:
    V(s)=maxaARsa+sSPssaV(s)(21) V^{*}(s) = \max\limits_{a \in A}R_{s}^{a}+ \sum\limits_{s^{'}\in S}P_{ss^{'}}^{a}V^{*}(s^{'}) \tag{21}
    接下来采用树的思想解释一下:

    价值迭代虽然不需要策略参与,但仍然需要知道状态之间的转移概率,也就是需要知道模型。

    ** 总结:**
    预测问题:在给定策略下迭代计算价值函数。控制问题:策略迭代寻找最优策略问题则先在给定或随机策略下计算状态价值函数,根据状态函数贪婪更新策略,多次反复找到最优策略;单纯使用价值迭代,全程没有策略参与也可以获得最优策略,但需要知道状态转移矩阵,即状态s在行为a后到达的所有后续状态及概率。使用状态价值函数或行为价值函数两种价值迭代的算法时间复杂度都较大,为 O(mn2)O(mn^{2})O(m2n2)O(m^{2}n^{2})

    3.2 蒙特卡罗法(Monte Calo)

    通过先前的讲解,我们明白了如何从理论上解决一个已知的MDP:通过动态规划来评估一个给定的策略,并且得到最优价值函数,根据最优价值函数来确定最优策略;也可以直接进行不基于任何策略的状态价值迭代得到最优价值函数和最优策略。接下来则是解决被认为是MDP、但却不掌握MDP具体细节的问题,也就是讲述如何直接从Agent与环境的交互来得得到一个估计的最优价值函数和最优策略。直白的说就是在给定的策略同时不清楚MDP细节的情况下,估计Agent会得到怎样的最终奖励。

    3.2.1 蒙特卡罗Introduction

    蒙特卡罗思想: 当所求解问题是某种随机事件出现的概率,或者是某个随机变量的期望值时,通过某种“实验”的方法,以这种事件出现的频率估计这一随机事件的概率,或者得到这个随机变量的某些数字特征,并将其作为问题的解。
    ** MC强化学习:** 指在不清楚MDP状态转移及即时奖励的情况下,直接从经历完整的Episode来学习状态价值,通常情况下某状态的价值等于在多个Episode中以该状态算得到的所有收获的平均。
    ** MC强化学习特点:** 不基于模型本身,直接从经历过的Episode中学习,必须是完整的Episode,使用的思想就是用平均收获值代替价值。理论上Episode越多,结果越准确。

    3.2.1 MC策略评估

    前文已经讲了关于策略评估,其实质是求解值函数,在MC中同样需要一系列完整的Episode(与后文的TD不同)去求解当前策略下的值函数。
    在一个特定的策略π\pi下,完整的Episode的序列表示如下:
    S1,A1,R2,S2,A2,R3,,St,At,Rt+1,,Skπ S_{1},A_{1},R_{2},S_{2},A_{2},R_{3},\cdots,S_{t},A_{t},R_{t+1},\cdots,S_{k} \sim \pi
    那么,在t时刻状态StS_{t}的收获我们可以描述为:

    Gt=Rt+1+γRt+2++γTRT(22) G_{t} = R_{t+1}+\gamma R_{t+2}+\cdots+\gamma^{T}R_{T} \tag{22}
    其中T表示为终止状态,根据前文对值函数的描述,同理状态值函数为:
    Vπ(s)=Eπ[GtSt=s](23) V_{\pi}(s)=E_{\pi}[G_{t}|S_{t}=s] \tag{23}
    在给定一个策略,使用一系列完整Episode评估某一个状态s时,对于每一个Episode,仅当该状态第一次出现时列入计算:
    ** 第一次出现时列入计算:**
    (1)状态出现的次数+1:
    N(s)N(s)+1(24) N(s) \leftarrow N(s) + 1 \tag{24}
    (2)总的收获值更新:
    S(s)S(s)+Gt(25) S(s) \leftarrow S(s) + G_{t} \tag{25}
    (3)状态s的价值:
    V(s)=S(s)/N(s)(26) V(s) = S(s) / N(s) \tag{26}
    (4)当$ N(s) \rightarrow \infty 时, V(s) \rightarrow v_{\pi}(s)$

    每次访问蒙特卡洛策略评估
    在给定一个策略,使用一系列完整Episode评估某一个状态s时,对于每一个Episode,状态s每次出现在状态转移链时,计算的具体公式与上面的一样,但具体意义不一样。
    (1)状态出现的次数加1:同公式(24)
    (2)总的收获值更新:同公式(25)
    (3)状态s的价值:同公式(26)
    (4)当 N(s)V(s)vπ(s)N(s) \rightarrow \infty 时, V(s) \rightarrow v_{\pi}(s)

    提到了在实际操作时常用的一个实时更新均值的办法,使得在计算平均收获时不需要存储所有既往收获,而是每得到一次收获,就计算其平均收获。

    理论公式如下:

    KaTeX parse error: No such environment: align* at position 8: \begin{̲a̲l̲i̲g̲n̲*̲}̲ \mu_{k} &=\fra…

    因此根据以下伪代码进行MC累计更新: **
    对于一系列Episodes中的每一个: S1,A1,R2,...,STS_{1},A_{1},R_{2},...,S_{T}
    对于Episode里的每一个状态 StS_{t}有一个收获$ G_{t}$ ,每碰到一次$ S_{t}$ ,使用下式计算状态的平均价值 GtG_{t}
          $N(S_{t}) \leftarrow N(S_{t})+1 $
          $ V(s_{t}) \leftarrow V(s_{t})+ \frac{1}{N(s_{t})}[G_{t}-V(s_{t})]$
    非静态问题时,使用这个方法跟踪一个实时更新的平均值是非常有用的,可以扔掉那些已经计算过的Episode信息。此时可以引入参数 $\alpha $来更新状态价值:
          $V(S_{t}) \leftarrow V(S_{t})+\alpha (G_{t}-V(S_{t})) $

    3.3 时间差分学习(TD-learning)

    时序差分学习简称TD学习,它的特点如下:和蒙特卡洛学习一样,它也从Episode学习,但不需要了解模型本身;且它可以学习不完整的Episode,通过自身的引导(bootstrapping,自举)猜测Episode的结果,同时持续更新这个猜测。

    目标:从策略π\pi中学习VπV_{\pi}
    过程:通过估计量: Rt+1+γV(St+1)R_{t+1}+\gamma V(S_{t+1}), 更新策略π\pi,依据公式:
    V(St)V(St)+α[Rt+1+γV(St+1)V(St)](28) V(S_{t}) \leftarrow V(S_{t})+\alpha[R_{t+1}+\gamma V(S_{t+1})-V(S_{t})] \tag{28}
    其中: $TD-error = [R_{t+1}+\gamma V(S_{t+1})-V(S_{t})] $


    DP、MC、TD三种方法对比:

    • 1、DP基于模型; MC、TD基于无模型
    • 2、DP采用bootstrapping(自举), MC采用采样,TD采用bootstrapping+采样
    • 3、DP用后继状态的值函数估计当前值函数,MC利用经验平均估计状态的值函数,TD利用后继状态的值函数估计当前值函数
    • 4、MC和TD都是利用样本估计值函数,其中MC为无偏估计,TD为有偏估计
    • 5、最明显的就是下图的值函数的计算方法的不同

    这里写图片描述


    至此,基础RL知识已经讲完,上文对所有的序列信息均通过表的形式存储,这是一种比较对于小状态空间的搞笑解决方法,但是围棋有107010^{70}(非常大)个状态空间,机械臂连续控制等问题无法在表中存储,这些问题总结为两个缺点:

    • 表空间特别大,存储资源的浪费;
    • 由于表特别大,导致检索一次查询效率特别低。

    因此不得不采用一中解决上述缺点的方法进行强化学习,目前比较实用的就是近似价值函数方法.

    四、近似价值函数

    近似值函数:从字面上看就是无限逼近真实值函数(状态值函数Vπ(s)V_{\pi}(s)、 状态-行为值函数Qs,qQ_{s,q})的意思,用数学表示为下面公式(29)[未标注]:

    V^(s,w)Vπ(s) \hat{V}(s,w) \approx V_{\pi}(s)

    Q^(s,a,w)Qπ(s,a) \hat{Q}(s,a,w) \approx Q_{\pi}(s,a)
    其中我们的目的就是找到合适的 ww 来近似值函数,ww可以是参数化逼近和非参数化逼近,非参数可以理解为通过核函数等方式,参数化后文会讲解。基于此,根据强化学习的输入,输出被表示为三种近似方法,如图:

    这里写图片描述

    • 图(1)表示根据状态本身,输出这个状态的近似价值;
    • 图(2)表示根据状态行为对,输出状态行为对的近似价值;
    • 图(3)表示根据状态本身,输出一个向量,向量中的每一个元素是该状态下采取一种可能行为的价值。

    我们可以将上述的三个正方形盒子视为黑盒子,它就是一个函数近似器,可以将其想象为任何东西,比如l它是一个** 神经网络、决策树、泰勒多项式、线性函数、Fourier/Wavelet base等 **。或者为一切可描述或者无法描述的东西。本文讲介绍神经网络,其他其中方法后续将单独做详解。

    4.1 递增方法 Incremental Methods

    本部分讲述采用神经网络方法进行近似值函数,因为神经网络可以拟合任何一个函数。神经网络j结构如图,对于反向传播更新方式此处不讲:

    这里写图片描述
    我们定义一个目标函数J(w)J(w)(该函数可微),ww为vector, 那么目标函数关于ww的梯度表示为:
    wJ(w)=[J(w)w1...J(w)wn](30) \nabla_{w}J(w)=\left[ \begin{matrix} \frac{\partial J(w)}{\partial w_{1}} \tag{30}\\ . \\ . \\ . \\ \frac{\partial J(w)}{\partial w_{n}} \end{matrix} \right]
    为了能够达到 minJ(w)\min J(w) ,只需在梯度下降或者上身的方向调整WW,使其达到局部最小值
    w=12αwJ(w)(31) \triangle w = -\frac{1}{2}\alpha \nabla_{w}J(w) \tag{31}
    ** 目标**: 找到参数ww,最小化状态值函数Vπ(s)V_{\pi}(s) 和近似器 V^(sw)\hat{V}(s,w)之间的均方差和状态-行为值函数Qπ(s,a)Q_{\pi}(s,a)和近似器 Q^(s,a,w)\hat{Q}(s,a,w)之间的的均方差。
    以状态值函数为例:定义目标函数:
    J(w)=Eπ[(Vπ(s)V^(s,w))2](32) J(w) = E_{\pi}[(V_{\pi}(s)-\hat{V}(s,w))^{2}] \tag{32}
    通过梯度下降找到当地最小值:
    KaTeX parse error: No such environment: align* at position 8: \begin{̲a̲l̲i̲g̲n̲*̲}̲ \triangle w &…
    其实,目前所列的公式都不能直接用于强化学习(看了这么多数学公式,尽然说没用), 因为公式里都有一个实际价值函数 vπ(S)v_{\pi}(S),而强化学习没有监督数据,因此不能直接使用上述公式。对于只有即时奖励,没有监督数据的强化学习。我们需要找到能替代vπ(S)v_{\pi}(S)的目标值,以便来使用监督学习的思路学习到近似函数的参数。

    因此对于强化学习的两个基本问题之一:** Prediction**
    ** 方法:**
    (1)对于MC,target是返回值GtG_{t}, 即:
    w=α(GtV^(s,w)wV^(s,w))(34) \triangle w = \alpha(G_{t}-\hat{V}(s,w)\nabla_{w}\hat{V}(s,w)) \tag{34}
    (2) 对于TD(0),target是TD-target Rt+1+γV^(St+1,w)R_{t+1}+\gamma\hat{V}(S_{t+1},w),即:
    w=α(Rt+1+γV^(St+1,w)V^(s,w)wV^(s,w))(35) \triangle w = \alpha(R_{t+1}+\gamma\hat{V}(S_{t+1},w)-\hat{V} (s,w)\nabla_{w}\hat{V}(s,w)) \tag{35}

    因此对于强化学习的两个基本问题之一:** Control**
    那么如何把近似函数引入到控制过程中呢?我们需要能够近似状态-行为值函数对价值函数近似而不是仅针对状态价值函数近似。为什么呢?
    因为** Model-free控制需要满足两个条件:**

    • 1、在模型未知的条件下无法知道当前状态的所有后续状态,进而无法确定在当前状态下采取怎样的行为更合适。通常使用状态行为对下的价值Q(s,a)来代替状态价值, 即:π(s)=argmaxaAQ(S,a)\pi^{'}(s) = \arg\max\limits_{a\in A}Q(S,a)
    • 2、探索(Exploration):即使满足条件(1),至少还存在一个问题,即当我们每次都使用贪婪算法来改善策略的时候,将很有可能由于没有足够的采样经验而导致产生一个并不是最优的策略,因此需要不停的探索(Exploration)新行为,即:π=ϵ\pi = \epsilon-greedy(Qw)greedy(Q_{w})

    这里写图片描述
    从一系列参数开始,得到一个近似的状态-行为值函数,在Ɛ-greedy执行策略下产生一个行为,执行该行为得到一个即时奖励,以此数据计算目标值,进行近似函数参数的更新。再应用这个策略得到后续的状态和对应的目标值,每经历一次状态就更新依次参数,如此反复进行策略的优化,同时逼近最优价值函数。

    因此对于** 策略评估 **,即近似策略评估:
    q^(s,a,w)qπ(s,a)(36)\hat{q}(s,a,w) \approx q_{\pi}(s,a) \tag{36}

    策略改善: 采用Ɛ-greedy

    状态-行为值函数的近似过程类似与状态值函数(此处不描述,直接给结论):

    w=α(qπ(s,q)q^(s,a,w))wq^(s,a,w)(37) \triangle w = \alpha(q_{\pi}(s,q)-\hat{q}(s,a,w))\cdot \nabla_{w}\hat{q}(s,a,w) \tag{37}

    至此,第一篇结束!

    第二篇《深度强化学习及算法讲解》

    声明:
    1 本文内容均属原创,受知识水平有限,如有错误之处,请联系作者以便于修改纠正.
    2 本文所有参考他人论文, 书籍,知识栏目, 图片等一切有关知识均在Blog末尾以引用格式进行标注, 再次表示致谢. 如有他人内容未标明引用的请联系本文作者,以添加引用,在此表示歉意!

    参考文献:

    [1]. Richard S.Sutton and Andrew G. Barto,Reinforcement learning: An Introduction,second edition.2017.
    [2]. Lucian Busontu et al, Reinforcement learning and dynamic programming using function approximators.
    [3]. 郭宪 方勇纯, 深入浅出强化学习:原理入门
    [4]. Howard M.Schwartz 连晓峰(译), 多智能体机器学习:强化学习方法
    [5]. David Sliver, Introduction to Reinforcement learning
    (UCL:https://www.youtube.com/channel/UCP7jMXSY2xbc3KCAE0MHQ-A)
    [6]. 阿里技术, 从虚拟世界走进现实应用,强化学习在阿里的技术演进与业务创新.
    [7]. Deep Reinforcements Learnin- An Overview()
    [8].https://zhuanlan.zhihu.com/reinforce
    [9]. https://mp.weixin.qq.com/s/aAHbybdbs_GtY8OyU6h5WA##
    [10].https://www.youtube.com/watch?v=W_gxLKSsSIE&list=PL5nBAYUyJTrM48dViibyi68urttMlUv7e
    [11]. https://www.youtube.com/watch?v=CIF2SBVY-J0

    展开全文
  • 《Accelerated methods for deep reinforcement learning》论文解读 ...目前这块的研究成果并不是特别多,但,深度强化学习大神Pieter Abbeel发表了深度强化学习的加速方法,他从整体上提出了一个...
  • 深度强化学习

    2021-07-03 09:56:30
    深度强化学习14.1 强化学习问题14.1.1 强化学习定义14.1.2 马尔可夫决策过程14.1.3 强化学习的目标函数14.1.4 值函数14.1.5 深度强化学习14.2 基于值函数的学习方法14.2.1 动态规划算法14.2.2 蒙特卡罗方法14.2.3 ...
  • 利用出租车司机经验,提出约束深度强化学习算法(CDRL)在线计算不同时间段内OD间最快路线。首先描述了路段经验数据库(ERSD)的提取; 然后介绍了CDRL方法,包括可选择约束路段生成和深度Q-lear-ning算法两个阶段,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 12,354
精华内容 4,941
关键字:

深度强化学习路径规划