劃常用算法)
運動規(guī)劃Motion Planning在機器人領域一般指給機器人從起始狀態(tài)到目標狀態(tài)生成一條滿足約束的運動軌跡。比如人形機器人抓瓶子已知機器人當前姿態(tài) → 目標抓取位姿 → 生成機械臂關節(jié)軌跡 → 避障 → 平滑執(zhí)行這整個過程就是運動規(guī)劃。運動規(guī)劃算法大體分為幾類1. 基于搜索的規(guī)劃Search-based Planning適合移動機器人柵格地圖低維空間① A* 算法最經典路徑規(guī)劃。思想總代價 已經走過的代價 預計距離 f(n)g(n)h(n)其中g(n)當前位置到當前節(jié)點成本h(n)當前位置到目標估計距離例如機器人 S □ □ □ □ ■ ■ □ □ □ □ G A*: S → → ↓ ↓ → G優(yōu)點? 保證最優(yōu)缺點? 高維機械臂不適合應用ROS Nav2Global PlannerSmac Planner② DijkstraA* 的前身。區(qū)別Dijkstraf(n)g(n)不知道目標在哪里全部搜索。優(yōu)點保證最短路徑缺點慢。2. 采樣規(guī)劃Sampling-based Planning這是機械臂最常用的一類。因為機械臂空間例如7自由度q[q1,q2,q3,q4,q5,q6,q7]搜索空間巨大。所以隨機采樣。① RRTRapidly-exploring Random Tree機器人領域非常經典。思想隨機長樹。例如* * * S----* \ * * G步驟隨機生成一個點找最近節(jié)點朝它擴展碰撞檢測連到樹優(yōu)點? 快? 高維有效缺點? 路徑比較亂② RRT*RRT優(yōu)化版。核心重新連接。讓路徑RRT: S------*---*---G RRT*: S-----------G特點隨著采樣增加越來越接近最優(yōu)。目前機械臂規(guī)劃非常常用。③ Informed RRT*進一步優(yōu)化。不是全空間隨機而是在起點-終點橢球區(qū)域采樣。速度更快。④ PRMProbabilistic Roadmap適合固定環(huán)境。先建地圖隨機點: * * * * * * 連接: *---*---* \ / *---*然后搜索。3. 優(yōu)化類運動規(guī)劃Optimization-based現(xiàn)在機器人研究熱點。核心把運動規(guī)劃變成優(yōu)化問題。目標最小[Cost距離碰撞能量平滑]① CHOMPCovariant Hamiltonian Optimization for Motion Planning優(yōu)化軌跡原始--------- \ \ G優(yōu)化----------- \ G特點軌跡平滑。② STOMP基于隨機優(yōu)化。特點不需要梯度。③ TrajOpt工業(yè)機器人常用。優(yōu)勢速度快。目標min: 軌跡長度 碰撞代價 動力學約束4. MPCModel Predictive Control這個現(xiàn)在非常火。不是一次規(guī)劃到底。而是滾動規(guī)劃。例如機器人走路預測未來現(xiàn)在 | |----未來2秒預測 | 執(zhí)行0.1秒 重新規(guī)劃循環(huán)。優(yōu)勢? 動態(tài)環(huán)境? 機器人控制結合應用自動駕駛四足機器人人形機器人5. 速度規(guī)劃Time Parameterization規(guī)劃路徑后還需要什么時候到哪里例如路徑A-------------B變成t0 t1 t2 A------M-------B常用TOPPTime Optimal Path ParameterizationRuckig現(xiàn)在工業(yè)機器人非?；?。作用限制速度加速度jerkMoveIt2 默認大量使用。6. 人形機器人/機械臂常用組合視覺 | 目標抓取位姿 | IK逆運動學 | 運動規(guī)劃 | 軌跡優(yōu)化 | 控制執(zhí)行具體MoveIt2:OMPL | RRTConnect | RRT* | PRM | TrajOpt | Ruckig7. 不同場景對應算法場景算法二維地圖導航A*、DijkstraROS導航A*、D*、Smac機械臂避障RRTConnect高自由度機械臂RRT*工業(yè)機械臂TrajOpt動態(tài)環(huán)境MPC人形機器人MPC優(yōu)化抓取規(guī)劃RRTIK腿式機器人MPC 運動規(guī)劃常用算法
運動規(guī)劃Motion Planning在機器人領域一般指給機器人從起始狀態(tài)到目標狀態(tài)生成一條滿足約束的運動軌跡。比如人形機器人抓瓶子已知機器人當前姿態(tài) → 目標抓取位姿 → 生成機械臂關節(jié)軌跡 → 避障 → 平滑執(zhí)行這整個過程就是運動規(guī)劃。運動規(guī)劃算法大體分為幾類1. 基于搜索的規(guī)劃Search-based Planning適合移動機器人柵格地圖低維空間① A* 算法最經典路徑規(guī)劃。思想總代價 已經走過的代價 預計距離 f(n)g(n)h(n)其中g(n)當前位置到當前節(jié)點成本h(n)當前位置到目標估計距離例如機器人 S □ □ □ □ ■ ■ □ □ □ □ G A*: S → → ↓ ↓ → G優(yōu)點? 保證最優(yōu)缺點? 高維機械臂不適合應用ROS Nav2Global PlannerSmac Planner② DijkstraA* 的前身。區(qū)別Dijkstraf(n)g(n)不知道目標在哪里全部搜索。優(yōu)點保證最短路徑缺點慢。2. 采樣規(guī)劃Sampling-based Planning這是機械臂最常用的一類。因為機械臂空間例如7自由度q[q1,q2,q3,q4,q5,q6,q7]搜索空間巨大。所以隨機采樣。① RRTRapidly-exploring Random Tree機器人領域非常經典。思想隨機長樹。例如* * * S----* \ * * G步驟隨機生成一個點找最近節(jié)點朝它擴展碰撞檢測連到樹優(yōu)點? 快? 高維有效缺點? 路徑比較亂② RRT*RRT優(yōu)化版。核心重新連接。讓路徑RRT: S------*---*---G RRT*: S-----------G特點隨著采樣增加越來越接近最優(yōu)。目前機械臂規(guī)劃非常常用。③ Informed RRT*進一步優(yōu)化。不是全空間隨機而是在起點-終點橢球區(qū)域采樣。速度更快。④ PRMProbabilistic Roadmap適合固定環(huán)境。先建地圖隨機點: * * * * * * 連接: *---*---* \ / *---*然后搜索。3. 優(yōu)化類運動規(guī)劃Optimization-based現(xiàn)在機器人研究熱點。核心把運動規(guī)劃變成優(yōu)化問題。目標最小[Cost距離碰撞能量平滑]① CHOMPCovariant Hamiltonian Optimization for Motion Planning優(yōu)化軌跡原始--------- \ \ G優(yōu)化----------- \ G特點軌跡平滑。② STOMP基于隨機優(yōu)化。特點不需要梯度。③ TrajOpt工業(yè)機器人常用。優(yōu)勢速度快。目標min: 軌跡長度 碰撞代價 動力學約束4. MPCModel Predictive Control這個現(xiàn)在非常火。不是一次規(guī)劃到底。而是滾動規(guī)劃。例如機器人走路預測未來現(xiàn)在 | |----未來2秒預測 | 執(zhí)行0.1秒 重新規(guī)劃循環(huán)。優(yōu)勢? 動態(tài)環(huán)境? 機器人控制結合應用自動駕駛四足機器人人形機器人5. 速度規(guī)劃Time Parameterization規(guī)劃路徑后還需要什么時候到哪里例如路徑A-------------B變成t0 t1 t2 A------M-------B常用TOPPTime Optimal Path ParameterizationRuckig現(xiàn)在工業(yè)機器人非?；?。作用限制速度加速度jerkMoveIt2 默認大量使用。6. 人形機器人/機械臂常用組合視覺 | 目標抓取位姿 | IK逆運動學 | 運動規(guī)劃 | 軌跡優(yōu)化 | 控制執(zhí)行具體MoveIt2:OMPL | RRTConnect | RRT* | PRM | TrajOpt | Ruckig7. 不同場景對應算法場景算法二維地圖導航A*、DijkstraROS導航A*、D*、Smac機械臂避障RRTConnect高自由度機械臂RRT*工業(yè)機械臂TrajOpt動態(tài)環(huán)境MPC人形機器人MPC優(yōu)化抓取規(guī)劃RRTIK腿式機器人MPC