Взаємозавадна швидкість

У робототехніці та плануванні руху, взаємозавадна швидкість (англ. Velocity Obstacle, зазвичай скорочено V.O) — це швидкість агента, яка призведе до зіткненні з іншим агентом в якийсь момент часу, за умови, що інший агент зберігає свою поточну швидкість^[1]. Якщо агент вибирає швидкість всередині множини взаємозавданих швидкостей, то два агенти в кінцевому підсумку стикаються, якщо він вибирає швидкість поза взаємозавадними швидкостями, таке зіткнення гарантовано не відбувається^[1]. Цей алгоритм запобігання зіткнень для агента було неодноразово пере відкрито і опубліковано під різними назвами: у 1989 році як підход бортового маневрування (англ. maneuvering-board approach)^[2], у 1993 його було вперше представлено як «взаємозавадну швидкість»^[3], у 1998 році, як зіткнення конусів^[4] і у 2009 році заборонених карт швидкості^[5]. Цей же алгоритм використовується у морській навігації з 1903 року^[6].

Взаємозавадна швидкість для агента спровокована агентом може бути описана як:

$VO_{A|B}=\{\mathbf {v} \,|\,\exists t>0:(\mathbf {v} -\mathbf {v} _{B})t\in D(\mathbf {x} _{B}-\mathbf {x} _{A},r_{A}+r_{B})\}$

де $A$ є радіус-вектором $\mathbf {x} _{A}$ з радіусом $r_{A}$ , а $B$ — радіус-вектором $\mathbf {x} _{B}$ з радіусом $r_{B}$ , та швидкістю $\mathbf {v} _{B}$ . $D(\mathbf {x} ,r)$ репрезентує круг перешкоди руху з центром $\mathbf {x}$ та радіусом $r$ .

Варіації алгоритму: загальна взаємозавадна швидкість (англ. common velocity obstacles - CVO)^[7], часоконечні взаємозавадні швидкості (англ. finite-time-interval velocity obstacles - FVO)^[8], узагальнені перешкоди швидкості (англ. generalized velocity obstacles - GVO)^[9], гібридні взаємні перешкоди швидкості (англ. hybrid reciprocal velocity obstacles - HRVO)^[10], нелінійні взаємозавадні швидкості (англ. nonlinear velocity obstacles - NLVO)^[11], взаємні перешкоди швидкості (англ. reciprocal velocity obstacles - РВО)^[12] і рекурсивно імовірнісні взаємозавадні швидкості (англ. recursive probabilistic velocity obstacles - PVO)^[13].

Примітки

↑ ^а ^б Fiorini, P.; Shiller, Z. (July 1998). Motion planning in dynamic environments using velocity obstacles. The International Journal of Robotics Research. Thousand Oaks, Calif.: SAGE Publications. 17 (7): 760—772. doi:10.1177/027836499801700706. ISSN 0278-3649.
↑ Tychonievich, L. P.; Zaret, D.; Mantegna, R.; Evans, R.; Muehle, E.; Martin, S. (1989). A maneuvering-board approach to path planning with moving obstacles. International Joint conference on Artificial Intelligence (IJCAI). с. 1017—1021.
↑ Fiorini, P.; Shiller, Z. (1993). Motion planning in dynamic environments using the relative velocity paradigm. IEEE Conference on Robotics and Automation. с. 560—565.
↑ Chakravarthy, A.; Ghose, D. (September 1998). Obstacle avoidance in a dynamic environment: A collision cone approach. IEEE Transactions on Systems, Man and Cybernetics—Part A: Systems and Humans. 28 (5): 562—574. doi:10.1109/3468.709600.
↑ Damas, B.; Santos-Victor, J. (2009). Avoiding moving obstacles: the forbidden velocity map. IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). с. 4393—4398.
↑ Miller, F. S.; Everett, A. F. (1903). Instructions for the Use of Martin’s Mooring Board and Battenberg’s Course Indicator. Authority of the Lords of Commissioners of the Admirality.
↑ Abe, Y.; Yoshiki, M. (November 2001). Collision avoidance method for multiple autonomous mobile agents by implicit cooperation. IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 01). New York, N.Y.: IEEE. с. 1207—1212. doi:10.1109/IROS.2001.977147.
↑ Guy, S. J.; Chhugani, J.; Kim, C.; Satish, N.; Lin, M.; Manocha, D.; Dubey, P. (August 2009). ClearPath: Highly parallel collision avoidance for multi-agent simulation. ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA 09). New York, N.Y.: ACM. с. 177—187. doi:10.1145/1599470.1599494.
↑ Wilkie, D.; v.d. Berg, J.; Manocha, D. (October 2009). Generalized velocity obstacles. IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 09). New York, N.Y.: IEEE. doi:10.1109/IROS.2009.5354175.
↑ Snape, J.; v.d. Berg, J.; Guy, S. J.; Manocha, D. (October 2009). Independent navigation of multiple mobile robots with hybrid reciprocal velocity obstacles. IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 09). New York, N.Y.: IEEE. Архів оригіналу за 24 грудня 2013. Процитовано 22 грудня 2013.
↑ Large, F.; Sekhavat, S.; Shiller, Z.; Laugier, C. (December 2002). Using non-linear velocity obstacles to plan motions in a dynamic environment. IEEE International Conference on Control, Automation, Robotics and Vision (ICARCV 02). New York, N.Y.: IEEE. с. 734—739. doi:10.1109/ICARCV.2002.1238513.
↑ v.d. Berg, J.; Lin, M.; Manocha, D. (May 2008). Reciprocal velocity obstacles for real-time multi-agent navigation. IEEE International Conference on Robotics and Automation (ICRA 08). New York, N.Y.: IEEE. с. 1928—1935. doi:10.1109/ROBOT.2008.4543489.
↑ Fulgenzi, C.; Spalanzani, A.; Laugier, C. (April 2007). Dynamic obstacle avoidance in uncertain environment combining PVOs and occupancy grid. IEEE International Conference on Robotics and Automation (ICRA 07). New York, N.Y.: IEEE. с. 1610—1616. doi:10.1109/ROBOT.2007.363554.

Це незавершена стаття з математики.
Ви можете допомогти проєкту, виправивши або дописавши її.

[fiorini98-1] а ^б Fiorini, P.; Shiller, Z. (July 1998). Motion planning in dynamic environments using velocity obstacles. The International Journal of Robotics Research. Thousand Oaks, Calif.: SAGE Publications. 17 (7): 760—772. doi:10.1177/027836499801700706. ISSN 0278-3649.

[tychonieivich89-2] Tychonievich, L. P.; Zaret, D.; Mantegna, R.; Evans, R.; Muehle, E.; Martin, S. (1989). A maneuvering-board approach to path planning with moving obstacles. International Joint conference on Artificial Intelligence (IJCAI). с. 1017—1021.

[fiorini93-3] Fiorini, P.; Shiller, Z. (1993). Motion planning in dynamic environments using the relative velocity paradigm. IEEE Conference on Robotics and Automation. с. 560—565.

[chakravarthy98-4] Chakravarthy, A.; Ghose, D. (September 1998). Obstacle avoidance in a dynamic environment: A collision cone approach. IEEE Transactions on Systems, Man and Cybernetics—Part A: Systems and Humans. 28 (5): 562—574. doi:10.1109/3468.709600.

[5] Damas, B.; Santos-Victor, J. (2009). Avoiding moving obstacles: the forbidden velocity map. IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). с. 4393—4398.

[miller03-6] Miller, F. S.; Everett, A. F. (1903). Instructions for the Use of Martin’s Mooring Board and Battenberg’s Course Indicator. Authority of the Lords of Commissioners of the Admirality.

[7] Abe, Y.; Yoshiki, M. (November 2001). Collision avoidance method for multiple autonomous mobile agents by implicit cooperation. IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 01). New York, N.Y.: IEEE. с. 1207—1212. doi:10.1109/IROS.2001.977147.

[8] Guy, S. J.; Chhugani, J.; Kim, C.; Satish, N.; Lin, M.; Manocha, D.; Dubey, P. (August 2009). ClearPath: Highly parallel collision avoidance for multi-agent simulation. ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA 09). New York, N.Y.: ACM. с. 177—187. doi:10.1145/1599470.1599494.

[9] Wilkie, D.; v.d. Berg, J.; Manocha, D. (October 2009). Generalized velocity obstacles. IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 09). New York, N.Y.: IEEE. doi:10.1109/IROS.2009.5354175.

[10] Snape, J.; v.d. Berg, J.; Guy, S. J.; Manocha, D. (October 2009). Independent navigation of multiple mobile robots with hybrid reciprocal velocity obstacles. IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 09). New York, N.Y.: IEEE. Архів оригіналу за 24 грудня 2013. Процитовано 22 грудня 2013.

[11] Large, F.; Sekhavat, S.; Shiller, Z.; Laugier, C. (December 2002). Using non-linear velocity obstacles to plan motions in a dynamic environment. IEEE International Conference on Control, Automation, Robotics and Vision (ICARCV 02). New York, N.Y.: IEEE. с. 734—739. doi:10.1109/ICARCV.2002.1238513.

[12] v.d. Berg, J.; Lin, M.; Manocha, D. (May 2008). Reciprocal velocity obstacles for real-time multi-agent navigation. IEEE International Conference on Robotics and Automation (ICRA 08). New York, N.Y.: IEEE. с. 1928—1935. doi:10.1109/ROBOT.2008.4543489.

[13] Fulgenzi, C.; Spalanzani, A.; Laugier, C. (April 2007). Dynamic obstacle avoidance in uncertain environment combining PVOs and occupancy grid. IEEE International Conference on Robotics and Automation (ICRA 07). New York, N.Y.: IEEE. с. 1610—1616. doi:10.1109/ROBOT.2007.363554.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]