# VO 文獻記事

## 順序

digraph flow{
    node[shape=Mrecord]
    VO [label="VO | 1998 "]
    RVO [label="RVO | 2008"]
    ClearPath [label="ClearPath\n (FVO) | 2009"]
    HRVO [label="HRVO | 2011"]
    ORCA [label="ORCA | 2011"]
    {rank=same; HRVO,ORCA}
    VO -> RVO;
    RVO -> ClearPath;
    RVO -> ORCA [nodesep=10]
    ClearPath -> HRVO
}

## 速度障礙區塊

| VO | RVO |ClearPath(FVO)|HRVO|ORCA|
| -------------------------------------------------- | -------------------------------------------------- | -------- | --- | --- |
|  |  ||||

* 1998年的VO文獻中其實有提到，可以設立一個time horizon ($\tau$)，僅考慮這個時間範圍內，自己與其他agents會不會發生碰撞。如此便可以在速度space中，修剪掉一些碰撞追靠近自己的部分，讓VO的領域縮小，增加更多的可行速度選擇。但是VO和RVO的論文中，實驗裡似乎都沒有加進這項考慮，會直接避開整個錐形的速度障礙。而ClearPath提出的FVO以及ORCA都有設立($\tau$)，擴大可行解範圍。

geogebra展示速度障礙區塊: https://www.geogebra.org/calculator/xbq5svsp

## 論文重點

### VO
* 只適合回避定速動態障礙
* 依照kinematic constrain & dynamic constrain 提出 feasible velocity區間概念
* 三種選擇速度的策略: TG(to goal)、MV(maximum velocity)、ST(structure)
* 設立 time horizon ($\tau$)概念
* <font color="#f00">僅有simulations，假設agent可以完美偵測動態障礙的速度與相對座標(上帝視角)</font>
### RVO
* 依據責任($\alpha$)移動VO形成RVO
* 選擇RVO外距離$\mathbf{v_A^{pref}}$最近的向量
* 僅考慮距離自己一定範圍內(neighbor region)的節點
* 在擁擠情況下允許agent選擇RVO內的速度向量，但是會依TTC、與$\mathbf{v_A^{pref}}$的距離，建立penalty。
* <font color="#f00">僅有simulations，假設agents之間沒有溝通，但可以完美偵測彼此的速度與相對座標(上帝視角)</font>
### ClearPath
* 以RVO為基礎，僅考慮 time horizon ($\tau$)時間範圍內的碰撞，增加可行解(FVO)
* 若沒有可行解，移除最遠的FVO，直到出現feasible velocity區間
* 選擇FVO外距離$\mathbf{v_A^{curr}}$最近的向量
* <font color="#f00">僅有simulations，各agents早就知道彼此的位置及速度並建立KD-tree(上帝視角)</font>
### HRVO
* 改進RVO可能發生的"reciprocal dancing"，結合RVO與VO的邊界形成HRVO
* 使用ClearPath演算法搜尋下一刻的速度向量
* 5篇paper中唯一一篇將不確定性納入速度障礙區塊進行考慮(較為偏向實用)
* 有稍微加入RRT以避開擋住目標的大塊障礙物
* <font color="#f00">有experiments與simulations，再experiments中，由於機器人尚無法靠感測器知道自身的確切座標與朝向，所以有一個中控系統用相機感應每個robots的位置與朝向，回傳給robots，再用Kalman filter推斷速度，論文稱是"有限度的溝通"(類上帝視角)</font>
### ORCA
* 以VO的概念做延伸，考慮time horizon ($\tau$)時間範圍內的碰撞
* 將原本錐形的速度障礙演變成二為空間中的半平面，將複雜的最佳化問題簡化為線性規劃，降低運算時間
* 透過改變理想的$\mathbf{v_A^{opt}}$，找出最佳速度向量。
* <font color="#f00">僅有simulation，假設各agents之間沒有溝通，但可以完美偵測彼此的速度與相對座標(上帝視角)</font>

## 心得(可能會再更新)
個人覺得，無果要將VO避障用在現實中的robot上，需要如HRVO那篇文獻一樣，將資訊的不準確性考慮進來，除此之外，如果不允許robots有溝通的話，也不能設置中控系統，不能有上帝視角，這樣子感測誤差可能會無法被校正。
我覺得，VO的最初的避障原理，是參考動態障礙物的當下位置座標，建立出一個現實的碰撞錐範圍，未來的下一刻，只要自己與障礙物的相對速度落在這個碰撞錐範圍內，便有可能發生碰撞。
為了更直觀判斷$\mathbf{v_A}$是否會導致碰撞，因此進入速度space中，依障礙物的未來速度，移動那個碰撞錐，形成速度障礙VO。如此便可以直接得出，未來的下一刻，$\mathbf{v_A}$是不是安全的。
由於以上，VO的避障法，需要的參數是當下自己與障礙物的相對或絕對座標，以及障礙物未來的下一刻之速度向量。藉由這些參數推斷下一刻自己的$\mathbf{v_A}$是否安全。在假設自己與障礙物的當下位置為已知的情況下，用VO法來閃避一個定速的障礙物很容易達成，畢竟障礙物的未來速度與當下速度一模一樣。然而，當人們用VO法來閃避一個會改變移動速度的障礙物時，會讓情況變得有點困難。困難點在於:「我們怎麼知道障礙物的未來速度?」。如果是一個規則運動的障礙物，我們可以套用kimematic公式，甚至是dynamic公式來預測出障礙物的未來速度，再用VO法避障。然而，如今我們面對的障礙物，是一個和自己一樣，會依照環境變化自由改變其速度的agent，預測障礙物的未來速度似乎不可行，那該如何用VO法來閃避障礙物?我個人認為，RVO和HRVO以及ORCA等避障方法其實並沒有真正去預測對方agent的未來速度，然後建立出速度障礙來避開。以上那些避障法所做的，其實是再agents之間建立「默契」，例如:只要angent A 採用RVO策略選擇速度，agent B 也如是，基本上他們便不會撞到。

## Reference
Fiorini, Paolo, and Zvi Shiller. "Motion planning in dynamic environments using velocity obstacles." The international journal of robotics research 17.7 (1998): 760-772.
Van den Berg, Jur, Ming Lin, and Dinesh Manocha. "Reciprocal velocity obstacles for real-time multi-agent navigation." 2008 IEEE international conference on robotics and automation. Ieee, 2008.
Guy, S. J., Chhugani, J., Kim, C., Satish, N., Lin, M., Manocha, D., & Dubey, P. (2009, August). Clearpath: highly parallel collision avoidance for multi-agent simulation. In Proceedings of the 2009 ACM SIGGRAPH/Eurographics Symposium on Computer Animation (pp. 177-187).
Snape, J., Van Den Berg, J., Guy, S. J., & Manocha, D. (2011). The hybrid reciprocal velocity obstacle. IEEE Transactions on Robotics, 27(4), 696-706.
Van Den Berg, J., Guy, S. J., Lin, M., & Manocha, D. (2011, August). Reciprocal n-body collision avoidance. In Robotics Research: The 14th International Symposium ISRR (pp. 3-19). Berlin, Heidelberg: Springer Berlin Heidelberg.