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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
The velocity obstacle VOAB for a robot A, with position xA, induced by another robot B, with position xB and velocity vB.

У робототехніці та плануванні руху, взаємозавадна швидкість (англ. 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].

References[ред.ред. код]

  1. а б Fiorini, P.; Shiller, Z. (July 1998). «Motion planning in dynamic environments using velocity obstacles». The International Journal of Robotics Research 17 (7) (Thousand Oaks, Calif.: SAGE Publications). с. 760–772. doi:10.1177/027836499801700706. ISSN 0278-3649. 
  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.
  3. Fiorini, P.; Shiller, Z.(1993). "Motion planning in dynamic environments using the relative velocity paradigm". IEEE Conference on Robotics and Automation, 560–565.
  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.
  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), 1207–1212, New York, N.Y.:IEEE.. 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), 177–187, New York, N.Y.:ACM.. 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.
  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), 734–739, New York, N.Y.:IEEE. DOI:10.1109/ICARCV.2002.1238513.
  12. v.d. Berg, J.(May 2008). "Reciprocal velocity obstacles for real-time multi-agent navigation". IEEE International Conference on Robotics and Automation (ICRA 08), 1928–1935, New York, N.Y.:IEEE. 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), 1610–1616, New York, N.Y.:IEEE. DOI:10.1109/ROBOT.2007.363554.