# 進度報告(2024/12/30)
這周我找到自己寫的ORCA運作失敗的原因了。原ORCA的論文[^1]強調「每顆節點的行動都是獨立自主的，沒有與其他機器人溝通」:"In our formulation, each robot acts fully in
dependently, and does not communicate with other robots."
這導致我有點被誤導了。細看論文以及比對後續相關文獻[^2]後，結論是節點間應該有事先溝通，再來才是獨立自主的避障行為。
:::info
三節點測試情境:
{%youtube 7vfM5-L7M7M%}
B1節點的速度空間:
{%youtube 4VH80UOtqqU%}
* 黑色圓圈範圍是節點的速度範圍，設為100。黑色的點代表朝向目標的最佳速度
* 藍色線帶表膨脹後的碰撞錐，虛線為被修掉的部分
* 綠色線是與碰撞錐的切線，綠色點則是$\mathbf{u}$與碰撞錐的交點
* 紅色虛線朝向綠色線的那半邊為ORCA，紅點則是$\mathbf{v}^{opt}+\frac{1}{2}\mathbf{u}$
* 桃紅點則象徵最佳化找到的速度
:::spoiler B1的速度
:::

## VO的形成
A節點與B障礙相遇時，會做下列幾件事形成VO，以保證自己不會碰撞B。
1. 將B的中心位置投射至自身的速度空間中，投射座標為$\mathbf{p}_B-\mathbf{p}_A$，也就是B相對於自身的位置

2. 在速度空間中，由B的中心點擴張出$r_A+r_B$的膨脹層，形成一個圓稱為$\hat{B}$，而自身所在的相對位置，也就是速度空間中的原點，稱為$\hat{A}$

3. 由$\hat{A}$對$\hat{B}$做兩條切線，形成一個速度空間中的錐形區域，叫做碰撞錐。此碰撞錐代表著所有會造成碰撞的A相對於B之速度$\mathbf{v}_{AB}$集合(Collision Cone,$CC_{A,B}$)

4. 若想得知有哪些$\mathbf{v}_A$會碰撞，將碰撞錐(相對速度集合)加回$\mathbf{v}_B$即可，而這群會造成相撞的$\mathbf{v}_A$集合，便被稱為Velocity Obstacle(VO)。
$$VO_{A,B} = CC_{A,B}\oplus\mathbf{v}_B$$

所以，我們便可以得知，節點A的速度空間中，有一塊被稱為"速度障礙"的區域，凡是$\mathbf{v}_A$踏入該區，便有可能在未來內造成AB相撞。
5. 接著，可以將VO套入TTC的概念，判斷在$\tau$秒後才會造成碰撞的$\mathbf{v}_A$速度還算安全。於是，我們可以將這個VO領域做修剪，形成$VO_{A,B}^\tau$。

## ORCA的形成
起初我以為ORCA僅是做VO的切線，將限制線性化而已。但是，重看論文後才明白，ORCA在平移碰撞錐形成VO的那一步，也就是樓上第4步，就已經與傳統的速度障礙法不同了。以下是ORCA形成的方式:
* 平移速度空間中的$CC_{A,B}$，但不是平移$\mathbf{v}_B$向量，而是$\mathbf{v}_B^{opt}$向量(最大速度朝終點前進的向量)。$VO_{A,B} = CC_{A,B}\oplus\mathbf{v}_B^{opt}$
* 修剪VO為$VO_{A,B}^\tau$
* 計算$\mathbf{v}_A^{opt}$距離$VO_{A,B}^\tau$最短的向量$\mathbf{u}$，並在最近點做VO的切線，然後將此切線平移$-\frac{1}{2}\mathbf{u}$的距離，得到$ORCA_{A|B}^\tau$

## 結論
機器人想要用ORCA法相互避障，便必須要知道對方的最佳速度($\mathbf{v}_B^{opt}$)。然而，若是機器人沒有事先知道其他機器人的目的地，便無法得知他們的最佳速度。也就是說，在所有機器人開始跑之前，他們必須先講好，而這其實就違反了不溝通的原則了。甚至可以說，ORCA對應的情況為已知意圖的多節點情境，因為 **所有機器人都希望朝目標點直線前進，也知道所有其他機器人欲朝他們的終點直線前進。** 因此ORCA提供的是一個共同行為準則，讓機器人間不會互相干擾彼此。
## Reference
[^1]:Van Den Berg, Jur, et al. "Reciprocal n-body collision avoidance." Robotics Research: The 14th International Symposium ISRR. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011.
[^2]:Alonso-Mora, Javier, et al. "Optimal reciprocal collision avoidance for multiple non-holonomic robots." Distributed autonomous robotic systems: The 10th international symposium. Springer Berlin Heidelberg, 2013.