“Dynamic optimal space partitioning for redirected walking in multi-user environment” by Jeon, Kwon, Hwang, Cho, Kim, et al. …

In multi-user Redirected Walking (RDW), the space subdivision method divides a shared physical space into sub-spaces and allocates a sub-space to each user. While this approach has the advantage of precluding any collisions between users, the conventional space subdivision method suffers from frequent boundary resets due to the reduction of available space per user. To address this challenge, in this study, we propose a space subdivision method called Optimal Space Partitioning (OSP) that dynamically divides the shared physical space in real-time. By exploiting spatial information of the physical and virtual environment, OSP predicts the movement of users and divides the shared physical space into optimal sub-spaces separated with shutters. Our OSP framework is trained using deep reinforcement learning to allocate optimal sub-space to each user and provide optimal steering. Our experiments demonstrate that OSP provides higher sense of immersion to users by minimizing the total number of reset counts, while preserving the advantage of the existing space subdivision strategy: ensuring better safety to users by completely eliminating the possibility of any collisions between users beforehand. Our project is available at https://github.com/AppleParfait/OSP-Archive.

1. Franz Aurenhammer. 1991. Voronoi diagrams—a survey of a fundamental geometric data structure. ACM Computing Surveys (CSUR) 23, 3 (1991), 345–405.Google ScholarDigital Library
2. Mahdi Azmandian, Timofey Grechkin, Mark Bolas, and Evan Suma. 2016. The redirected walking toolkit: a unified development platform for exploring large virtual environments. In 2016 IEEE 2nd Workshop on Everyday Virtual Reality (WEVR). IEEE, 9–14.Google ScholarCross Ref
3. Mahdi Azmandian, Timofey Grechkin, and Evan Suma Rosenberg. 2017. An evaluation of strategies for two-user redirected walking in shared physical spaces. In 2017 IEEE Virtual Reality (VR). IEEE, 91–98.Google Scholar
4. Mahdi Azmandian, Rhys Yahata, Timofey Grechkin, Jerald Thomas, and Evan Suma Rosenberg. 2022. Validating simulation-based evaluation of redirected walking systems. IEEE Transactions on Visualization & Computer Graphics 01 (2022), 1–1.Google Scholar
5. Eric R Bachmann, Eric Hodgson, Cole Hoffbauer, and Justin Messinger. 2019. Multi-user redirected walking and resetting using artificial potential fields. IEEE transactions on visualization and computer graphics 25, 5 (2019), 2022–2031.Google ScholarCross Ref
6. Eric R Bachmann, Jeanette Holm, Michael A Zmuda, and Eric Hodgson. 2013. Collision prediction and prevention in a simultaneous two-user immersive virtual environment. In 2013 IEEE Virtual Reality (VR). IEEE, 89–90.Google Scholar
7. Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston. 2009. Curriculum learning. In Proceedings of the 26th annual international conference on machine learning. 41–48.Google ScholarDigital Library
8. Luke Bölling, Niklas Stein, Frank Steinicke, and Markus Lappe. 2019. Shrinking circles: Adaptation to increased curvature gain in redirected walking. IEEE transactions on visualization and computer graphics 25, 5 (2019), 2032–2039.Google Scholar
9. Yuchen Chang, Keigo Matsumoto, Takuji Narumi, Tomohiro Tanikawa, and Michitaka Hirose. 2021. Redirection controller using reinforcement learning. IEEE Access 9 (2021), 145083–145097.Google ScholarCross Ref
10. Ze-Yin Chen, Yi-Jun Li, Miao Wang, Frank Steinicke, and Qinping Zhao. 2021. A Reinforcement Learning Approach to Redirected Walking with Passive Haptic Feedback. In 2021 IEEE International Symposium on Mixed and Augmented Reality (ISMAR). IEEE, 184–192.Google ScholarCross Ref
11. Yong-Hun Cho, Dae-Hong Min, Jin-Suk Huh, Se-Hee Lee, June-Seop Yoon, and InKwon Lee. 2021. Walking Outside the Box: Estimation of Detection Thresholds for Non-Forward Steps. In 2021 IEEE Virtual Reality and 3D User Interfaces (VR). IEEE, 448–454.Google Scholar
12. Emily Dao, Andreea Muresan, Kasper Hornbæk, and Jarrod Knibbe. 2021. Bad Breakdowns, Useful Seams, and Face Slapping: Analysis of VR Fails on YouTube. In Proceedings of the 2021 CHI Conference on Human Factors in Computing Systems. 1–14.Google ScholarDigital Library
13. Tianyang Dong, Xianwei Chen, Yifan Song, Wenyuan Ying, and Jing Fan. 2020. Dynamic artificial potential fields for multi-user redirected walking. In 2020 IEEE Conference on Virtual Reality and 3D User Interfaces (VR). IEEE, 146–154.Google ScholarCross Ref
14. Tianyang Dong, Yue Shen, Tieqi Gao, and Jing Fan. 2021a. Dynamic Density-based Redirected Walking Towards Multi-user Virtual Environments. In 2021 IEEE Virtual Reality and 3D User Interfaces (VR). IEEE, 626–634.Google Scholar
15. Zhi-Chao Dong, Xiao-Ming Fu, Zeshi Yang, and Ligang Liu. 2019. Redirected smooth mappings for multiuser real walking in virtual reality. ACM Transactions on Graphics (TOG) 38, 5 (2019), 1–17.Google ScholarDigital Library
16. Zhi-Chao Dong, Xiao-Ming Fu, Chi Zhang, Kang Wu, and Ligang Liu. 2017. Smooth assembled mappings for large-scale real walking. ACM Transactions on Graphics (TOG) 36, 6 (2017), 1–13.Google ScholarDigital Library
17. Zhi-Chao Dong, Wenming Wu, Zenghao Xu, Qi Sun, Guanjie Yuan, Ligang Liu, and Xiao-Ming Fu. 2021b. Tailored Reality: Perception-aware Scene Restructuring for Adaptive VR Navigation. ACM Transactions on Graphics (TOG) 40, 5 (2021), 1–15.Google ScholarDigital Library
18. Qiang Du, Maria Emelianenko, and Lili Ju. 2006. Convergence of the Lloyd algorithm for computing centroidal Voronoi tessellations. SIAM journal on numerical analysis 44, 1 (2006), 102–119.Google Scholar
19. Qiang Du, Vance Faber, and Max Gunzburger. 1999. Centroidal Voronoi tessellations: Applications and algorithms. SIAM review 41, 4 (1999), 637–676.Google Scholar
20. Franz Faul, Edgar Erdfelder, Albert-Georg Lang, and Axel Buchner. 2007. G* Power 3: A flexible statistical power analysis program for the social, behavioral, and biomedical sciences. Behavior research methods 39, 2 (2007), 175–191.Google Scholar
21. Steven Fortune. 1987. A sweepline algorithm for Voronoi diagrams. Algorithmica 2, 1 (1987), 153–174.Google ScholarDigital Library
22. Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. 2018. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In International conference on machine learning. PMLR, 1861–1870.Google Scholar
23. Matthew Hausknecht and Peter Stone. 2015. Deep recurrent q-learning for partially observable mdps. In 2015 aaai fall symposium series.Google Scholar
24. Sepp Hochreiter and Jürgen Schmidhuber. 1997. Long short-term memory. Neural computation 9, 8 (1997), 1735–1780.Google Scholar
25. Eric Hodgson and Eric Bachmann. 2013. Comparing four approaches to generalized redirected walking: Simulation and live user data. IEEE transactions on visualization and computer graphics 19, 4 (2013), 634–643.Google Scholar
26. Eric Hodgson, Eric Bachmann, and Tyler Thrash. 2014. Performance of redirected walking algorithms in a constrained virtual world. IEEE transactions on visualization and computer graphics 20, 4 (2014), 579–587.Google ScholarDigital Library
27. Jeannette E Holm. 2012. Collision prediction and prevention in a simultaneous multi-user immersive virtual environment. Ph. D. Dissertation. Miami University.Google Scholar
28. Lu Jiang, Deyu Meng, Qian Zhao, Shiguang Shan, and Alexander G Hauptmann. 2015. Self-paced curriculum learning. In Twenty-Ninth AAAI Conference on Artificial Intelligence.Google ScholarDigital Library
29. Arthur Juliani, Vincent-Pierre Berges, Ervin Teng, Andrew Cohen, Jonathan Harper, Chris Elion, Chris Goy, Yuan Gao, Hunter Henry, Marwan Mattar, et al. 2018. Unity: A general platform for intelligent agents. arXiv preprint arXiv:1809.02627 (2018).Google Scholar
30. Leslie Pack Kaelbling, Michael L Littman, and Anthony R Cassandra. 1998. Planning and acting in partially observable stochastic domains. Artificial intelligence 101, 1–2 (1998), 99–134.Google Scholar
31. Robert S Kennedy, Norman E Lane, Kevin S Berbaum, and Michael G Lilienthal. 1993. Simulator sickness questionnaire: An enhanced method for quantifying simulator sickness. The international journal of aviation psychology 3, 3 (1993), 203–220.Google Scholar
32. Dooyoung Kim, Jae-eun Shin, Jeongmi Lee, and Woontack Woo. 2021. Adjusting Relative Translation Gains According to Space Size in Redirected Walking for Mixed Reality Mutual Space Generation. In 2021 IEEE Virtual Reality and 3D User Interfaces (VR). IEEE, 653–660.Google Scholar
33. Vijay R Konda and John N Tsitsiklis. 2000. Actor-critic algorithms. In Advances in neural information processing systems. 1008–1014.Google Scholar
34. Bruce Krogh. 1984. A generalized potential field approach to obstacle avoidance control. In Proc. SME Conf. on Robotics Research: The Next Five Years and Beyond, Bethlehem, PA, 1984. 11–22.Google Scholar
35. Eike Langbehn, Paul Lubos, Gerd Bruder, and Frank Steinicke. 2017. Bending the curve: Sensitivity to bending of curved paths and application in room-scale vr. IEEE transactions on visualization and computer graphics 23, 4 (2017), 1389–1398.Google Scholar
36. Eike Langbehn, Paul Lubos, and Frank Steinicke. 2018a. Evaluation of locomotion techniques for room-scale vr: Joystick, teleportation, and redirected walking. In Proceedings of the Virtual Reality International Conference-Laval Virtual. 1–9.Google ScholarDigital Library
37. Eike Langbehn, Frank Steinicke, Markus Lappe, Gregory F Welch, and Gerd Bruder. 2018b. In the blink of an eye: leveraging blink-induced suppression for imperceptible position and orientation redirection in virtual reality. ACM Transactions on Graphics (TOG) 37, 4 (2018), 1–11.Google ScholarDigital Library
38. Dong-Yong Lee, Yong-Hun Cho, and In-Kwon Lee. 2019. Real-time optimal planning for redirected walking using deep q-learning. In 2019 IEEE Conference on Virtual Reality and 3D User Interfaces (VR). IEEE, 63–71.Google ScholarCross Ref
39. Dong-Yong Lee, Yong-Hun Cho, Dae-Hong Min, and In-Kwon Lee. 2020. Optimal planning for redirected walking based on reinforcement learning in multi-user environment with irregularly shaped physical space. In 2020 IEEE Conference on Virtual Reality and 3D User Interfaces (VR). IEEE, 155–163.Google ScholarCross Ref
40. Changyang Li, Haikun Huang, Jyh-Ming Lien, and Lap-Fai Yu. 2021a. Synthesizing scene-aware virtual reality teleport graphs. ACM Transactions on Graphics (TOG) 40, 6 (2021), 1–15.Google ScholarDigital Library
41. Rongpeng Li, Chujie Wang, Zhifeng Zhao, Rongbin Guo, and Honggang Zhang. 2020. The LSTM-based advantage actor-critic learning for resource management in network slicing with user mobility. IEEE Communications Letters 24, 9 (2020), 2005–2009.Google ScholarCross Ref
42. Yi-Jun Li, De-Rong Jin, Miao Wang, Jun-Long Chen, Frank Steinicke, Shi-Min Hu, and Qinping Zhao. 2021b. Detection Thresholds with Joint Horizontal and Vertical Gains in Redirected Jumping. In 2021 IEEE Virtual Reality and 3D User Interfaces (VR). IEEE, 95–102.Google Scholar
43. Yi-Jun Li, Miao Wang, Frank Steinicke, and Qinping Zhao. 2021c. OpenRDW: A Redirected Walking Library and Benchmark with Multi-User, Learning-based Functionalities and State-of-the-art Algorithms. In 2021 IEEE International Symposium on Mixed and Augmented Reality (ISMAR). IEEE, 21–30.Google Scholar
44. JJ-W Lin, Henry Been-Lirn Duh, Donald E Parker, Habib Abi-Rached, and Thomas A Furness. 2002. Effects of field of view on presence, enjoyment, memory, and simulator sickness in a virtual environment. In Proceedings ieee virtual reality 2002. IEEE, 164–171.Google ScholarCross Ref
45. Sebastian Marwecki, Maximilian Brehm, Lukas Wagner, Lung-Pan Cheng, Florian’Floyd’ Mueller, and Patrick Baudisch. 2018. Virtualspace-overloading physical space with multiple virtual reality users. In Proceedings of the 2018 CHI Conference on Human Factors in Computing Systems. 1–10.Google ScholarDigital Library
46. Justin Messinger, Eric Hodgson, and Eric R Bachmann. 2019. Effects of tracking area shape and size on artificial potential field redirected walking. In 2019 IEEE Conference on Virtual Reality and 3D User Interfaces (VR). IEEE, 72–80.Google ScholarCross Ref
47. Thomas Nescher, Ying-Yin Huang, and Andreas Kunz. 2014. Planning redirection techniques for optimal free walking experience using model predictive control. In 2014 IEEE Symposium on 3D User Interfaces (3DUI). IEEE, 111–118.Google ScholarCross Ref
48. Niels Christian Nilsson, Tabitha Peck, Gerd Bruder, Eri Hodgson, Stefania Serafin, Mary Whitton, Frank Steinicke, and Evan Suma Rosenberg. 2018. 15 years of research on redirected walking in immersive virtual environments. IEEE computer graphics and applications 38, 2 (2018), 44–56.Google ScholarDigital Library
49. Atsuyuki Okabe, Barry Boots, Kokichi Sugihara, and Sung Nok Chiu. 2009. Spatial tessellations: concepts and applications of Voronoi diagrams. Vol. 501. John Wiley & Sons.Google ScholarCross Ref
50. Martin L Puterman. 2014. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons.Google ScholarDigital Library
51. Prajit Ramachandran, Barret Zoph, and Quoc V Le. 2017. Searching for activation functions. arXiv preprint arXiv:1710.05941 (2017).Google Scholar
52. S. Razzaque. 2005. Redirected walking. Ph. D. Dissertation. The University of North Carolina at Chapel Hill.Google Scholar
53. Z. Kohn S. Razzaque and M. C. Whitton. 2001. Redirected walking. Proceedings of the Eurographics, Manchester, UK (2001), 5–7.Google Scholar
54. Thomas Schubert, Frank Friedmann, and Holger Regenbrecht. 2001. The experience of presence: Factor analytic insights. Presence: Teleoperators & Virtual Environments 10, 3 (2001), 266–281.Google ScholarDigital Library
55. John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. 2017. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347 (2017).Google Scholar
56. Ana Serrano, Diego Gutierrez, Belen Masia, Daniel Martin, and Karol Myszkowski. 2020. Imperceptible manipulation of lateral camera motion for improved virtual reality applications. Technical Report.Google Scholar
57. Wataru Shibayama and Shinichi Shirakawa. 2020. Reinforcement Learning-Based Redirection Controller for Efficient Redirected Walking in Virtual Maze Environment. In Computer Graphics International Conference. Springer, 33–45.Google Scholar
58. Daniel J Simons and Daniel T Levin. 1997. Change blindness. Trends in cognitive sciences 1, 7 (1997), 261–267.Google Scholar
59. Frank Steinicke, Gerd Bruder, Klaus Hinrichs, Jason Jerald, Harald Frenz, and Markus Lappe. 2009a. Real walking through virtual environments by redirection techniques. JVRB-Journal of Virtual Reality and Broadcasting 6, 2 (2009).Google Scholar
60. Frank Steinicke, Gerd Bruder, Klaus Hinrichs, and Pete Willemsen. 2010. Change blindness phenomena for stereoscopic projection systems. In 2010 IEEE Virtual Reality Conference (VR). IEEE, 187–194.Google ScholarDigital Library
61. Frank Steinicke, Gerd Bruder, Jason Jerald, Harald Frenz, and Markus Lappe. 2008a. Analyses of human sensitivity to redirected walking. In Proceedings of the 2008 ACM symposium on Virtual reality software and technology. 149–156.Google ScholarDigital Library
62. Frank Steinicke, Gerd Bruder, Jason Jerald, Harald Frenz, and Markus Lappe. 2009b. Estimation of detection thresholds for redirected walking techniques. IEEE transactions on visualization and computer graphics 16, 1 (2009), 17–27.Google Scholar
63. Frank Steinicke, Gerd Bruder, Timo Ropinski, and Klaus Hinrichs. 2008b. Moving towards generally applicable redirected walking. In Proceedings of the Virtual Reality International Conference (VRIC). IEEE Press, 15–24.Google Scholar
64. Ryan R Strauss, Raghuram Ramanujan, Andrew Becker, and Tabitha C Peck. 2020. A steering algorithm for redirected walking using reinforcement learning. IEEE transactions on visualization and computer graphics 26, 5 (2020), 1955–1963.Google ScholarCross Ref
65. Evan A Suma, Gerd Bruder, Frank Steinicke, David M Krum, and Mark Bolas. 2012a. A taxonomy for deploying redirection techniques in immersive virtual environments. In 2012 IEEE Virtual Reality Workshops (VRW). IEEE, 43–46.Google ScholarDigital Library
66. Evan A Suma, Seth Clark, David Krum, Samantha Finkelstein, Mark Bolas, and Zachary Warte. 2011. Leveraging change blindness for redirection in virtual environments. In 2011 IEEE Virtual Reality Conference. IEEE, 159–166.Google ScholarDigital Library
67. Evan A Suma, Zachary Lipps, Samantha Finkelstein, David M Krum, and Mark Bolas. 2012b. Impossible spaces: Maximizing natural walking in virtual environments with self-overlapping architecture. IEEE Transactions on Visualization and Computer Graphics 18, 4 (2012), 555–564.Google ScholarDigital Library
68. Qi Sun, Anjul Patney, Li-Yi Wei, Omer Shapira, Jingwan Lu, Paul Asente, Suwen Zhu, Morgan McGuire, David Luebke, and Arie Kaufman. 2018. Towards virtual reality infinite walking: dynamic saccadic redirection. ACM Transactions on Graphics (TOG) 37, 4 (2018), 1–13.Google ScholarDigital Library
69. Richard S Sutton, Andrew G Barto, et al. 1998. Introduction to reinforcement learning. Vol. 135. MIT press Cambridge.Google Scholar
70. Jerald Thomas and Evan Suma Rosenberg. 2019. A general reactive algorithm for redirected walking using artificial potential functions. In 2019 IEEE Conference on Virtual Reality and 3D User Interfaces (VR). IEEE, 56–62.Google ScholarCross Ref
71. Martin Usoh, Kevin Arthur, Mary C Whitton, Rui Bastos, Anthony Steed, Mel Slater, and Frederick P Brooks Jr. 1999. Walking > walking-in-place > flying, in virtual environments. In Proceedings of the 26th annual conference on Computer graphics and interactive techniques. 359–364.Google ScholarDigital Library
72. Martin Usoh, Ernest Catena, Sima Arman, and Mel Slater. 2000. Using presence questionnaires in reality. Presence 9, 5 (2000), 497–503.Google ScholarDigital Library
73. Khrystyna Vasylevska, Hannes Kaufmann, Mark Bolas, and Evan A Suma. 2013. Flexible spaces: Dynamic layout generation for infinite walking in virtual environments. In 2013 IEEE Symposium on 3D User Interfaces (3DUI). IEEE, 39–42.Google ScholarCross Ref
74. Georges Voronoi. 1908. Nouvelles applications des paramètres continus à la théorie des formes quadratiques. Deuxième mémoire. Recherches sur les parallélloèdres primitifs. Journal für die reine und angewandte Mathematik (Crelles Journal) 1908, 134 (1908), 198–287.Google ScholarCross Ref
75. Christopher JCH Watkins and Peter Dayan. 1992. Q-learning. Machine learning 8, 3–4 (1992), 279–292.Google Scholar
76. Betsy Williams, Gayathri Narasimham, Bjoern Rump, Timothy P McNamara, Thomas H Carr, John Rieser, and Bobby Bodenheimer. 2007. Exploring large virtual environments with an HMD when physical space is limited. In Proceedings of the 4th symposium on Applied perception in graphics and visualization. 41–48.Google ScholarDigital Library
77. Niall L Williams, Aniket Bera, and Dinesh Manocha. 2021a. Arc: Alignment-based redirection controller for redirected walking in complex environments. IEEE Transactions on Visualization and Computer Graphics 27, 5 (2021), 2535–2544.Google ScholarCross Ref
78. Niall L Williams, Aniket Bera, and Dinesh Manocha. 2021b. Redirected walking in static and dynamic scenes using visibility polygons. IEEE Transactions on Visualization and Computer Graphics 27, 11 (2021), 4267–4277.Google ScholarDigital Library
79. Niall L Williams, Aniket Bera, and Dinesh Manocha. 2022. ENI: Quantifying Environment Compatibility for Natural Walking in Virtual Reality. arXiv preprint arXiv:2201.01261 (2022).Google Scholar
80. Niall L Williams and Tabitha C Peck. 2019. Estimation of rotation gain thresholds considering fov, gender, and distractors. IEEE transactions on visualization and computer graphics 25, 11 (2019), 3158–3168.Google ScholarCross Ref
81. Ronald J Williams. 1992. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine learning 8, 3 (1992), 229–256.Google Scholar
82. Jackie Yang, Christian Holz, Eyal Ofek, and Andrew D Wilson. 2019. Dreamwalker: Substituting real-world walking experiences with a virtual reality. In Proceedings of the 32nd Annual ACM Symposium on User Interface Software and Technology. 1093–1107.Google ScholarDigital Library
83. Jingxin Zhang, Eike Langbehn, Dennis Krupke, Nicholas Katzakis, and Frank Steinicke. 2018. Detection thresholds for rotation and translation gains in 360 video-based telepresence systems. IEEE transactions on visualization and computer graphics 24, 4 (2018), 1671–1680.Google ScholarDigital Library
84. Michael A Zmuda, Joshua L Wonser, Eric R Bachmann, and Eric Hodgson. 2013. Optimizing constrained-environment redirected walking instructions using search techniques. IEEE transactions on visualization and computer graphics 19, 11 (2013), 1872–1884.Google ScholarDigital Library