FRA641 Class project :Solved Maze

Project : Solved Maze

Objective

1. เรียนรู้วิธีวิเคราะห์ปัญหาอย่างเป็นระบบเพื่อให้อัลกอริทึมได้รับมาเพื่อแก้ปัญหา  

2.เรียนรู้เกี่ยวกับการใช้อัลกอริธึมดังกล่าวเพื่อแก้ปัญหาจริง  

3.เรียนรู้เกี่ยวกับแอปพลิเคชันของอัลกอริทึมดังกล่าวเพื่อเริ่มต้นกับโลกของอัลกอริทึมหุ่นยนต์ ปัญญาประดิษฐ์ และอื่นๆ 

ขอบเขตของงาน

1. เขาวงกตที่มีขนาด 3000×3000 mm. หรือ 10×10 block. โดยหุ่นยนต์ Lidarbot จะวิ่งในเขาวงกตทั้งหมด 2 รอบ
2. LidarBot สำรวจเส้นทางเข้าวงกตโดยเดินทางสำรวจแผนที่ทั้งหมดในรอบแรก
3. LidarBot สามารถคำนวณเพื่อหาทางออกที่สั้นที่สุดในการวิ่งรอบที่ 2 และแสดงวิธีการเดินทางออกมาของหุ่นยนต์
4. LidarBot สามารถเคลื่อนที่ในสนามที่สมมาตรและไม่สมมาตรได้

Algorithm ที่ใช้

1.การรับรู้ของโปรแกรม : เริ่มจากการทำแผนที่สำหรับการสร้างเป็นตำแหน่งอ้างอิงให้กับ algorithm เพื่อให้ตัว algorithm สามารถเข้าใจได้ว่าตัวเองกำลังทำอะไรอยู่ มันจะต้องเข้าใจถึงตำแหน่งที่อยู่ จุดที่อยู่ เส้นที่อยู่ และ box ที่อยู่ ซึ่งกำหนดเป็น Ai,j ตามรูปด้านล่าง

ผลลัพธ์การเดินทางครั้งแรก

2. BFS หรือ Breadth-First Search (การค้นหาแบบกว้าง)

ขั้นตอนการทำงานของ BFS ได้แก่:

1. เริ่มต้นที่โหนดเริ่มต้น (start node) และทำเครื่องหมายว่าโหนดนั้นถูกเยือนแล้ว.

2. ท่องไปยังโหนดลูกทุกตัวของโหนดปัจจุบัน (ถ้ามี) และทำเครื่องหมายว่าลูกของโหนดนั้นถูกเยือน.

3. ทำซ้ำขั้นตอน 2 สำหรับทุกๆ โหนดลูกที่ยังไม่ได้เยือน.

4. ทำซ้ำขั้นตอน 3 สำหรับโหนดลูกของโหนดล่าสุดที่ยังไม่ได้เยือน.

5. ทำซ้ำขั้นตอน 4 จนกว่าทุกโหนดที่เป็นไปได้จะถูกเยือน.

BFS มักถูกใช้ในการหาทางที่สั้นที่สุด, ค้นหาคำตอบในปัญหา Maze (ปัญหาทางใน Labrynth), หรือในการค้นหาโครงสร้างข้อมูลแบบกราฟ เพื่อตรวจสอบความสัมพันธ์ระหว่างโหนดและระยะทางที่ใกล้ที่สุด.

จากคลิปหลังจากได้รับค่า csv file มาแล้วนำค่าไปคำนวนหาเส้นทางที่สั้นที่สุด โดยกำหนดจุด Start = (1,5) และ จุด Goal = (10,1)

Content

Team Members

1. 66340700401 นายกวิน แย้มด่วน 

2. 66340700402 นายกอบโชค ปภานิธิสกุล 

3. 66340700404 นายเมธีรัฐ เสนคำสอน 

4. 66340700405 นายวชิรเมษฐ์ กุลธนาเรืองนนท์ 

5. 66340700406 นายวิธวินท์ ปิ่นประเสริฐ