Class Project : Lidar bot for maze solving (SNC Group)

สวัสดีครับ วันนี้จะมาแบ่งปันความรู้ที่ได้รับจากการทำโปรเจ็คในวิชา Computer programming for robotics กันครับ

ก่อนอื่นเลยโจทย์ที่ได้รับคือ

หุ่นยนต์สี่ล้อสำรวจเส้นทางเข้าวงกตโดยเดินทางสำรวจแผนที่ในรอบแรก
หุ่นยนต์ตัวเดิมจะนำแผนที่มาคำนวณเพื่อหาทางออกที่ดีที่สุด

Project ของรายวิชานี้เน้นที่การคิดเชิงอัลกอริทึมและการเขียนโปรแกรม นักเรียนออกแบบเขาวงกต 4000×4000 mm. ที่เรียบง่าย

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

Algorithm ที่ใช้

Dept First search เป็น Algorithm หลักที่ใช้ในการหาเส้นทางที่ดีที่สุด โดยหลักการที่นำมาใช้เป็นดังนี้

1.สำรวจเส้นทางโดยรวมโดยใช้หลักการให้ robot วิ่งโดยมีการเรียงลำดับความสำคัญดังนี้

ถ้าเจอซ้าย ให้ไปซ้าย
ถ้าไม่มีซ้าย ให้ตรง
ถ้าไม่มีตรง ให้เลี้ยวขวา
ถ้าไม่สามารถไปไหนได้ ให้กลับรถ
ในขณะที่เดินสำรวจเส้นทาง จะมีการเก็บค่า coordinate (x, y) ไว้ในทุกๆการเดินไปช่องต่อไป

โดยตัวแปรที่ใช้ในการเก็บค่าเส้นทาง เราจะใช้ array 2 มิติในการเก็บ โดยมีสองตัวแปรคือ

visited: เป็น array ตัวแรกที่เก็บ coordinate ทั้งหมดที่หุ่นยนต์เดินผ่าน

stack: เป็น array ที่จะเก็บแค่เส้นทางที่ดีที่สุด โดยทุกครั้งที่เดินผ่านเส้นทางที่ไม่ถูกต้อง (วังวน หรือทางตัน) จะมีฟังชั่นก์ที่ทำการ slice coordinate ที่เป็นเป็นเส้นทางที่ไม่ถูกต้องออก ดังนั้นเมื่อหุ่นยนต์เดินทางจนถึงเส้นชัย ตัวแปร stack สุดท้ายที่ได้จะเป็นลำดับของ coordinate ที่ดีที่สุด โดยรายละเอียดอยู่ในข้อ 2

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

รูปภาพการเดินทางครั้งแรก โดยพื้นที่สีเหลืองจะเป็นพื้นที่ทั้งหมดที่หุ่นยนต์เดินทางไปโดยใช้หลักการตามข้อ 1

2. การนำ Stack มาใช้ในการ Solve Maze

ก่อนที่เราจะมาใช้ Stack มา Solve Maze เรามาดูวิธีจัดการของ Stack เพื่อให้ได้ Path ที่ในการ Solve Maze กันนะครับ

ใน Array Stack จะเก็บ coordinate ที่เดินไปใน Maze
Stack จะเช็คค่า coordinate ล่าสุดที่นำมาเก็บกับตัวก่อนหน้าทุกครั้งว่าซ้ำหรือไม่
เมื่อเจอค่าซ้ำ Stack จะ ลบค่าล่าสุดและค่าที่อยู่ระหว่างค่าที่ซ้ำกันไว้ทั้งหมด หมายความว่า ค่าที่ซ้ำกันนั้นเปรียบเสมือน – Robot เดินกลับมาทางเดิมซึ่งเป็นทางวน หรือ ทางตัน
ผลลัพธ์สุดท้ายของ Stack นั้นจะได้ coordinate ที่ไม่ซ้ำกันและเป็นทางออกนั้นเอง

และเมื่อเรามาดูที่ Array Stack นั้น เราได้ coordinate ดังนี้

[[0,0],[0,1],[1,1],[2,1],[2,0],[3,0],[3,1],[4,1],[4,2],[5,2],[5,3],[5,4],[6,4],[7,4],[8,4],[9,4],[10,4]]

ซึ่งเมื่อนำ coordinate ต่างๆมาต่อจะได้ Path ดังนี้

สุดท้ายเมื่อได้ Path ในการ Solve Maze มาแล้ว ก็จะเหลือให้ Robot วิ่งตาม Path นี้โดยแปลงจากทิศทางปัจจุบันของ Robot และ coordinate ที่จะเดินถัดไป จะได้ sequence การทำงานของ Robot ดังนี้

[“FW”,”turn right”,”FW”,”FW”,”turn right”,”FW”,”turn left”,”FW”,”turn left”,”FW”,”turn right”, “FW”,”turn left”,”FW”,”turn right”,”FW”,”turn left”,”FW”,”FW”,”turn right”,”FW”,”FW”,”FW”,”FW”,”FW”]

ซึ่งจะเป็น sequence ให้ Robot ทำตามและ Robot จะสามารถออกจาก Maze ได้

อุปกรณ์ที่ใช้