Analysis of navigation of robot populations using finite automata models

การวิเคราะห์การนำทางของหุ่นยนต์โดยใช้แบบจำลองไฟไนต์ออโตเมตา

Name: Banhan Bootsingha

LCSH: ROBOTS -- CONTROL

keyword: Adjacency matrix

; Finite automata

Abstract: Mobile rescue robots have been suggested as an alternative to human rescuers for rescuing people in dangerous environments, e.g., people trapped by fire in a building. In this thesis, the movements of a heterogeneous population of rescue robots in a discrete environment are modeled using matrix methods. Two types of rescue problem are considered. In the first type, the robots must travel from a specified finite set of start states (rooms in a building) to a specified finite set of target rooms. If possible, each target room should be reached by one robot. In the second type of the problem, the robots must reach the target rooms and then return to a specified set of safe rooms. The paths of each robot are classified using the concepts of blocked, blocked but controllable and unblocked paths. The allowed motions of each robot are modeled using automata theory. The transition function and transition diagram are obtained. The transition diagram is then modeled to generate digraph and an adjacency matrix for the digraph is constructed. An algorithm based on powers of the adjacency matrix is presented which can derive blocked and controllability properties for the paths of each robot. These properties of the population of mobile rescue robots are then easily obtained for the two types of rescue problems. A Matlab program based on the algorithm has been developed and tested on randomly selected problems with a range of 3 to 30 robots and target rooms in buildings with a range of 10 to 300 rooms.

Abstract: หุ่นยนต์ได้เข้ามามีบทบาทและเป็นทางเลือกในการช่วยเหลือชีวิตมนุษย์ เมื่ออยู่ในพื้นที่ อันตราย เช่น การช่วยเหลือคนที่ติดอยู่บนอาคารที่ไฟไหม้ ในวิทยานิพนธ์นี้จำลองการเคลื่อนที่ ของหุ่นยนต์ที่มีความสามารถแตกต่างกันในสภาพแวดล้อมที่ไม่ต่อเนื่องด้วยวิธีเมทริกซ์ โดยจะ พิจารณาปัญหาในสองกรณี คือ กรณีแรก หุ่นยนต์จะต้องเดินทางจากสถานะเริ่มต้น (ห้องใน อาคาร) ที่กำหนดไปยังห้องเป้าหมายที่ระบุ ซึ่งหุ่นยนต์ 1 ตัว จะไปถึง 1 ห้องเป้าหมายเท่านั้น กรณีที่สอง หุ่นยนต์ต้องไปยังเป้าหมายและกลับมายังที่ห้องปลอดภัยที่กำหนด ในการวิเคราะห์ ทางเดินของหุ่นยนต์แต่ละตัวถูกจัดกลุ่มโดยใช้หลักการของเส้นทาง 3 แบบ คือ เส้นทางที่มีสิ่ง กีดขวาง เส้นทางที่มีสิ่งกีดขวางแต่สามารถควบคุมได้ และเส้นทางที่ไม่มีสิ่งกีดขวาง ซึ่งจะ จำลองการเคลื่อนที่ของหุ่นยนต์แต่ละตัวโดยใช้ทฤษฎีออโตเมตา ที่ประกอบด้วยฟังก์ชันเปลี่ยน สถานะและแผนภาพเปลี่ยนสถานะของหุ่นยนต์ โดยแผนภาพเปลี่ยนสถานะจะถูกนำไปสร้าง กราฟระบุทิศทางและเมทริกซ์ประชิด (Adjacency matrix) ขั้นตอนวิธีการที่ใช้ในงานวิจัยนี้ใช้ พื้นฐานของการยกกำลังเมทริกซ์ประชิด ซึ่งใช้อธิบายสมบัติของเส้นทางที่มีสิ่งกีดขวางและ สมบัติการควบคุมของหุ่นยนต์แต่ละตัว คุณสมบัติเหล่านี้ทำให้การแก้ปัญหาของหุ่นยนต์ ช่วยชีวิตสามารถทำได้ง่ายขึ้น งานวิจัยนี้ได้พัฒนาโปรแกรมแม็ทแล็บ (Matlab) จากขั้นตอน วิธีการข้างต้นและทดสอบกับปัญหาที่มีการสุ่มแบบคัดเลือก โดยใช้หุ่นยนต์จำนวน 3 ถึง 30 ตัว และห้องเป้าหมายเท่ากับจำนวนหุ่นยนต์ จากห้องทั้งหมด 10 ถึง 300 ห้อง

King Mongkut's Institute of Technology North Bangkok. Central Library

Address: Bangkok

Email: library@kmutnb.ac.th

Name: Utomporn Phalavonk

Role: Thesis advisors

Email : upv@kmitnb.ac.th

Name: Elvin James Moore

Role: Thesis advisors

Created: 2006

Issued: 2550-08-21

Modified: 2550-08-21

วิทยานิพนธ์/Thesis

CallNumber: Thesis MMA B3B

eng

DegreeName: Master of science

Level: Master's Degree

Descipline: Applied Mathematics

Grantor: สถาบันเทคโนโลยีพระจอมเกล้าพระนครเหนือ

©copyrights King Mongkut's University of Technology North Bangkok

ลำดับที่.	ชื่อแฟ้มข้อมูล	ขนาดแฟ้มข้อมูล	จำนวนเข้าถึง	วัน-เวลาเข้าถึงล่าสุด
1	mma0015.pdf	616.55 KB	131	2024-02-16 10:02:04

ใช้เวลา

0.031571 วินาที