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
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.
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
3. Thiết kế phần cứng
GVHD: TS. Nguyễn Minh Tâm Trang 29
Thông số của Robot tự hành được thiết kế và trình bày như bảng sau:
Bảng 3.1: Thông số kỹ thuật của robot tự hành.
Mô tả Thông số
Động cơ DC 12V 3000Rpm
Bánh xe Đường kính 6cm
Khối lượng Robot 0.7 Kg
Chiều dài Robot 19 cm
Chiều rộng Robot 16 cm
Chiều cao Robot 8 cm
Sơ đồ khối của hệ thống như hình 3.2:
- Khối điều khiển gồm chip ATmega8A có nhiệm vụ nhận tín hiệu từ các cảm
biến, xử lý thuật toán điều khiển và xuất tín hiệu điều khiển.
- Khối điều khiển động cơ gồm IC L298N và các IC logic có nhiệm vụ nhận tín
hiệu từ khối điều khiển để điều khiển hai động cơ.
- Khối nguồn sử dụng Pin Li-Poly loại . V 2 C 2 mAh.
www.dienvietnam.vn
3. Thiết kế phần cứng
GVHD: TS. Nguyễn Minh Tâm Trang 30
Hình 3.2: Sơ đồ khối của robot tự hành.
3.2 Lựa chọn thiết bị:
3.2.1 Lựa chọn động cơ:
Có 3 loại động cơ thích hợp cho đề tài này đó là động cơ bước, động cơ DC và
động cơ Servo. Các yếu tố quan trọng cần thiết để lựa chọn động cơ đó là động cơ có
kích thước nhỏ để phù hợp với Robot, tốc độ và moment đủ lớn để truyền động cho
bánh xe.
- Động cơ bước có moment lớn nhưng có tốc độ thấp và kích thước lớn.
- Động cơ Servo có tốc độ lớn nhưng hạn chế về moment và chỉ quay trong
phạm vi
www.dienvietnam.vn
3. Thiết kế phần cứng
GVHD: TS. Nguyễn Minh Tâm Trang 31
- Động cơ DC thì phong phú về chủng loại, có kích thước nhỏ, tốc độ và
moment phù hợp với yêu cầu của đề tài.
Như vậy, chọn động cơ DC là phù hợp. Nhóm đã chọn được đông cơ DC có
thông số như sau: 2VDC, 3 Rpm.
3.2.2 Lựa chọn cảm biến:
Để phát hiện được vật cản (bức tường mê cung) thì có thể sử dụng các loại cảm
biến: cảm biến hồng ngoại, cảm biến siêu âm, cảm biến quang trở...
Do ảnh hưởng của một số yếu tố khách quan nên nhóm đã chọn sử dụng cảm
biến quang trở cho đề tài này.
3.3 Thiết kế mạch điện cho Robot:
Việc thiết kế mạch điện đóng một vai trò rất quan trọng đến hoạt động của
Robot. Thiết kế mạch điện phải xem xét đến nhiều yếu tố liên quan cũng như khả n ng
của Robot. Nhóm đã chọn Chip vi điều khiển dòng AVR, cụ thể là chip ATmega8A
Hình 3.3: Vi điều khiển ATmega8A
Vi điều khiển Atmega8 AVR có công suất cao, tiêu thụ n ng lượng thấp, cấu
trúc RISC tiến với 3 lệnh với chu kỳ thực hiện đơn xung lớn nhất, 32 thanh ghi đa
mục đích 8 bít, 6 MIPS tại tần số đặt 6 MHz, bộ nhân 2 chu kỳ On-chip, Power-on
Reset và Brown-out Detection có thể lập trình, bộ dao động RC bên trong có thể lập
trình các mức, 5 Mode ngủ (Idle, ADC Noise Reduction, Power-save, Power-down và
Standby), có khả n ng Reset khi bật nguồn, khả n ng dò lỗi Brown out lập trình được,
có nguồn ngắt trong và ngắt ngoài.
Cốt lõi của AVR là sự kết hợp các câu lệnh phong phú với 32 thanh ghi đa mục
đích. Tất cả 32 thanh ghi đều trực tiếp kết nối tới bộ xử lý logíc số học - Arithmetic
Logic Unit (ALU), cho phép truy nhập 2 thanh ghi độc lập trong một câu lệnh đơn
www.dienvietnam.vn
3. Thiết kế phần cứng
GVHD: TS. Nguyễn Minh Tâm Trang 32
được thực hiện trong một chu kỳ xung. Kết quả của cấu trúc trở nên gọn nhẹ, hiệu quả
hơn, trong khi v n đạt được thời gian xử lý nhanh hơn gấp lần các vi điều khiển
CISC thông thường khác.
8K byte Flash trên chíp có thể lập trình với các khả n ng đọc trong khi ghi
(Read-While-Write), 5 2 byte EEPROM, K byte SRAM, 23 đường vào ra đa mục
đích, 32 thanh ghi đa mục đích, 3 Timer/Counter rất linh hoạt với các compare mode,
các ngắt trong và ngắt ngoài, một bộ USART nối tiếp có thể lập trình được, ghép nối
nối tiếp 2 dây định hướng byte, 6 kênh ADC (8 kênh với loại TQFP và MLF packages)
trong đó 4 (hoặc 6) kênh có độ chính xác -bit và 2 kênh có độ chính xác 8-bit,
Watchdog Timer có thể lập trình được với bộ dao động bên trong, một cổng nối tiếp
SPI và 5 mode tiết kiệm n ng lượng có thể lựa chọn mềm.
- Idle mode dừng CPU trong khi v n cho phép SRAM, Timer/Counters, cổng
SPI, và hệ thống ngắt tiếp tục chức n ng của chúng.
- Power-down mode tiết kiệm nội dung thanh ghi, nhưng hạn định bộ dao động,
không cho phép tất cả các chức n ng khác của chíp được hoạt động cho đến khi ngắt
tiếp theo hoặc Reset phần cứng xuất hiện.
- Trong Power-save mode, timer không đồng bộ tiếp tục chạy, cho phép sử dụng
để duy trì thời gian nền, trong khi các phần còn lại của thiết bị được ngủ.
- ADC Noise Reduction mode dừng CPU và tất các module I/O ngoại trừ timer
không đồng bộ và ADC để tối thiểu hóa nhiễu mạch trong suốt quá trình ADC trong
chuyển đổi.
- Trong Standby mode, bộ dao động thạch anh/ resonator được phép chạy trong
khi các phần còn lại của thiết bị được ngủ. Điều này cho phép start-up rất nhanh cùng
với hiệu quả tiêu thụ ít n ng lượng.
Thiết bị được sản suất áp dụng công nghệ tích hợp bộ nhớ non-volatile cao của
Atmel. Bộ nhớ chương trình Flash này có thể lập trình thông qua ghép nối tiếp SPI
bằng chương trình lập trình bộ nhớ non-volatile riêng, hoặc bằng một chương trình
boot on – chip, chạy trong AVR core. Chương trình boot có thể sử dụng bất kỳ một
ghép nối nào để download chương trình ứng dụng trong bộ nhớ Flash. Phần mềm
trong Boot Flash sẽ tiếp tục chạy trong khi các phần sử dụng Flash v n được update,
hỗ trợ cho hoạt động đọc trong khi ghi (Read-While-Write).
Bằng việc kết hợp với một CPU 8-bit RISC với bộ nhớ Flash tự lập trình trong
hệ thống trên một chíp, Atmel ATmega8 là một vi điều khiển cực mạnh, thỏa mãn yêu
cầu về một bộ vi điều khiển với độ linh hoạt cao và đem lại lợi nhuận lớn với rất nhiều
các ứng dụng điều khiển tác động nhanh.
www.dienvietnam.vn
3. Thiết kế phần cứng
GVHD: TS. Nguyễn Minh Tâm Trang 33
ATmega8 AVR cũng hỗ trợ đầy đủ về lập trình và phát triển các tool hệ thống,
bao gồm bộ dịch C, macro assemblers, bộ mô phỏng/gỡ rối chương trình, In-Circuit
Emulators, và evaluation kits.
Những Tính Năng Chính Của ATmega8:
- Có 8Kbyte bộ nhớ flash
- Có thể xóa lập trình được và có thể chịu được lần ghi xóa.
- Có 32 thanh ghi đa n ng 8 bit.
- Có 512 byte bộ nhớ EEPROM tích hợp trên chíp.
- Có kbyte SRAM nội.
- Có hai bộ Timer/counter 8 bit và một bộ timer/counter 6 bit với bộ chia tần
lập trình được.
- Có ba kênh điều xung, 6 kênh lối vào chuyển đổi ADC với độ phân giải bit.
- Atmega8 có 28 chân, trong đó có 23 cổng vào ra.
- Nguồn nuôi từ 2. đến 5.5 đối với Atmega8L và từ 4.5 đến 5.5 đối với
Atmega8.
- Làm việc tiêu thụ dòng 3.6mA.
- Sử dụng mạch dao động ngoài từ đến 8 Mhz với Atmega8L và từ đến 6
Mhz với Atmega8.
- Ngoài ra chíp Atmega8 còn có bộ xung nội bên trong có thể lập trình chế độ
xung nhịp.
Vi điều khiển AVR do hãng Atmel (Hoa Kì) sản xuất được gới thiệu lần đầu n m
996. AVR có rất nhiều dòng khác nhau bao gồm dòng Tiny AVR (như AT tiny 3,
ATtiny 22…) có kích thước bộ nhớ nhỏ, ít bộ phận ngoại vi, rồi đến dòng AVR (chẳng
hạnAT9 S8535, AT9 S85 5,…) có kích thước bộ nhớ vào loại trung bình và mạnh
hơn là dòng Mega (như ATmega32, ATmega 28,…) với bộ nhớ có kích thước vài
Kbyte đến vài tr m Kbyte cùng với các bộ ngoại vi đa dạng được tích hợp trên chip,
cũng có dòng tích hợp cả bộ LCD trên chip (dòng LCD AVR ). Tốc độ của dòng Mega
cũng cao hơn so với các dòng khác. Sự khác nhau cơ bản giữa các dòng chính là cấu
trúc ngoại vi, còn nhân thì v n như nhau.
Cấu trúc của ATmega8A như hình 3.4:
www.dienvietnam.vn
3. Thiết kế phần cứng
GVHD: TS. Nguyễn Minh Tâm Trang 34
Hình 3.4: Sơ đồ cấu trúc ATmega8A.
3.3.1 Giao diện TWI (I2C):
TWI (Two-Wire Serial Intereafce) là một module truyền thông nối tiếp đồng bộ
trên các chip AVR dựa trên chuẩn truyền thông I2C. I2C là viết tắt của từ Inter-
Integrated Circuit là một chuẩn truyền thông do hãng điện tử Philips Semiconductor
sáng lập và xây dựng thành chuẩn n m 99 . Phiên bản mới nhất của I2C là V3.0 phát
hành n m 2 .
TWI (I2C) là một truyền thông nối tiếp đa chip chủ (tạm dịch của cụm từ multimaster
serial computer bus). Khái niệm “multi-master” được hiểu là trong trên cùng
một bus có thể có nhiều hơn một thiết bị làm Master, đồng thời một Slave có thể trở
thành một Master nếu nó có khả n ng. Ví dụ trong một mạng TWI của nhiều AVR kết
www.dienvietnam.vn
3. Thiết kế phần cứng
GVHD: TS. Nguyễn Minh Tâm Trang 35
nối với nhau, bất kỳ một AVR nào đều có thể trở thành Master ở một thời điểm nào
đó. Tuy nhiên nếu một mạng dùng một AVR điều khiển các chip nhớ (như EEPROM
AT24C 24 chẳng hạn) thì khái niệm “multi-master” không tồn tại vì các chip nhớ
được thiết kế sẵn là Slave, không có khả n ng trở thành master. TWI (I2C) được thực
hiện trên 2 đường SDA (Serial DATA) và SCL (Serial Clock) trong đó SDA là đường
truyền/nhận dữ liệu và SCL là đường xung nhịp. C n cứ theo chuẩn I2C, các đường
SDA và SCL trên các thiết bị có cấu hình “cực góp mở” (open-drain hoặc opencollector,
tham khảo các mạch số dùng transistor để hiểu thêm), nghĩa là cần có các
“điện trở kéo lên” (pull-up resistor) cho các đường này. Ở trạng thái nghỉ (Idle), 2 chân
SDA và SCL ở mức cao. Hình 3.5 mô tả một mô hình mạng TWI (I2C) cơ bản.
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.
Master: là chip khởi động quá trình truyền nhận, phát đi địa chỉ của thiết bị cần
giao tiếp và tạo xung giữ nhịp trên đường SCL.
Slave: là chip có một địa chỉ cố định, được gọi bởi Master và phục vụ yêu cầu từ
Master.
SDA - Serial Data: là đường dữ liệu nối tiếp, tất cả các thông tin về địa chỉ hay
dữ liệu đều được truyền trên đường này theo thứ tự từng bit một. Chú ý là trong chuẩn
I2C, bit có trọng số lớn nhất (MSB) được truyền trước nhất, đặc điểm này ngược lại
với chuẩn UART.
SCL –Serial Clock: là đường giữ nhịp nối tiếp. TWI (I2C) là chuần truyền thông
nối tiếp đồng bộ, cần có đường tạo xung giữ nhịp cho quá trình truyền/nhận, cứ mỗi
xung trên đường giữ nhịp SCL, một bit dữ liệu trên đường SDA sẽ được lấy m u
(sample). Dữ liệu nối tiếp trên đường SDA được lấy m u khi đường SCL ở mức cao
trong một chu kỳ giữ nhịp, vì thế đường SDA không được đổi trạng thái khi SCL ở
mức cao (trừ START và STOP condition). Chân SDA có thể được đổi trạng thái khi
SCL ở mức thấp.
www.dienvietnam.vn
3. Thiết kế phần cứng
GVHD: TS. Nguyễn Minh Tâm Trang 36
Hình 3.6: Quá trình lấy mẫu dữ liệu nối tiếp.
START Condition-Điều kiện bắt đầu: từ trạng thái nghỉ, khi cả SDA v
...........
Chương 6:
Kết luận và hướng phát triển đề tài
6.1 Kết Luận:
Đề tài đã thiết kế thành công phần điện, phần cơ khí, chương trình phần mềm cho
robot tự hành. Xét về những mục tiêu và giới hạn của đề tài đã được đặt ra ngay từ đầu
thì những điều mà đề tài đã thực hiện được và chưa thực hiện được như sau:
- Thiết kế phần cơ khí cho robot tự hành dò đường trong mê cung với những chi
tiết có kích thước nhỏ và phức tạp, đạt được tính kỹ thuật và thẩm mỹ cao.
- Thiết kế thành công phần điện cho robot. Mạch điện gồm có: điều khiển động cơ
bằng PWM, mạch cầu H sử dụng IC L298, đọc tín hiệu từ khối cảm biến sử dụng
ADC, giao tiếp RS232.
- Thiết kế thành công phần mềm cho robot áp dụng thuật toán tìm kiếm theo chiều
sâu trong trí tuệ nhân tạo, tuy nhiên v n chưa thích ứng được hoàn toàn với các
hình dạng mê cung khác nhau. Ví dụ: khi ta rút ngắn khoảng cách các đường
trong mê cung thì robot sẽ hoạt động không còn ổn định.
- Chưa thể vẽ lại đường của mê cung dùng công nghệ xử lý ảnh.
6.2 Hướng phát triển:
Sau khi thực hiện xong đề tài, do sự thiếu sót và giới hạn của nhóm sinh viên thực
hiện đề tài cũng như sự hạn chế về mặt kỹ thuật của thiết bị, để đề tài hoạt động tốt, mang
tính thích nghi cao trong môi trường thực tế thì cần phải phát triển một số vấn đề sau:
- Về phần cứng (phần điện và cảm biến) dùng cảm biến siêu âm hoặc cảm biến thu
phát hồng ngoại để dò các chương ngại vật thay cho việc dùng cảm biến quang
trở bám theo line.
- Kết hợp công nghệ xử lí ảnh vẽ lại hình dạng đường đi của robot tự hành để ứng
dụng trong việc tìm đường đến các vị trí nguy hiểm trong thực tế.
- Tùy thuộc vào các ứng dụng và đường đi mà áp dụng các thuật toán khác nhau để
đem lại hiệu quả cao nhất.