localization

goal recognition

pathplaning

• static obsacle
• dynamic obsable

Spatial Decomposition

Uniform sample (Uniform grid)

แบ่งเป็นส่วนๆเท่าๆกัน

Structure: Array Grid: Square

Quadtree

แบ่งตามวัตถุ ตรงไหนมีวัตถุจะแบ่งออกเป็นส่วนๆเยอะขึ้น การเก็บข้อมูลจะเป็นแบบ Tree

Structure: Tree Grid: Square

Binary Space Partifioning Tree (BSP)

แบ่งพื้นที่ออกเป็น Binary Tree ไปเรื่อยๆ

Structure: Tree Grid: Rectangle

Exact

แบ่งออกเป็นส่วนๆโดยจะมีรูปร่างแบบไหนก็ได้

Structure: Grid: Any Shape

Configuration Space : C-Space

"Point Robot Assumption" เป็นการมองหุ่นยนต์ให้เป็นเหมือนจุด แล้วเก็บค่า Obasacle ให้ขยายออกมาแทน จะได้ไม่ต้องเกิดการคำนวณซ้ำๆ

Obstacle region in C-Space

Constraints in C-Space

Holonomic Constraint

Nonholonomic Constraint

Path in C-Space

การแปลงจาก initial configuration ไปยัง goal configuration

Path Planning

Discrete Path Planning

Cell Decomposition Path Planning

เผาหญ้าา : ให้คะแนนน้อยอยู่ใกล้วัตถุ เวฟฟรอน : ให้คะแนนน้อยอยู่ใกล้เป้าหมาย

creating map