Chulalongkorn University Theses and Dissertations (Chula ETD)

อัลกอริทึมการวางวิถีเรบกราฟสำหรับการจำลองฝูงชน

Other Title (Parallel Title in Other Language of ETD)

Reeb graph path planning algorithm for crowd simulation

Year (A.D.)

2011

Document Type

Thesis

First Advisor

พิษณุ คนองชัยยศ

Faculty/College

Faculty of Engineering (คณะวิศวกรรมศาสตร์)

Degree Name

วิทยาศาสตรมหาบัณฑิต

Degree Level

ปริญญาโท

Degree Discipline

วิทยาศาสตร์คอมพิวเตอร์

DOI

10.58837/CHULA.THE.2011.1387

Abstract

งานวิจัยนี้เสนออัลกอริทึมการวางวิถีสำหรับการจำลองฝูงชนโดยอัลกอริทึมในการวางวิถีแบบต่างๆที่ผ่านมาเมื่อนำมาประยุกต์ใช้กับการสร้างภาพเคลื่อนไหวฝูงชนนั้น จะพบว่านอกเหนือจากข้อจำกัดต่าง ๆ เช่นการใช้ตารางกริด(Grid-Based search) นั้นวิถีที่ได้จะขึ้นกับความเหมาะสมของการกำหนดขนาดตารางซึ่งไม่มีหลักการตายตัว ส่วนวิถีการเคลื่อนที่ตามวิธีพลังงานสนามศักย์ (Potential field) จะมีข้อจำกัดในเรื่องจุดต่ำสุดเฉพาะที่ (Local minima) ทำให้อาจจะได้วิถีทางตัน ส่วนวิธีเรขาคณิต (Geometric algorithms) หรือวิธีเชิงสุ่ม(Sampling-based algorithm)ก็อาจจะได้วิถีที่ไม่เป็นแนวกลางและซับซ้อนซึ่งทำให้การเคลื่อนที่ของฝูงชนมีการชนมากขึ้น งานวิจัยนี้จึงมุ่งเน้นที่การออกแบบอัลกอริทึมวางวิถีสำหรับการจำลองฝูงชนที่ใช้เวลาในการคำนวณน้อยและวิถีที่ได้ครอบคลุมสภาพแวดล้อมทั้งหมด เหมาะกับการจำลองการเคลื่อนที่ของฝูงชนคือวางตัวในแนวกลางของพื้นที่ว่างและไม่มีวิถีที่แตกกิ่งซับซ้อน โดยเริ่มจากประยุกต์ต้นไม้อัฐภาค (Octree) ช่วยในการแบ่งพื้นที่ว่างและสิ่งกีดขวางออกเป็นตารางกริดแปดส่วนจนกว่าในพื้นที่จะว่างหรือมีแต่สิ่งกีดขวางอยู่ ส่วนในการสร้างเรบกราฟ (Reeb graph) สร้าง เรบกราฟขึ้น โดยกำหนดเซตระดับให้กับพื้นที่ว่างแบ่งออกเป็นเซต และกำหนดให้แต่ละเซตระดับสมนัยกับปมของเรบ กราฟ (Reeb node) ซึ่งอยู่กลางปริมาตรของพื้นที่ว่าง แล้วเชื่อมต่อด้วยเส้นเชื่อมของเรบกราฟ (Reeb edges) โดยจะกำหนดปมของเรบ กราฟ ท้ายสุดจะได้วิถีการเคลื่อนที่ ผลจากการทดลองพบว่าวิถีการเคลื่อนที่ที่ได้จากอัลกอริทึมการวางวิถีสำหรับการจำลองฝูงชน แสดงการเชื่อมต่อของพื้นที่ว่างที่เคลื่อนที่ได้และวางตัวในแนวกลางห่างจากสิ่งกีดขวางโดยวิถีที่ได้จะเรียบง่ายเหมาะกับการเคลื่อนที่ฝูงชนและใช้เวลาในการคำนวณน้อย

Other Abstract (Other language abstract of ETD)

This research proposes an algorithm for Path planning of crowd simulation. Several algorithms such as grid-based search method, potential field and geometric algorithms can be used for path planning. Efficiency of path generated by grid-based method depends on the size of the grid, while path from potential field method may have local minima. Geometric algorithm usually creates path not lying in the central of the free space or too complex which is not proper for animation of the massive crowd because it might lead to high obstacle collision of crowd. In this research proposes a less time-complexity path planning algorithm, create a central path of the free space for the crowd simulation. We represent the path with Reeb graph generated by Octree Space Partition. After using Octree Space Partition to divide space and obstacles into several cubes of free space and obstacle space, we map all free space grids into level sets. Each level set corresponds to a Reeb node connecting to the neighboring node by Reeb edges. We finally obtain the Reeb graph representing central path lying in the central of the free space. The experimental results demonstrate that paths generated from the proposed algorithm can represent free space connectivity and lying in the central of the free space. These simple paths are suitable for crowd simulation. Finally the time-complexity of the algorithm is also not expensive.

Link to Full Text

Share

COinS