11071_Thiết kế và điều khiển robot tự hành dò đường trong mê cung

BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT TP. HỒ CHÍ MINH
KHOA ĐIỆN – ĐIỆN TỬ
BỘ MÔN TỰ ĐỘNG ĐIỀU KHIỂN
—–—–

ĐỒ ÁN TỐT NGHIỆP

ĐỀ TÀI:
Thiết Kế Và Điều Khiển Robot Tự Hành Dò
Đường Trong Mê Cung

GVHD: TS. Nguyễn Minh Tâm

SVTH:
Đỗ Trường Giang 08118020

Nguyễn Phước Khánh 08118036

THÀNH PHỐ HỒ CHÍ MINH, THÁNG 07 NĂM 2012
www.dienvietnam.vn

Bộ Giáo Dục Và Đào Tạo
Trường Đại Học SPKT TP.HCM
Khoa: Điện – Điện tử
Cộng Hòa Xã Hội Chủ Nghĩa Việt Nam
Độc Lập – Tự Do – Hạnh Phúc
—o0o—

—o0o—

NHIỆM VỤ ĐỒ ÁN TỐT NGHIỆP
Họ và tên sinh viên:
Đỗ Trường Giang
MSSV:
08118020

Nguyễn Phước Khánh
MSSV:
08118036
Lớp:
081180B
Ngành:
Công Nghệ Điện Tự Động
1.Tên đề tài:
Thiết Kế và Điều Khiển Robot Tự Hành Dò Đường Trong Mê
Cung
2. Mục tiêu và giới hạn:
Mục tiêu của đề tài là thiết kế, thi công, điều khiển robot tự hành. Robot tự
hành có thể hoạt động ổn định, tự tìm đường đi đến vị trí đích đã xác định sẵn trong
mê cung, có thể học nhanh chóng cách tìm đường đi khi thay đổi hình dạng mê cung,
sử dụng thuật toán tìm kiếm theo chiều sâu trong trí tuệ nhân tạo.
Giới hạn của đề tài, robot tự hành chỉ tìm được đường đi đến vị trí đích đã định
sẵn, sử dụng thuật toán tìm kiếm theo chiều sâu trong trí tuệ nhân tạo.
3. Ngày giao đề tài:
4. Ngày hoàn thành:
TPHCM, tháng n m 2 2

TPHCM, tháng n m 2 2

Giáo viên hướng d n
Chủ nhiệm Bộ môn ĐKTĐ

TS. Nguyễn Minh Tâm
TS.Nguyễn Minh Tâm
www.dienvietnam.vn

NHẬN XÉT CỦA GIÁO VIÊN HƯỚNG DẪN
Giáo viên hướng d n: TS. Nguyễn Minh Tâm
Họ và tên sinh viên:
Đỗ Trường Giang
MSSV:
08118020

Nguyễn Phước Khánh
MSSV:
08118036
Lớp:
081180B
Ngành:
Công Nghệ Điện Tự Động
1.Tên đề tài:
Thiết Kế và Điều Khiển Robot Tự Hành Dò Đường Trong Mê
Cung
Nhận xét của giáo viên hướng d n:
——————————————————————————————————
——————————————————————————————————
——————————————————————————————————
——————————————————————————————————
——————————————————————————————————
——————————————————————————————————
TPHCM, tháng n m 2 2

Giáo viên hướng d n

TS. Nguyễn Minh Tâm
www.dienvietnam.vn

NHẬN XÉT CỦA GIÁO VIÊN PHẢN BIỆN
Giáo viên phản biện:
Họ và tên sinh viên:
Đỗ Trường Giang
MSSV:
08118020

Nguyễn Phước Khánh
MSSV:
08118036
Lớp:
081180B
Ngành:
Công Nghệ Điện Tự Động
1.Tên đề tài:
Thiết Kế và Điều Khiển Robot Tự Hành Dò Đường Trong Mê
Cung
Nhận xét của giáo viên phản biện:
——————————————————————————————————
——————————————————————————————————
——————————————————————————————————
——————————————————————————————————
——————————————————————————————————
——————————————————————————————————
TPHCM, tháng n m 2 2

Giáo viên phản biện

www.dienvietnam.vn

Lời Cảm Ơn
Để có được thành công của đề tài như ngày hôm nay, trước hết nhóm sinh viên
thực hiện đề tài xin gửi lời cảm ơn chân thành nhất tới thầy Nguyễn Minh Tâm và thầy
Phạm Hoàng Thông, hai thầy đã định hướng và hỗ trợ về phương tiện, thiết bị cũng
như động viên, khích lệ tinh thần làm việc của các thành viên trong suốt thời gian thực
hiện đề tài.

Bên cạnh đó, những người thực hiện đề tài cũng xin gửi lời cảm ơn sâu sắc tới
các thầy cô giáo trong Bộ môn Tự động Điều khiển nói riêng và các thầy cô giáo trong
Khoa Điện-Điện Tử nói chung đã nhiệt tình giúp đỡ chúng em về các kiến thức liên
quan tới lĩnh vực nghiên cứu của đề tài trong suốt thời gian thực hiện đề tài, cũng như
các kiến thức mà các thầy cô đã truyền đạt cho chúng em trong suốt thời gian học tập
tại trường.

Chúng em cũng xin gửi lời cảm ơn chân thành đến Anh Lê Đình Cẩn và các bạn
trong đội Robocon SPK – Galaxy. Trong suốt thời gian thực hiện thi công phần cơ khí
của mô hình này, Anh và các bạn đã tận tình giúp đỡ về vật tư, máy móc và điều đặc
biệt là anh đã trực tiếp vẽ một số chi tiết phức tạp để có được mô hình mang tính kỹ
thuật và khoa học như robot hiện tại.

Nhóm sinh viên thực hiện đề tài

Đỗ Trường Giang
Nguyễn Phước Khánh
www.dienvietnam.vn

Mục lục
Lời Cảm Ơn …………………………………………………………………………………………………
8
Chương 1:…………………………………………………………………………………………………..
15
Tổng Quan
…………………………………………………………………………………………………..
15
. Đặt vấn đề:
…………………………………………………………………………………………..
15
.2 Mục tiêu đề tài: …………………………………………………………………………………….
15
.4 Nội dung nghiên cứu: …………………………………………………………………………….
16
1.5 Nội dung của đề tài: ………………………………………………………………………………
16
Chương 2:…………………………………………………………………………………………………..
17
Cơ sở lý thuyết …………………………………………………………………………………………….
17
2. Tổng quan về trí tuệ nhân tạo: …………………………………………………………………
17
2.2 Không gian bài toán : …………………………………………………………………………….
18
2.3 Chiến lược tìm kiếm :
…………………………………………………………………………….
19
2.3.2 Chiến lược tìm kiếm suy diễn lùi:
…………………………………………………………
19
2.4 Giải thuật tìm kiếm: ………………………………………………………………………………
19
2.4. Giải thuật tìm kiếm theo chiều rộng (Breadth_First_Search): …………………….
20
2.4.2 Giải thuật tìm kiếm theo chiều sâu (Depth First Search):
…………………………..
22
2.4.3 Giải thuật tìm kiếm truyền lùi ( Back Tracking search ) :…………………………..
23
2.5 Tìm Kiếm Heuristic:………………………………………………………………………………
25
2.5. Giải thuật tìm kiếm Best_First_Search: …………………………………………………
25
2.5.2 Hàm đánh giá heuristic:
……………………………………………………………………….
27
Chương 3:…………………………………………………………………………………………………..
28
Thiết kế và thi công mô hình robot tự hành
……………………………………………………….
28
3. Tổng quan về phần cứng Robot tự hành. …………………………………………………..
28
3.2 Lựa chọn thiết bị: ………………………………………………………………………………….
30
3.2.1
Lựa chọn động cơ. …………………………………………………………………………..
30
www.dienvietnam.vn

3.2.2 Lựa chọn cảm biến: …………………………………………………………………………….
31
3.3 Thiết kế mạch điện cho Robot:
………………………………………………………………..
31
3.3. Giao diện TWI (I2C): ………………………………………………………………………….
34
3.3.2 TWI trên AVR: ………………………………………………………………………………….
39
3.4 Thiết kế mạch điện tử
…………………………………………………………………………….
51
3.4.1 Mạch cảm biến dùng quang trở …………………………………………………………….
51
3.4.2 Mạch điều khiển động cơ …………………………………………………………………….
51
3.4.3 Mạch giao tiếp EEPROM:
……………………………………………………………………
55
3.4.4 Mạch giao tiếp máy tính: ……………………………………………………………………..
56
Chương 4:…………………………………………………………………………………………………..
57
Thuật toán điều khiển ……………………………………………………………………………………
57
4. Các phương pháp giải quyết vấn đề cơ bản:……………………………………………….
57
4. . Các chiến lược tìm kiếm:
……………………………………………………………………..
57
4. .2 Tìm kiếm theo chiều sâu:……………………………………………………………………..
57
4.2 Lưu đồ giải thuật tìm đường đi cho Robot: ………………………………………………..
59
Chương 5:…………………………………………………………………………………………………..
61
Kết quả thực nghiệm
……………………………………………………………………………………..
61
5.1 Robot đã được thiết kế: ………………………………………………………………………….
61
5.2 Kết quả thực nghiệm robot tìm đường: ……………………………………………………..
62
Chương 6:…………………………………………………………………………………………………..
66
Kết luận và hướng phát triển đề tài ………………………………………………………………….
66
6. Kết Luận: …………………………………………………………………………………………….
66
6.2 Hướng phát triển: ………………………………………………………………………………….
66
Tài liệu tham khảo ………………………………………………………………………………………
67

www.dienvietnam.vn

Danh mục các hình
Hình 2.1
Không gian trạng thái của bài toán tìm kiếm theo chiều rộng
Hình 2.2
Không gian trạng thái của bài toán tìm kiếm theo chiều sâu
Hình 3.1
Robot tự hành dò đường trong mê cung đã được thiết kế.
Hình 3.2
Sơ đồ khối Robot tự hành
Hình 3.3
Vi điều khiển ATmegaA
Hình 3.4
Sơ đồ cấu trúc ATmega8A
Hình 3.5
Mạng TWI (I2C) với nhiều thiết bị và 2 điện trở kéo lên cho SDA, SCL.
Hình 3.6
Quá trình lấy m u dữ liệu nối tiếp.
Hình 3.7
Mô tả các Master tạo ra START, STOP và REPEAT START.
Hình 3.8
Mô tả định dạng gói dữ liệu trong TWI(I2C)
Hình 3.9
Khung truyền thông thường
Hình 3.10 Master truyền dữ liệu.
Hình 3.11 Master nhận dữ liệu.
Hình 3.12 Slave nhận dữ liệu.
Hình 3.13 Slave truyền dữ liệu.
Hình 3.14 Mạch cầu H
Hình 3.15 Nguyên lý hoạt động của mạch cầu H
Hình 3.16 Sơ đồ chân của IC L298 (phải) và IC L298 (trái)
Hình 3.17 Sơ đồ nguyên lý của IC L298.
Hình 3.18 Sơ đồ nguyên lý mạch điều khiển động cơ
Hình 3.19 Sơ đồ nguyên lý mạch giao tiếp EEPROM
Hình 3.20 Sơ đồ nguyên lý mạch giao tiếp máy tính
Hình 4.1
Tìm kiếm theo chiều sâu
Hình 5.1
Robot tự hành dò đường trong mê cung
Hình 5.2
Mô phỏng mê cung
www.dienvietnam.vn

Hình 5.3
Lần chạy đầu tiên
Hình 5.4
Lần chạy thứ 2
Hình 5.5
Lần chạy thứ 3
Hình 5.6
Lần chạy thứ 4
Hình 5.7
Lần chạy thứ 5
Hình 5.8
Lần chạy thứ 6

www.dienvietnam.vn

Danh mục các bảng

Bảng 3.1
Thông số kỹ thuật của robot tự hành
Bảng 3.2
Tốc độ xung giữ nhịp tham khảo.
Bảng 3.3
Các chân điều khiển của ATmega8A

www.dienvietnam.vn

Danh mục các từ viết tắt
ACK: Acknowledgement
ADC: Analog Digital Converter
CPU: Central Processing Unit
DC: Drect Current
IC: Integrated Circuit
LCD: liquid crystal display
RISC: reduced instruction set computer
www.dienvietnam.vn
1. Tổng Quan

GVHD: TS. Nguyễn Minh Tâm

Trang 15

Chương 1:
Tổng Quan
1.1 Đặt vấn đề:
Trong giai đoạn hiện nay, máy tính có thể giải được rất nhiều bài toán khó mà
trước kia chưa giải quyết được. Mặc dù vậy v n còn một số lớn các bài toán rất thú vị
cần một thuật toán thích hợp để giải chúng. Trong đó, các bài toán sử dụng trí tuệ nhân
tạo là các bài toán thường gặp trong các ứng dụng thực tiễn. Ví dụ: ứng dụng phương
pháp mô phỏng luyện thép để tìm đường đi ngắn nhất cho xe cứu hỏa, bài toán chơi
cờ, hay robot tự hành…
Robot tự hành hay robot di động (mobile robot hay được viết tắt là mobot) được
định nghĩa là một loại xe robot có khả n ng tự dịch chuyển, tự vận động (có thể lập
trình lại được) dưới sự điều khiển tự động có khả n ng hoàn thành công việc được
giao. Theo lý thuyết, môi trường hoạt động của robot tự hành có thể là đất, nước,
không khí, không gian vũ trụ hay tổ hợp giữa chúng. Địa hình bề mặt mà robot di
chuyển trên đó có thể bằng phẳng hoặc thay đổi, lồi lõm. Đề tài nghiên cứu này đi sâu
nghiên cứu robot tự hành dò đường trong mê cung.
Robot tự hành (Mobile Robot) là một thành phần có vai trò quan trọng trong ngành
Robot học, một ngành không thể thiếu trong lĩnh vực tự động hóa. Cùng với sự phát
triển mạnh mẽ của các hệ thống tự động hóa, robot tự hành ngày một được hoàn thiện
và càng cho thấy lợi ích của nó trong công nghiệp và sinh hoạt. Một vấn đề rất được
quan tâm khi nghiên cứu về robot tự hành là làm thế nào để robot biết được vị trí nó
đang đứng và có thể di chuyển tới một vị trí xác định, đồng thời có thể tự động tránh
được các chướng ngại vật trên đường đi. Vì vậy, việc chế tạo thành công đề tài này sẽ
mở ra một hướng tiếp cận mới và góp phần thúc đẩy việc ứng dụng của robot ngày
càng nhiều vào trong đời sống hằng ngày và trong nghiên cứu chế tạo.
1.2 Mục tiêu đề tài:
Mục tiêu của đề tài là thiết kế, thi công, điều khiển robot tự hành. Robot tự hành có
thể hoạt động ổn định, tự tìm đường đi đến vị trí đích đã xác định sẵn trong mê cung,
có thể học nhanh chóng cách tìm đường đi khi thay đổi hình dạng mê cung, sử dụng
thuật toán tìm kiếm theo chiều sâu trong trí tuệ nhân tạo. Áp dụng công nghệ xử lý ảnh
để vẽ lại hình dạng mê cung và thực hiện giao tiếp máy tính.

www.dienvietnam.vn
1. Tổng Quan

GVHD: TS. Nguyễn Minh Tâm

Trang 16

1.3 Giới hạn đề tài:

Trong đề tài này, robot tự hành chỉ tìm được đường đi đến vị trí đích đã định sẵn,
sử dụng thuật toán tìm kiếm theo chiều sâu trong trí tuệ nhân tạo. Chức n ng vẽ lại
hình dạng của mê cung và giao tiếp máy tính nằm ngoài phạm vi của đề tài.
1.4 Nội dung nghiên cứu:
Dựa vào nguyên lý hoạt động của robot tự hành nhóm đã thiết kế mô hình bằng các
phương pháp cụ thể như sau:
– Khảo sát phân tích tổng hợp: phân tích cách thức hoạt động của robot tự hành
để thiết kế bộ phận dò tìm có độ chính xác cao nhất, bộ phận xử lí tín hiệu có
tốc độ cao nhất đồng thời có giá thành thấp và tuổi thọ cao…
– Khảo sát tính khả thi của từng thuật toán nhỏ trong trí tuệ nhân tạo.
– Thực nghiệm: dùng phương pháp thực nghiệm để kiểm tra tính khả thi của từng
thuật toán, đồng thời mô phỏng hoạt động của robot trên Matlab.
– Đánh giá kết quả dựa trên quá trình thực nghiệm.
1.5 Nội dung của đề tài:
Phần còn lại của nội dung đề tài bao gồm những chương sau:
Chương 2: Cơ sở lý thuyết.
Nội dung của chương này là trình bày lý thuyết về trí tuệ nhân tạo và các thuật
toán tìm kiếm trong trí tuệ nhân tạo.
Chương 3: Thiết kế và thi công mô hình robot tự hành.
Chương này chủ yếu trình bày sơ lược về cấu trúc hoạt động của vi điều khiển
ATmega8A, thiết kế về phần cơ khí và phần điện cho mô hình robot tự hành.
Chương 4: Thuật toán điều khiển mô hình robot tự hành.
Chương này trình bày lưu đồ thuật toán tìm kiếm của đề tài.
Chương 5: Kết quả thực nghiệm
Chương này trình bày về các kết quả đạt được của đề tài như thiết kế phần
cứng, tính ổn định của mô hình robot tự hành và mô phỏng hoạt động của Robot
bằng Matlab.
Chương 6: Kết luận và hướng phát triển của đề tài.

Chương này trình bày những kết quả đạt được trong luận v n, các mặt hạn chế
và hướng phát triển của đề tài.
www.dienvietnam.vn
2. Cơ sở lý thuyết

GVHD: TS. Nguyễn Minh Tâm

Trang 17

Chương 2:

Cơ sở lý thuyết
Chương này giới thiệu sơ lược về trí tuệ nhân tạo, các thuật toán tìm kiếm trong trí tuệ
nhân tạo.
2.1 Tổng quan về trí tuệ nhân tạo:
Trí tuệ nhân tạo là gì?
Trí tuệ nhân tạo là lĩnh vực khoa học chuyên nghiên cứu các phương pháp chế tạo
trí tuệ máy sao cho giống như trí tuệ con người.
Vài định nghĩa của trí tuệ nhân tạo điển hình là:
– Hệ thống mà biết suy nghĩ như con người.
– Hệ thống mà biết hành động như con người.
Để hệ thống mà biết suy nghĩ và hành động như con người thì hệ thống đó phải
được trang bị các công cụ thính giác, tri thức, lý giải tự động, việc học, thị giác và di
chuyển giống như con người.
Thông thường, cách giải quyết vấn đề của con người được thể hiện qua bốn thao
tác cơ bản đó là:
– Xác định tập hợp của các đích.
– Thu thập các sự kiện và luật suy diễn.
– Cơ chế tập trung.
– Bộ máy suy diễn.
Như vậy, trí tuệ máy là các khả n ng giải quyết vấn đề của máy có các đặc điểm
sau:
– Hành động giống như con người
– Suy nghĩ giống như con người.
– Học giống như con người.
– Xử lý thông tin giống như con người.
– Hành động và suy nghĩ trên cơ sở logic và chính xác.

Các thành phần cơ bản của trí tuệ nhân tạo:
www.dienvietnam.vn
2. Cơ sở lý thuyết

GVHD: TS. Nguyễn Minh Tâm

Trang 18

Có hai thành phần cơ bản của trí tuệ nhân tạo đó là biểu diễn tri thức và tìm kiếm
tri thức trong miền biễu diễn. Tri thức của bài toán có thể được phân ra làm ba loại tri
thức cơ bản đó là tri thức mô tả, tri thức thủ tục và tri thức điều khiển.
– Tri thức mô tả: là loại tri thức mô tả những gì mà được biết về bài toán. Loại tri
thức này bao gồm các sự kiện, các quan hệ và các tính chất của bài toán.
– Tri thức thủ tục: là loại tri thức mô tả các giải quyết bài toán. Loại tri thức này
bao gồm luật suy diễn hợp lệ, chiến lược tìm kiếm và giải thuật tìm kiếm.
– Tri thức điều khiển: là loại tri thức được xem như là luật chủ chốt điều khiển
quá trình lý giải để d n đến kết luận.
Để biểu diễn tri thức của bài toán nhờ các phương pháp biểu diễn như:
– phương pháp biểu diễn nhờ luật.
– phương pháp biểu diễn nhờ mạng ngữ nghĩa.
– phương pháp biểu diễn nhờ Frame.
– phương pháp biểu diễn nhờ logic vị từ.
Sau khi tri thức của bài toán đã được biểu diễn, kỹ thuật giải bài toán trong lĩnh
vực trí tuệ nhân tạo là các phương pháp tìm kiếm trong miền đặc trưng tri thức về bài
toán.
2.2 Không gian bài toán :
Tri thức của bài toán được chia ra làm ba lọai tri thức cơ bản đó là tri thức mô tả,
tri thức thủ tục và tri thức điều khiển, trong đó tri thức thủ tục định nghĩa không gian
bài toán. Không gian bài toán có thể được biểu diễn bằng không gian trạng thái đó là
một biểu diễn bằng đồ thị định hướng gồm bốn thành phần như sau:
+ S: Trạng thái ban đầu của bài toán (dữ liệu ban đầu).
+ G: Tập các trạng thái đích của bài toán (dữ liệu đích).
+ N: Tập các trạng thái khác được phát sinh từ trạng thái ban đầu đạt đến trạng
thái đích đó là các nút của đồ thị.
+ A: Tập các trạng thái chuyển tiếp đó là các cung liên kết giữa các nút của đồ thị
nhờ thông qua các luật áp dụng của bài toán.
Luật áp dụng là luật mà vế điều kiện của nó hợp với trạng thái hiện có để vế kết
luận của nó phát sinh ra các trạng thái mới.
Đường lời giải của bài toán là đường bắt đầu từ trạng thái ban đầu thông qua các
trạng thái khác được phát sinh đến một trạng thái nào đó trong tập các trạng thái đích.
www.dienvietnam.vn
2. Cơ sở lý thuyết

GVHD: TS. Nguyễn Minh Tâm

Trang 19

2.3 Chiến lược tìm kiếm :
Có hai chiến lược tìm kiếm trên không gian trạng thái bài toán đó là tìm kiếm bắt
đầu từ dữ liệu ban đầu về đích và tìm kiếm từ dữ liệu đích lùi về dữ liệu ban đầu.
Tìm kiếm bắt đầu từ dữ liệu ban đầu về đích được gọi là chiến lược tìm kiếm suy
diễn tiến và tìm kiếm bắt đầu từ đích lùi về dữ liệu được gọi là chiến lược tìm kiếm
suy diễn lùi.
2.3.1 Tìm kiếm suy diễn tiến:
Thủ tục tìm kiếm suy diễn tiến trên không gian trạng thái bài toán được mô tả
như sau:
+ Bắt đầu tìm kiếm từ dữ liệu ban của bài toán.
+ Chọn tất các các luật ứng dụng với vế điều kiện hợp với dữ liệu ban đầu của
bài toán để vế kết luận phát sinh ra các dữ liệu mới.
+ Tại mỗi điểm dữ liệu mới, chọn tất cả các luật ứng dụng với vế điều kiện hợp
với dữ liệu mới để vế kết luận phát sinh ra các dữ liệu mới hơn.
+ Thủ tục này được lặp lại cho tất cả các dữ liệu mới cho đến khi dữ liệu đích
được tìm thấy.
2.3.2 Chiến lược tìm kiếm suy diễn lùi:
Thủ tục tìm kiếm suy diễn lùi trên không gian trạng thái bài tóan được mô tả
như sau:
+ Thủ tục bắt đầu tìm kiếm từ dữ liệu đích của bài toán.
+ Chọn tất cả các luật ứng dụng với vế kết luận hợp với dữ liệu đích, thiết lập
dữ liệu ở vế điều kiện phát sinh ra đích làm dữ liệu đích mới.
+ Tại mỗi điểm dữ liệu đích mới, chọn tất cả các luật ứng dụng với vế kết luận
hợp với đích mới, thiết lập dữ liệu ở điều kiện làm dữ liệu đích mới hơn.
+ Thủ tục này lặp lại cho tất cả các đích mới cho đến khi nào dữ liệu ban đầu
của bài toán được tìm thấy.
2.4 Giải thuật tìm kiếm:
Để giải bài toán sử dụng chiến lược tìm kiếm suy diễn tiến hoặc chiến lược tìm
kiếm suy diễn lùi, công việc tìm kiếm là phải tìm một đường từtrạng thái bắt đầu đến
trạng thái đích thông qua không gian trạng thái của bài toán. Công cụ thực hiện việc
www.dienvietnam.vn
2. Cơ sở lý thuyết

GVHD: TS. Nguyễn Minh Tâm

Trang 20

tìm kiếm này đó là giải thuật. Quá trình tìm kiếm được xem như cây tìm kiếm thông
qua không gian trạng thái của bài toán. Giải thuật bắt đầu từ nút gốc của cây tìm kiếm
th m dò qua các nút khác của cây trong không gian trạng thái của bài toán. Nếu giải
thuật tìm thấy đích thì giải thuật thiết lập đường lời giải bắt đầu từ nút gốc thông qua
các nút liên kết đến nút đích của cây. Cấu trúc dữ liệu cho cây tìm kiếm ở đây là ta giả
sử nút là một cấu trúc dữ liệu với n m thành phần như sau:
+ Trạng thái trong không gian trạng thái tương ứng với nút của cây.
+ Nút trong cây tìm kiếm mà đã phát sinh ra nút mới thì nút này được gọi là nút
cha và nút mới được gọi là nút con.
+ Luật hay lệnh hợp lệ được áp dụng để phát sinh ra nút.
+ Số lượng của các nút trên đường từ nút gốc của cây đến một nút,được gọi là độ
sâu của nút đó.
+ Giá chi phí của đường là tính từ nút gốc của cây đến nút đó.
Có hai loại giải thuật tìm kiếm cơ bản đó là giải thuật tìm kiếm theo chiều
rộng và giải thuật tìm kiếm theo chiều sâu.
2.4.1 Giải thuật tìm kiếm theo chiều rộng (Breadth_First_Search):
Giải thuật tìm kiếm theo chiều rộng là giải thuật tìm kiếm mức theo mức của cây.
Giải thuật bắt đầu từ nút gốc của cây tìm kiếm qua tất cả các nút ở mức kế theo, nếu nó
chưa tìm thấy đích thì nó tiếp tục tìm kiếm qua tất cả các nút ở mức sâu hơn, cứ như
thế cho đến khi nó tìm thấy nút đích thì nó dừng thủ tục tìm kiếm và thiết lập đường
lời giải bắt đầu từ nút gốc thông qua các nút liên kết đến nút đích.
Giả sử cho không gian trạng thái của bài toán với các trạng thái được đánh nhãn
bằng các chữ cái A, B, C… được mô tả như hình 2.1.

www.dienvietnam.vn
2. Cơ sở lý thuyết

GVHD: TS. Nguyễn Minh Tâm

Trang 21

Hình 2.1: Không gian trạng thái của bài toán tìm kiếm theo chiều rộng.
Thứ tự của các trạng thái tìm kiếm với giải thuật tìm kiếm theo chiều rộng là:
A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U.
Giải thuật tìm kiếm theo chiều rộng được trang bị bằng hai danh sách mở Open
và đóng Closed, trong đó danh sách Open chứa các trạng th ái đang chờ được duyệt và
danh sách Closed chứa các trạng thái đã được duyệt qua. Giải thuật được mô tả như
sau:
Procedure breadth_first_search
Begin
Open = [Start];
Closed = [ ];
While Open ≠ [ ] Begin
+ Lọai bỏ nút đầu tiên từ danh sách Open và gọi nút này là X. If X =
đích Then trả về thành công
Else begin
+ Phát sinh các con của X dùng các luật áp dụng hợp với X;
+ Đặt X vào danh sách Closed;
+ Lọai bỏ các con của X đã có mặt trên Open hoặc Closed;
+ Đặt các on của X chưa có mặt trên Open hoặc Closed vào cuối
danh sách Open;
end
end;
end.

www.dienvietnam.vn
2. Cơ sở lý thuyết

GVHD: TS. Nguyễn Minh Tâm

Trang 22

2.4.2 Giải thuật tìm kiếm theo chiều sâu (Depth First Search):
Giải thuật tìm kiếm theo chiều sâu là giải thuật tìm kiếm nhánh theo nhánh của
cây. Giải thuật bắt đầu từ nút gốc tìm kiếm đến con, cháu, chắc của gốc, nếu giải thuật
tìm thấy đích thì dừng thủ tục tìm kiếm và thiết lập đường lời giải từ nút gốc thông qua
các nút liên kết đến nút đích; mặt khác nếu giải thuật tìm thấy đường cụt thì nó lùi về
tìm kiếm nút anh em. Không gian trạng thái của phương pháp tìm kiếm theo chiều sâu
được mô tả như hình 2.2:

Hình 2.2: Không gian trạng thái của phương pháp tìm kiếm theo chiều sâu.
Cho không trạng thái của bài toán như hình trên, thứ tự của các trạng thái tìm
kiếm với giải thuật tìm kiếm theo chiều sâu là A, B, E, K, S, L, T, F, M, C, G, N, H, O,
P, U, D, I, Q, J, R.
Giải thuật cũng được trang bị bằng hai danh sách mở Open và đóng Closed giống
như giải thuật tìm kiếm theo chiều rộng. Giải thuật được mô tả như sau:
Procedure depth_first_search
Begin
Open = [Start];
www.dienvietnam.vn
2. Cơ sở lý thuyết

GVHD: TS. Nguyễn Minh Tâm

Trang 23

Closed = [ ];
While Open ≠ [ ] Begin
+ Lọai bỏ nút đầu tiên từ danh sách Open và gọi nút này là X. If X =
đích Then trả về thành công
Else begin
+ Phát sinh các con của X dùng các luật áp dụng hợp với X;
+ Đặt X vào danh sách Closed;
+ Lọai bỏ các con của X đã có mặt trên Open hoặc Closed;
+ Đặt các on của X chưa có mặt trên Open hoặc Closed vào đầu danh
sách Open;
end
end;
end.
2.4.3 Giải thuật tìm kiếm truyền lùi ( Back Tracking search ):
Một giải thuật tìm kiếm khác được gọi là giải thuật tìm kiếm truyền lùi, cách tìm
kiếm đích của giải thuật này cũng giống như cách tìm kiếm đích của giải thuật tìm
kiếm theo chiều sâu. Giải thuật được trang bị bằng ba danh sách N, S và D, trong đó
danh sách N chứa các trạng thái đang chờ sẽ được duyệt qua, danh sách S chứa các
trạng thái đã được duyệt qua trên đường tìm kiếm và D là danh sách chứa các trạng
thái của các đường cụt. Khi giải thuật tìm thấy đích, danh sách S được thiết lập với các
trạng thái liên kết nhau từ nút gốc đến nút đích đó là đường lời giải của bài toán. Giải
thuật được mô tả như sau:
Function backtracking
Begin
N = [Start];
S = [Start];
D = [ ];
www.dienvietnam.vn
2. Cơ sở lý thuyết

GVHD: TS. Nguyễn Minh Tâm

Trang 24

C = Start;
While N ≠ [ ] Begin
If C = đích then return (S)
Elseif C không có thừa kế
( Không kể các thừa kế đã có mặt trên N, S hoặc D)
begin
while S ≠ [ ] và C là phần tử đầu tiên của S
begin
+ Đặt C vào đầu danh sách D.
+ Lọai bỏ nút đầu tiên của S.
+ Lọai bỏ nút đầu tiên của N.
+ Đặt C = phần tử đầu tiên của N.
end
Đặt C vào đầu danh sách S.
end
Else
begin
+ Khai triển các thừa kế của C dùng các luật ứng hợp với C.
+ Lọai bỏ tất cả các thừa kế của C đã có mặt trên N, S, hoặc D.
+ Đặt các thừa kế của C chưa có mặt trên N, S, hoặc D vào đầu danh
sách N.
+ Đặt C = phần tử đầu tiên của N.
+ Đặt C vào đầu danh sách S.
www.dienvietnam.vn
2. Cơ sở lý thuyết

GVHD: TS. Nguyễn Minh Tâm

Trang 25

end
end;
end.
2.5 Tìm Kiếm Heuristic:

Heuristic là gì?

Tri thức điều khiển của bài toán còn được gọi là heuristic. Heuristic là luật chủ
chốt điều khiển thuật toán tìm kiếm bám theo đường có các trạng thái tốt nhấtđể đạt
đến đích. Heuristic có thể được thể hiện dưới dạng luật hoặc dưới dạng hàm số. Nếu
nó được thể hiện dưới dạng luật thì nó được gọi là luật heuristic và nếu nó được thể
hiện dưới dạng hàm thì nó được gọi là hàm heuristic.
Heuristic còn được gọi là tri thức nông cạn của bài toán vì nó chỉ đoán bắt trạng
thái tốt nhất ở bước kế theo trong quá trình giải quyết vấn đề. Do đó heuristic đôi lúc
không thể đảm bảo tìm thấy lời giải tốt nhất nhưng hầu hết nó đảm bảo tìm thấy lời
giải tương đối tốt nhất.
Nếu ta định nghĩa h(n) là hàm heuristic tại trạng thái n thì h(n) là một ước lượng
tính từ trạngthái n đến trạng thái đích của bài toán. Trạng thái nào cóheuristic nhỏnhất
đólà trạng thái tốt nhất được chọn để tiếp diễn quá trình tìmkiếm.
+ Nếu trạng thái n không d n đến đường cụt thì heuristic của nó là h(n) >= .
+ Nếu trạng thái n d n đến đường cụt thì heuristic của nó là h(n) = ∞.
+ Nếu trạng thái n d n đến trạng thái đích của bài tóan thì heuristic của nó là h(n)
= 0.
2.5.1 Giải thuật tìm kiếm Best_First_Search:
Một trong các giải thuật tìm kiếm sử dụng heuristic đó là giải thuật
Best_first_search. Giải thuật được trang bị bằng hai danh sách mở Open và đóng
Closed cũng giống như giải thuật tìm kiếm theo chiều rộng và chiều sâu. Giải thuật bắt
đầu tìm kiếm với nút gốc của cây, khai triển các thừa kế của gốc nhờ thông qua các
luật ứng dụng, ước lượng heuristic cho tất cả các nút con của gốc, chọn nút có
heuristic nhỏ nhất để đến viếng th m và tháo bỏ tất cả các nút còn lại. Thủ tục
nàyđược lặp lại cho tất cả các nút viếng th m cho đến khi nào trạng thái đích của bài
toán được tìm thấy. Cách tìm kiếm này tạo ra một đường liên kết bám theo các trạng
thái có thông tin heuristic nhỏ nhất đó là các trạng thái được đánh giá là tốt nhất để đạt
đến đích.
Giải thuật được mô tả như sau:
Procedure best_first_search
www.dienvietnam.vn
2. Cơ sở lý thuyết

GVHD: TS. Nguyễn Minh Tâm

Trang 26

Begin
Open = [Start];
Closed = [ ];
While Open ≠ [ ] Begin
+ Lấy nút đầu tiên của danh sách Open , gọi nút này là X và lọai bỏ X khỏi
danh sách Open.
+ If X = đích Then return(success)
Else
Begin
+ Khai triển các thừa kế của X nhờ thông qua các luật ứng dụng.
Cho mỗi thừa kế của X thực hiện một trong các trường hợp như sau :
Case : Thừa kế chưa xuất hiện trên danh sách Open hoặc Closed.
+ Ước lượng heuristic cho thừa kế.
+ Đặt thừa kế vào danh sách Open.
Case : Thừa kế đã có mặt trên danh sách Open.
+ Ước lượng heuristic cho thừa kế.
+ Nếu trạng thái mới xuất hiện là tốt hơn trạng thái cũ đã xuất hiện trên
Open thì lọai bỏ cũ khỏi danh sách Open và đặt mới vào danh sách Open; mặt khác
giữ lại trạng thái cũ ở danh sách Open và lọai bỏ trạng thái mới xuất hiện.
Case : Thừa kế đã có mặt trên danh sách Closed.
+ Ước lượng heuristic cho thừa kế.
+ Nếu trạng thái mới xuất hiện là tốt hơn trạng thái cũ đã có mặt sẵn
trên Closed thì lọai bỏ cũ khỏi danh sách Closed và đặt mới vào danh sách Open; mặt
khác giữ lại trạng thái cũ ở danh sách Closed và lọai bỏ trạng thái mới xuất hiện.
End
+ Đặt X vào danh sách Closed.
www.dienvietnam.vn
2. Cơ sở lý thuyết

GVHD: TS. Nguyễn Minh Tâm

Trang 27

+ Sắp xếp lại các trạng thái trong danh sách Open theo thứ tự từ đầu danh sách
đến cuối danh sách tương ứng với trạng thái tốt nhất đến trạng thái xấu nhất.
End;
End.
2.5.2 Hàm đánh giá heuristic:

Giả sử quá trình tìm kiếm với thông tin heuristic trên không gian bài toán có hai
hoặc nhiều trạng thái xuất hiện có cùng heuristic, trong trường hợp này, trạng thái nào
là gần gốc nhất của cây đó là trạng thái tốt nhất. Để đánh giá đầy đủ thông tin heuris
cho các trường hợp như vậy, một hàm đánh giá heuristic được thiết lập gồm hai thành
phần đó là:
f(n) = h(n) + g(n)
trong đó, h(n) là hàm heuristic tại mỗi trạng thái n và g(n) là hàm chi phí đo từ trạng
thái gốc của cây đến nút trạng thái n.
Vì vậy, quá trình tìm kiếm, trạng thái nào có f(n) là nhỏ nhất đó là trạng thái tốt
nhất được chọn để tiếp diễn tìm kiếm.

www.dienvietnam.vn
3. Thiết kế phần cứng

GVHD: TS. Nguyễn Minh Tâm

Trang 28

Chương 3:
Thiết kế và thi công mô hình robot tự hành

Chương này trình bày về thiết kế phần cứng của Robot tự hành, giới thiệu sơ
lược về chip ATmega8A, giao tiếp với EEPROM và phương pháp thiết kế mạch điện
cho Robot.

Hình 3.1: Robot tự hành dò đường trong mê cung đã được thiết kế.
3.1 Tổng quan về phần cứng Robot tự hành.

Robot tự hành được thiết kế như hình gồm các phần chính như sau:
– Khung xe bằng mica.
– Động cơ DC có hộp số dùng để truyền động cho 2 bánh xe.
– Hệ thống cảm biến được chọn sử dụng trong mô hình này là dò lai bằng quang
trở.
www.dienvietnam.vn