[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

CN115016499B - 一种基于sca-ql的路径规划方法 - Google Patents

一种基于sca-ql的路径规划方法 Download PDF

Info

Publication number
CN115016499B
CN115016499B CN202210792993.5A CN202210792993A CN115016499B CN 115016499 B CN115016499 B CN 115016499B CN 202210792993 A CN202210792993 A CN 202210792993A CN 115016499 B CN115016499 B CN 115016499B
Authority
CN
China
Prior art keywords
value
action
sca
state
algorithm
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Active
Application number
CN202210792993.5A
Other languages
English (en)
Other versions
CN115016499A (zh
Inventor
朱冰
李响
赵健
黄殷梓
孙一
姜景文
禚凇瑀
黄沐寒
薛越
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Jilin University
Original Assignee
Jilin University
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Jilin University filed Critical Jilin University
Priority to CN202210792993.5A priority Critical patent/CN115016499B/zh
Publication of CN115016499A publication Critical patent/CN115016499A/zh
Application granted granted Critical
Publication of CN115016499B publication Critical patent/CN115016499B/zh
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Classifications

    • GPHYSICS
    • G05CONTROLLING; REGULATING
    • G05DSYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
    • G05D1/00Control of position, course, altitude or attitude of land, water, air or space vehicles, e.g. using automatic pilots
    • G05D1/02Control of position or course in two dimensions
    • G05D1/021Control of position or course in two dimensions specially adapted to land vehicles
    • G05D1/0212Control of position or course in two dimensions specially adapted to land vehicles with means for defining a desired trajectory
    • G05D1/0221Control of position or course in two dimensions specially adapted to land vehicles with means for defining a desired trajectory involving a learning process
    • GPHYSICS
    • G05CONTROLLING; REGULATING
    • G05DSYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
    • G05D1/00Control of position, course, altitude or attitude of land, water, air or space vehicles, e.g. using automatic pilots
    • G05D1/02Control of position or course in two dimensions
    • G05D1/021Control of position or course in two dimensions specially adapted to land vehicles
    • G05D1/0212Control of position or course in two dimensions specially adapted to land vehicles with means for defining a desired trajectory
    • G05D1/0223Control of position or course in two dimensions specially adapted to land vehicles with means for defining a desired trajectory involving speed control of the vehicle
    • GPHYSICS
    • G05CONTROLLING; REGULATING
    • G05DSYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
    • G05D1/00Control of position, course, altitude or attitude of land, water, air or space vehicles, e.g. using automatic pilots
    • G05D1/02Control of position or course in two dimensions
    • G05D1/021Control of position or course in two dimensions specially adapted to land vehicles
    • G05D1/0268Control of position or course in two dimensions specially adapted to land vehicles using internal positioning means
    • G05D1/0274Control of position or course in two dimensions specially adapted to land vehicles using internal positioning means using mapping information stored in a memory device
    • YGENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
    • Y02TECHNOLOGIES OR APPLICATIONS FOR MITIGATION OR ADAPTATION AGAINST CLIMATE CHANGE
    • Y02TCLIMATE CHANGE MITIGATION TECHNOLOGIES RELATED TO TRANSPORTATION
    • Y02T10/00Road transport of goods or passengers
    • Y02T10/10Internal combustion engine [ICE] based vehicles
    • Y02T10/40Engine management systems

Landscapes

  • Engineering & Computer Science (AREA)
  • Radar, Positioning & Navigation (AREA)
  • Aviation & Aerospace Engineering (AREA)
  • Remote Sensing (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Automation & Control Theory (AREA)
  • Feedback Control In General (AREA)

Abstract

本发明公开了一种基于SCA‑QL的路径规划方法,其方法为:第一步、获取真实环境信息,包括智能体在真实环境下的起点位置和终点位置信息、障碍物位置信息;第二步、根据真实环境信息,建立用于智能体训练的仿真环境;第三步、在仿真环境中运行SCA‑QL算法对智能体进行训练求解最优路径:其中,通过改进正余弦算法的方式对建立的Q值表进行初始化,在此基础上基于Q‑learning方法训练强化学习模型,求解最优路径。有益效果:减少了Q‑learning方法在训练最初阶段无目的、完全随机的搜索过程中大量无效迭代,本方法具有更快的收敛速度和更准确的路径规划结果,提高了智能体面对复杂场景下的路径规划效率。

Description

一种基于SCA-QL的路径规划方法
技术领域
本发明涉及一种路径规划方法,特别涉及一种基于SCA-QL的路径规划方法。
背景技术
目前,随着智能化技术的发展,以智能汽车和智能机器人为代表的智能体正被应用于更加复杂多样的场景,路径规划方法是移动智能体重要的核心技术之一。
当前路径规划方法可以分为三大类:基于搜索的方法、基于采样的方法和基于群体智能的方法。其中基于搜索的方法主要将状态空间通过确定的方式离散,然后通过启发式搜索算法搜索可行解,这类算法具有解析完备性甚至最优性,代表算法Dijkstra算法、A*算法、D*算法等;基于采样的方法的基本思路是通过对状态空间均匀随机采样来构建一个连通图,当初始、目标状态都在图中即解决了规划问题,随机采样的算法不需要对状态空间进行显式建模,代表算法有PRM算法、RRT算法等;基于群体智能的方法通过模拟自然界生物行为方式进行路径规划,较为经典的有蚁群算法、遗传算法等。
近年来,强化学习方法被广泛应用于各个领域,用以求解智能系统在环境中的最优行为策略。其特点可以通过智能体与环境的交互的方式使智能体进行学习,最终学习到最优的序贯决策。Q-learning算法是一种被广泛应用的强化学习算法,其特点是建立表示智能体的状态和动作转移关系的Q值,形成Q值表,在智能体在环境的探索过程中对其进行奖惩更新Q值表,使智能体在学习过后可以针对不同状态给出最优动作使得长期奖励最大化。
Q-learning算法常被用来解决移动智能体路径规划问题,其通过智能体对有障碍物和目标的环境交互进行智能体学习,完成最优路径的规划。当智能体对环境的状态有完整认知时,Q-learning算法往往会得到最优的路径规划结果。但是当环境更加复杂时,智能体会由于缺少目标的先验信息而陷入搜索目标的循环之中难以收敛得到结果。此外,针对复杂环境Q-learning算法可能会因对已有学习知识过度贪婪而陷入局部最优解,降低贪婪度则又会导致收敛速度大幅下降。因此需要对Q-learning算法进行改进以提高其针对复杂环境的收敛速度和结果准确度。
发明内容
本发明的主要目的是为了对Q-learning算法进行改进以提高其针对复杂环境的收敛速度和结果准确度,而提供的一种基于SCA-QL的路径规划方法。
本发明提供的基于SCA-QL的路径规划方法,其方法包括如下步骤:
第一步、获取真实环境信息,包括智能体在真实环境下的起点位置和终点位置信息、障碍物位置信息;
第二步、根据真实环境信息,建立用于智能体训练的仿真环境;仿真环境建立过程包括:根据真实环境信息建立环境模型,利用栅格法对环境模型进行划分,网格位置基于笛卡尔坐标进行标记,在环境模型中确定起点位置与终点位置坐标对应的栅格并标记,同样的,在环境模型中根据障碍物位置信息对其对应的栅格进行标记;
第三步、在仿真环境中运行SCA-QL算法对智能体进行训练求解最优路径:其中,通过改进正余弦算法的方式对建立的Q值表进行初始化,在此基础上基于Q-learning方法训练强化学习模型,求解最优路径。
第三步中的SCA-QL算法是一种改进强化学习方法,主要步骤如下:
步骤一、初始化参数空间,设定超参数;初始化参数空间过程中,参数空间具体指SCA-QL算法中重要变量的集合,其初始化过程包括算法对集合的创建过程和初始条件的设定过程;
参数空间至少包括:状态空间S,表示智能体可能所处的状态的集合;动作空间A,表示智能体执行的动作的集合;奖励函数空间R,表示对于指定的状态和动作下,奖励函数的期望的集合;动作价值空间Q-table,表示对于指定的状态和动作下,智能体动作带来的累积价值的期望的集合;种群空间X,表示SCA算法的可迭代个体的集合;
超参数至少包括:贪婪度ε,影响智能体决策过程中对于学习信息的依赖程度,具体表示智能体决策过程选择最大Q值的动作执行的概率;学习率α,影响智能体对于最具动作价值的动作的学习速度;衰减系数γ,影响在考虑未来动作奖励对当前动作价值影响时的衰减效益;最大迭代步数Max_Iteration,具体表示在算法内各个循环阶段的最大的迭代步数,用以中止算法及避免无限循环;
步骤二、随机生成SCA初始种群;随机生成SCA初始种群过程,表示在种群空间X中,借助随机方法产生数个可迭代个体,其中,每个可迭代个体的都表示为状态空间S中的一个状态,并以与栅格地图相同维度的方式对其位置坐标进行表示,可迭代个体应满足的要求为:每个产生的可迭代个体的位置坐标不能够超出栅格地图范围;每个产生的可迭代个体坐标不能够处于障碍物栅格内,针对不满足要求生成的可迭代个体,重新采用相同随机生成方法进行生成,直到满足所述条件或达到最大迭代步数,对于到达最大迭代步数仍无法完成可迭代个体生成的状况,重新调整SCA种群维度;
步骤三、对当前种群每个个体位置Q值进行计算更新;在Q-learning之前对SCA种群进行Q值的初始化和迭代,所述Q值迭代过程利用时序差分,即TD学习方法,TD学习指根据下一时间步的值函数估计当前时间步的值函数,具体的估计公式如下:
V(s)←V(s)+α(Rt+1+γV(s′)-V(s)) (1)
其中,V(s)表示状态s下的状态值函数,Rt+1表示下一时刻状态s'对应的奖励,Rt+1+γV(s′)称为TD目标,δt=Rt+1+γV(s′)-V(s)称为TD偏差;
针对Q-learning方法可迭代个体根据公式(1)进行Q值的迭代,具体如下:
Q(s,a)←Q(s,a)+α[Rt+1+γmaxa′Q(s′,a′)-Q(s,a)] (2)
其中,Q(s,a)表示状态s下某时刻的动作a的动作价值,maxa′Q(s′,a′)表示下一时刻状态s'下具有最大动作价值的动作a'对应的Q值;
步骤四、确定当前种群内的最优个体;对当前阶段种群内全部个体的Q值进行搜索,将具有最大Q值的个体标记已知最优个体;
步骤五、对SCA算法参数r1、r2、r3、r4进行更新;SCA算法基于SCA种群进行优化,使用基于正弦和余弦函数的数学模型向外波动或朝着最佳方向前进,算法参数r1、r2、r3、r4用于在不同的优化阶段中自适应调整搜索空间,具体如下:
参数r1指示下一位置区域或移动方向,下一位置区域或移动方向在当前解与当前阶段最优解之间,或在当前解与当前阶段最优解之外;
参数r2定义了根据参数r1指示的方向上运动的距离;
参数r3影响优化目标的权重,即加强或淡化当前阶段最优解在运动距离上的影响;
参数r4随机对使用正弦公式或余弦公式进行选择;
参数r2、r3、r4的更新过程指在一定范围内进行随机选取,参数r1的更新过程使用公式如下:
其中,a为常数,t为当前代数,T为最大迭代数;
步骤六、利用SCA迭代公式基于当前种群最优解更新种群;SCA迭代公式如下:
其中,表示第i个维度上第t代个体的位置,Pi t表示第i个维度上第t代个体最优解的位置;
步骤七、重复步骤三至步骤六,直至达到设定迭代步数;
步骤八、智能体根据Q-learning方法进行动作选择;选择过程动作价值函数最大策略,具体的动作选择策略公式如下:
其中,a*(s)表示在s状态下的最优动作;
步骤九、计算Q值并更新Q值表;Q值表是由状态s与动作a作为基底关于Q值的向量空间,Q值表的更新包括Q值的迭代和新状态s'的添加过程,Q值的迭代依据步骤八确定的动作估计下一状态并使用贝尔曼方程计算,具体Q值迭代公式如下:
Q(s,a)←Q(s,a)+α[Rt+1+γmaxa′Q(s′,a′)-Q(s,a)] (6);
步骤十、智能体进行状态转移;状态转移过程依据步骤八进行的动作选择执行,具体状态转移公式如下:
st=st+1 (7)
步骤十一、重复步骤八至步骤十,直到收敛条件或者达到设定迭代步数,重复循环过程,得到训练完成的Q值表,智能体从起点位置出发,重复动作选择过程与状态转移过程直到终点位置,经过路径即为规划得到的最优路径,投影至真实环境即完成了路径规划过程。
本发明的有益效果:
本发明提供的基于SCA-QL的路径规划方法中使用SCA方法生成可迭代种群,利用种群对环境的探索进行Q值的初始化,然后基于Q-learning方法进行智能体路径规划。本方法相较于传统的Q-learning算法使用SCA方法进行初始化,减少了Q-learning方法在训练最初阶段无目的、完全随机的搜索过程中大量无效迭代,本方法具有更快的收敛速度和更准确的路径规划结果,提高了智能体面对复杂场景下的路径规划效率。
附图说明
图1为本发明所述的路径规划方法整体流程示意图。
图2为本发明所述的方法中建立虚拟环境示意图。
图3为本发明所述的SCA方法原理示意图。
具体实施方式
请参阅图1至图3所示:
本发明提供的基于SCA-QL的路径规划方法,具体包括如下步骤:
第一步、获取真实环境信息,包括智能体在真实环境下的起点位置和终点位置信息、障碍物位置信息;
第二步、根据所述真实环境信息,建立用于智能体训练的仿真环境;
第三步、在仿真环境中运行SCA-QL算法对智能体进行训练求解最优路径:其中,通过改进正余弦算法(SineCosineAlgorithm,SCA)的方式对建立的Q-table进行初始化,在此基础上基于Q-learning方法训练强化学习模型,求解最优路径。
第一步中真实环境信息获取可以基于搭载融合感知系统的地图车进行定位与地图构建得到,也可以基于无人机采集图像处理得到。本实例中以二维路径规划任务为例,选择无人机图像采集方案作为具体实施方式。针对无人机采集图像进行灰度化后,采用Canny算法对所述图像进行平滑去噪提取图像内障碍物边界,下一步进行霍夫变换处理所获图像边界,将笛卡尔空间内图像转换至霍夫空间进行直线和圆提取构成障碍物边界。
第二步中的仿真环境建立过程包括:根据所述的真实环境信息建立环境模型,利用栅格法对所述环境模型进行划分,网格位置基于笛卡尔坐标进行标记,在环境模型中确定起点位置与终点位置坐标对应的栅格并标记,同样的,在环境模型中根据障碍物位置信息对其对应的栅格进行标记。
具体的,本实例中建立仿真环境中,智能体位置根据其质心简化至一个点表示,障碍物位置由其障碍物边界所围成图形覆盖的区域表示。本实例以二维路径规划任务为例,建立维度为100*100的栅格对环境模型进行划分,每个栅格用于SCA-QL算法中表示该位置的状态,栅格位置基于笛卡尔坐标进行标记,具体表示为(x,y)。创建关于栅格位置坐标的矩阵Grid(x,y)用于表示各个栅格的状态,矩阵Grid维度与栅格维度一致,为100*100。栅格状态包含障碍物占用位置、空闲位置、终点位置、起点位置,根据各栅格状态对其Grid矩阵进行初始化赋值,例如位置(x1,y1)为空闲位置,则Grid(x1,y1)=0,具体栅格状态赋值规则如下表:
表1栅格状态Grid矩阵赋值规则
第三步中的SCA-QL方法是一种改进强化学习方法,主要步骤如下:
步骤一、初始化参数空间,设定超参数;
步骤二、随机生成SCA初始种群;
步骤三、对当前种群每个个体位置Q值进行计算更新;
步骤四、确定当前种群内的最优个体;
步骤五、对SCA算法参数r1、r2、r3、r4进行更新;
步骤六、利用SCA迭代公式基于当前种群最优解更新种群;
步骤七、重复步骤三至步骤六,直至达到设定迭代步数;
步骤八、智能体根据Q-learning方法进行动作选择;
步骤九、计算Q值并更新Q-table;
步骤十、智能体进行状态转移;
步骤十一、重复步骤八至步骤十,直到收敛条件或者达到设定迭代步数。
步骤一中参数空间具体指SCA-QL算法中重要变量的集合,其初始化过程包括算法对所述集合的创建过程和初始条件的设定过程。
参数空间至少包括:状态空间S,表示智能体可能所处的状态的集合;动作空间A,表示智能体可能执行的动作的集合;奖励函数空间R,表示对于指定的状态和动作下,奖励函数的期望的集合;动作价值空间Q-table,表示对于指定的状态和动作下,智能体动作带来的累积价值的期望的集合;种群空间X,表示SCA算法的可迭代个体的集合。
具体的,本实例对状态空间S初始化过程为创建空的状态空间S:
S=[]
其中,S空间内数据格式为栅格坐标(x,y),数据随循环过程填充至S空间用于记录智能体经过的位置。
具体的,本实例对动作空间A初始化过程为创建不可变动作空间A:
A=['top','bottom','left','right','topleft','topright','bottomleft','bottomright']
其中,A空间内提供智能体可执行的动作,用于引导智能体的行为评估和状态转移。
具体的,本实例对奖励函数空间R初始化过程为创建奖励函数空间R并进行赋值:
其中,R空间为2*u*v维张量,u,v表示栅格横纵向维度,本实例中u,v均为100。对每个栅格坐标均进行奖励函数赋值,本实例中对各类型栅格奖励赋值规则如下表:
表2栅格状态Grid矩阵赋值规则
本实例对动作价值空间Q-table初始化过程为创建空的动作价值空间Q-table:
Q-table=[]
其中,Q-table空间格式为栅格坐标(x,y)、动作a为基底关于Q值的向量空间,数据随循环过程更新至Q-table空间用于进行后续动作选择。更新后的Q-table如下:
其中,m为智能体历经的状态个数,n为智能体可能执行的动作个数,本实例中n取8,得到每一经历的状态下智能体执行各动作的Q值矩阵Q-table。
具体的,本实例针对二维路径规划问题,对种群空间X维度设定如下:
其中N表示种群个体数,种群内每个个体代表栅格地图中的一个位置。
超参数至少包括:贪婪度ε,影响智能体决策过程中对于已许学习信息的依赖程度,具体表示智能体决策过程选择最大Q值的动作执行的概率;学习率α,影响智能体对于最具动作价值的动作的学习速度;衰减系数γ,影响在考虑未来动作奖励对当前动作价值影响时的衰减效益;最大迭代步数max_Iteration,具体表示在算法内各个循环阶段的最大的迭代步数,本实例中选取为100,用以中止算法及避免无限循环。
步骤二中随机生成SCA初始种群过程,表示在种群空间X中,借助随机方法产生多个可迭代个体。其中,每个可迭代个体的都应表示为状态空间S中的一个状态,并以与栅格地图相同维度的方式对其位置坐标进行表示。所述可迭代个体应满足如下要求:每个产生的可迭代个体的位置坐标不能够超出栅格地图范围;每个产生的可迭代个体坐标不能够处于障碍物栅格内。针对于不满足所述要求生成的可迭代个体,应重新采用相同随机生成方法进行生成,直到满足所述条件或达到最大迭代步数,对于到达最大迭代步数仍无法完成可迭代个体生成的状况,应重新调整SCA种群维度。
步骤三中在Q-learning之前对所述的SCA种群进行Q值的初始化和迭代。Q值迭代过程利用时序差分(TD)学习方法,TD学习指根据下一时间步的值函数估计当前时间步的值函数,具体的估计公式如下:
V(s)←V(s)+α(Rt+1+γV(s′)-V(s)) (1)
其中,V(s)表示状态s下的状态值函数,Rt+1表示下一时刻状态s'对应的奖励,Rt+1+γV(s′)称为TD目标,δt=Rt+1+γV(s′)-V(s)称为TD偏差。
进一步的,针对Q-learning方法可迭代个体根据公式(1)进行Q值的迭代:
Q(s,a)←Q(s,a)+α[Rt+1+γmaxa′Q(s′,a′)-Q(s,a)] (2)
其中,Q(s,a)表示状态s下某时刻的动作a的动作价值,maxa′Q(s′,a′)表示下一时刻状态s'下具有最大动作价值的动作a'对应的Q值。
步骤四对当前阶段种群内全部个体的Q值进行搜索,将具有最大Q值的个体标记已知最优个体。
步骤五对SCA算法参数r1、r2、r3、r4进行更新。SCA算法基于SCA种群进行优化,使用基于正弦和余弦函数的数学模型向外波动或朝着最佳方向前进。所述算法参数r1、r2、r3、r4用于在不同的优化阶段中自适应调整搜索空间。
参数r1指示下一位置区域或移动方向,下一位置区域或移动方向可能在当前解与当前阶段最优解之间,也可能在二者之外;参数r2定义了根据参数r1指示的方向上运动的距离;参数r3影响优化目标的权重,即加强或淡化当前阶段最优解在运动距离上的影响;参数r4随机对使用正弦公式或余弦公式进行选择。
参数r2、r3、r4的更新过程指在一定范围内进行随机选取,参数r1的更新过程使用公式如下:
其中,a为常数,t为当前代数,T为最大迭代数。
步骤六利用SCA迭代公式基于当前阶段种群最优解更新种群,SCA迭代公式如下:
其中,表示第i个维度上第t代个体的位置,Pi t表示第i个维度上第t代个体最优解的位置。
步骤八智能体根据Q-learning方法进行动作选择,选择过程动作价值函数最大策略,相对于传统Q-learning的方法,本算法动作选择过程受SCA初始化影响,具有更小的随机性。具体的动作选择策略公式如下:
其中,a*(s)表示在s状态下的最优动作。
需要注意的是,所述步骤S8中进行的动作选择用于对Q值的迭代过程,此处选择动作的过程并不进行智能体状态转移。
步骤九计算Q值并更新Q值表,Q值表是由状态s与动作a作为基底关于Q值的向量空间,Q值表的更新具体值其中Q值的迭代和新状态s'的添加过程,Q值的迭代依据步骤S8确定的动作估计下一状态并使用贝尔曼方程计算,具体Q值迭代公式如下:
Q(s,a)←Q(s,a)+α[Rt+1+γmaxa′Q(s′,a′)-Q(s,a)] (6)
步骤十状态转移过程在依据步骤八进行的动作选择执行,具体状态转移公式如下:
st=st+1 (7)
经过步骤十一重复循环过程,得到训练完成的Q值表,智能体从起点位置出发,重复所述动作选择过程与状态转移过程直到终点位置,经过路径即为规划得到的最优路径,投影至真实环境即完成了路径规划过程。

Claims (1)

1.一种基于SCA-QL的路径规划方法,其特征在于:其方法包括如下步骤:
第一步、获取真实环境信息,包括智能体在真实环境下的起点位置和终点位置信息、障碍物位置信息;
第二步、根据真实环境信息,建立用于智能体训练的仿真环境;仿真环境建立过程包括:根据真实环境信息建立环境模型,利用栅格法对环境模型进行划分,网格位置基于笛卡尔坐标进行标记,在环境模型中确定起点位置与终点位置坐标对应的栅格并标记,同样的,在环境模型中根据障碍物位置信息对其对应的栅格进行标记;
第三步、在仿真环境中运行SCA-QL算法对智能体进行训练求解最优路径:其中,通过改进正余弦算法的方式对建立的Q值表进行初始化,在此基础上基于Q-learning方法训练强化学习模型,求解最优路径;
SCA-QL算法是一种改进强化学习方法,步骤如下:
步骤一、初始化参数空间,设定超参数;初始化参数空间过程中,参数空间具体指SCA-QL算法中重要变量的集合,其初始化过程包括算法对集合的创建过程和初始条件的设定过程;
参数空间至少包括:状态空间S,表示智能体可能所处的状态的集合;动作空间A,表示智能体执行的动作的集合;奖励函数空间R,表示对于指定的状态和动作下,奖励函数的期望的集合;动作价值空间Q-table,表示对于指定的状态和动作下,智能体动作带来的累积价值的期望的集合;种群空间X,表示SCA算法的可迭代个体的集合;
超参数至少包括:贪婪度ε,影响智能体决策过程中对于学习信息的依赖程度,具体表示智能体决策过程选择最大Q值的动作执行的概率;学习率α,影响智能体对于最具动作价值的动作的学习速度;衰减系数γ,影响在考虑未来动作奖励对当前动作价值影响时的衰减效益;最大迭代步数Max_Iteration,具体表示在算法内各个循环阶段的最大的迭代步数,用以中止算法及避免无限循环;
步骤二、随机生成SCA初始种群;随机生成SCA初始种群过程,表示在种群空间X中,借助随机方法产生数个可迭代个体,其中,每个可迭代个体的都表示为状态空间S中的一个状态,并以与栅格地图相同维度的方式对其位置坐标进行表示,可迭代个体应满足的要求为:每个产生的可迭代个体的位置坐标不能够超出栅格地图范围;每个产生的可迭代个体坐标不能够处于障碍物栅格内,针对不满足要求生成的可迭代个体,重新采用相同随机生成方法进行生成,直到满足达到最大迭代步数,对于到达最大迭代步数仍无法完成可迭代个体生成的状况,重新调整SCA种群维度;
步骤三、对当前种群每个个体位置Q值进行计算更新;在Q-learning之前对SCA种群进行Q值的初始化和迭代,所述Q值迭代过程利用时序差分,即TD学习方法,TD学习指根据下一时间步的值函数估计当前时间步的值函数,具体的估计公式如下:
V(s)←V(s)+α(Rt+1+γV(s′)-V(s)) (1)
其中,V(s)表示状态s下的状态值函数,Rt+1表示下一时刻状态s'对应的奖励,Rt+1+γV(s′)称为TD目标,δt=Rt+1+γV(s′)-V(s)称为TD偏差;
针对Q-learning方法可迭代个体根据公式(1)进行Q值的迭代,具体如下:
Q(s,a)←Q(s,a)+α[Rt+1+γmaxa′Q(s′,a′)-Q(s,a)] (2)
其中,Q(s,a)表示状态s下某时刻的动作a的动作价值,maxa′Q(s′,a′)表示下一时刻状态s'下具有最大动作价值的动作a'对应的Q值;
步骤四、确定当前种群内的最优个体;对当前阶段种群内全部个体的Q值进行搜索,将具有最大Q值的个体标记已知最优个体;
步骤五、对SCA算法参数r1、r2、r3、r4进行更新;SCA算法基于SCA种群进行优化,使用基于正弦和余弦函数的数学模型向外波动或朝着最佳方向前进,算法参数r1、r2、r3、r4用于在不同的优化阶段中自适应调整搜索空间,具体如下:
参数r1指示下一位置区域或移动方向,下一位置区域或移动方向在当前解与当前阶段最优解之间,或在当前解与当前阶段最优解之外;
参数r2定义了根据参数r1指示的方向上运动的距离;
参数r3影响优化目标的权重,即加强或淡化当前阶段最优解在运动距离上的影响;
参数r4随机对使用正弦公式或余弦公式进行选择;
参数r2、r3、r4的更新过程指在一定范围内进行随机选取,参数r1的更新过程使用公式如下:
其中,a为常数,t为当前代数,T为最大迭代数;
步骤六、利用SCA迭代公式基于当前种群最优解更新种群;SCA迭代公式如下:
其中,表示第i个维度上第t代个体的位置,Pi t表示第i个维度上第t代个体最优解的位置;
步骤七、重复步骤三至步骤六,直至达到设定迭代步数;
步骤八、智能体根据Q-learning方法进行动作选择;选择过程动作价值函数最大策略,具体的动作选择策略公式如下:
其中,a*(s)表示在s状态下的最优动作;
步骤九、计算Q值并更新Q值表;Q值表是由状态s与动作a作为基底关于Q值的向量空间,Q值表的更新包括Q值的迭代和新状态s'的添加过程,Q值的迭代依据步骤八确定的动作估计下一状态并使用贝尔曼方程计算,具体Q值迭代公式如下:
Q(s,a)←Q(s,a)+α[Rt+1+γmaxa′Q(s′,a′)-Q(s,a)] (6);
步骤十、智能体进行状态转移;状态转移过程依据步骤八进行的动作选择执行,具体状态转移公式如下:
st=st+1 (7)
步骤十一、重复步骤八至步骤十,直到收敛条件或者达到设定迭代步数,重复循环过程,得到训练完成的Q值表,智能体从起点位置出发,重复动作选择过程与状态转移过程直到终点位置,经过路径即为规划得到的最优路径,投影至真实环境即完成了路径规划过程。
CN202210792993.5A 2022-07-07 2022-07-07 一种基于sca-ql的路径规划方法 Active CN115016499B (zh)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN202210792993.5A CN115016499B (zh) 2022-07-07 2022-07-07 一种基于sca-ql的路径规划方法

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN202210792993.5A CN115016499B (zh) 2022-07-07 2022-07-07 一种基于sca-ql的路径规划方法

Publications (2)

Publication Number Publication Date
CN115016499A CN115016499A (zh) 2022-09-06
CN115016499B true CN115016499B (zh) 2024-10-25

Family

ID=83078294

Family Applications (1)

Application Number Title Priority Date Filing Date
CN202210792993.5A Active CN115016499B (zh) 2022-07-07 2022-07-07 一种基于sca-ql的路径规划方法

Country Status (1)

Country Link
CN (1) CN115016499B (zh)

Families Citing this family (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN116822765B (zh) * 2023-06-02 2024-08-16 东南大学 一种基于Q-learning的智能体时序任务路径规划方法

Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN111649758A (zh) * 2020-06-16 2020-09-11 华东师范大学 一种动态环境下基于强化学习算法的路径规划方法
CN112344944A (zh) * 2020-11-24 2021-02-09 湖北汽车工业学院 一种引入人工势场的强化学习路径规划方法

Family Cites Families (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN111061966B (zh) * 2019-11-27 2022-08-05 福州大学 基于强化学习算法的失踪目标搜索方法
CN112964272A (zh) * 2021-03-16 2021-06-15 湖北汽车工业学院 一种改进的Dyna-Q学习路径规划算法
CN113010967B (zh) * 2021-04-22 2022-07-01 吉林大学 一种基于混合交通流模型的智能汽车在环仿真测试方法

Patent Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN111649758A (zh) * 2020-06-16 2020-09-11 华东师范大学 一种动态环境下基于强化学习算法的路径规划方法
CN112344944A (zh) * 2020-11-24 2021-02-09 湖北汽车工业学院 一种引入人工势场的强化学习路径规划方法

Also Published As

Publication number Publication date
CN115016499A (zh) 2022-09-06

Similar Documents

Publication Publication Date Title
CN112356830B (zh) 一种基于模型强化学习的智能泊车方法
CN114603564B (zh) 机械臂导航避障方法、系统、计算机设备及存储介质
CN113110509A (zh) 一种基于深度强化学习的仓储系统多机器人路径规划方法
WO2017215044A1 (zh) 一种移动机器人的自动规划路径方法及移动机器人
CN114460943B (zh) 服务机器人自适应目标导航方法及系统
Otte A survey of machine learning approaches to robotic path-planning
CN110181508B (zh) 水下机器人三维航路规划方法及系统
CN109726676B (zh) 自动驾驶系统的规划方法
CN112596515A (zh) 一种多物流机器人移动控制方法及装置
Belmonte-Baeza et al. Meta reinforcement learning for optimal design of legged robots
CN109940614B (zh) 一种融合记忆机制的机械臂多场景快速运动规划方法
CN115990891A (zh) 一种基于视觉示教和虚实迁移的机器人强化学习装配的方法
CN115016499B (zh) 一种基于sca-ql的路径规划方法
CN114161419B (zh) 一种情景记忆引导的机器人操作技能高效学习方法
CN116147627A (zh) 一种结合深度强化学习和内在动机的移动机器人自主导航方法
CN118394090A (zh) 一种基于深度强化学习的无人车决策与规划方法及系统
CN115542912B (zh) 一种基于改进Q-learning算法的移动机器人路径规划方法
CN117606490A (zh) 一种水下自主航行器协同搜索路径规划方法
CN116430891A (zh) 一种面向多智能体路径规划环境的深度强化学习方法
CN117523359A (zh) 一种基于强化学习的图像比对识别方法及设备
CN116360435A (zh) 基于情节记忆的多智能体协同策略的训练方法和系统
CN114815813A (zh) 一种基于改进ddpg算法的高效路径规划方法、装置及介质
CN114118441A (zh) 基于高效搜索策略在不确定性环境下的在线规划方法
Tang et al. Reinforcement learning for robots path planning with rule-based shallow-trial
CN118758320B (zh) 一种基于改进灰狼优化算法的机器人路径规划方法及系统

Legal Events

Date Code Title Description
PB01 Publication
PB01 Publication
SE01 Entry into force of request for substantive examination
SE01 Entry into force of request for substantive examination
GR01 Patent grant
GR01 Patent grant