MỤC LỤC

MỤC LỤC . 2

DANH MỤC CÁ C HÌNH VẼ, ĐỒ THỊ 4

MỞ ĐẦU... 5

CHưƠNG I: GIƠI THIỆU BÀI TOÁN LẬP TRÌNH CHO ROBOT . 7

1.1. Robot nhân tạo . 7

1.2. Bài toán lập lộ trình 9

1.3.Ví dụ và những ứng dụng về lộ trình Robot .. 12

1.4. Những thành phần cơ bản của việc lập lộ trình . 16

1.5. Giải thuật, ng ười lập lộ trình và lộ trình .. 17

1.6. Kết luận . 23

Chương II- CẤU HÌNH KHÔNG GIAN TRẠNG THÁI . 24

2.1.Các Khái niệm cấu hình không gian ... 24

2.1.1. Chướng ngại (Obstacle) ... 24

2.1.2. Không gian trống ( Free Space- Cfree ). .. 25

2.2. Mô hình cấu hình . 26

2.2.1. Mô hình hình học .... 26

2.2.2. Mô hình nửa Đại số . 32

2.3. Các phép biến đổi của robot 35

2.4. Không gian cấu hình ch ướng ngại vật 37

2.5- Định nghĩa chính xác về vấn đề lập lộ trình chuyển động .... 38

2.6. Một số mô hình C obs .. 39

2.7. Kết luận . 47

Chương III- MỘT SỐ PHƯƠNG PHÁP CHÍNH XÁC LẬP LỘ TRÌNH CHUYỂN

ĐỘNG 48

3.1.Giới thiệu chung .. 48

3.2. Biểu diễn không gian chướ ng ngại vật .. 50

3.3. Một số giải thuật lập lộ trình chính xác cho robo t . 53

3.3.1 . Roadmap Visibility Graph – Đồ thị tầm nhìn .... 53

3.3.2. Vertical Cell Deco mposition ( phân ly Ô dọc ) .. 59

KẾT LUẬN .. 68

TÀI LIỆU THAM KHẢO..... 69

PHỤ LỤC 1 - Chương trình thử nghiệm Visibility Graph .. 70

PHỤ LỤC 2- Chương trình thử nghiệm Vertical Cell Decomposition ...73

MỞ ĐẦU

Tìm đường là một khoa học (hay nghệ thuật) hướng dẫn lộ trình cho robot di chuyển qua môi trường với mong muốn đến được đích mà không bị lạc hay va vào những đối tượng khác.

Thông thường, một lộ trình được lập trước để dẫn dắt robot đến đích của nó. Với phương pháp này, môi trường robot đi qua phải được biết hoàn toàn và không thay đổi, robot có thể đi theo một cách hoàn hảo. Hạn chế của việc vạch lộ trình trước đòi hỏi việc nghiên cứu tìm hiểu việc vạch lộ trình nội tại, phụ thuộc vào các tri thức thu được từ môi trường hiện tại đề xử lý các chướng ngại chưa biết khi robot băng qua môi trường.

Trên thế giới hiện nay robot là một lĩnh vực được hết sức quan tâm. Bài toán lập lộ trình cho robot là bài toán c ơ bản để thiết kế chế tạo Robot, do vậy việc tìm hiểu bài toán và nghiên cứu các phương pháp vạch lộ trình là hết sức quan trọng cần thiết cho sự phát triển lĩnh vực thiết kế và chế tạo Robot. Đã có một số nghiên cứu

để giải quyết bài toán như ứng dụng giả i thuật di truyền lập chương trình tiến hoá, xây dựng một số các thuật toán cho bài toán, nhưng đây vẫn là một vấn đề mở đang rất được quan tâm. Đặc biệt trong nước, đây là một lĩnh vực còn tương đối mới mẻ, hầu như chưa có các tài liệu đề một cách đầy đủ về lĩnh vực này.

Nhận thức được vấn đề đó và với sự gợi ý định hướng của PGS .TS

Đặng Quang Á em đã chọn nghiên cứu đề tài “Một số phương phỏp chớ nh xỏc l ập l ộ trỡ nh chuyển động cho Robot” . Nội dung cơ bản của luận văn tốt nghiệp gồm có ba chương:

Chương 1- Trình bày tổng quan bài toán lập lộ trình cho Robot đó là các khái niệm cơ bản về Robot, và bài toán về Robot, thuật toán và một số ví dụ ứng dụng bài toán lập lộ trình cho Robot.

Chương 2- Trình bày các khái niệm về cấu hình không gian trạng thái, cách biểu diễn không gian trong bài toán lập lộ trình cho robot. Đây làcác khái niệm cơ sở để biểu diễn được bài toán cho các giải thuật lập lộ trình chuyển động cho robot.

Chương 3- Đi sâu nghiên cứu một số phương pháp chính xác lập lộ trình chuyển động cho Robot. Cụ thể đó là hai phương pháp ROADMAP VISIBILITY GR APH và CELL DECOMPSITION. Đây là những cách tiếp cận tổ hợp tới việc lập lộ trình chuyển động để tìm thấy những đường đi xuyên qua không gian cấu hình liên tục mà không dùng đến những thuật toán xấp xỉ.

Qua luận văn này em xin chân thành cảm ơn: PGS .TS Đặng Quang Á - Viện Công nghệ thông tin đã tận tình giúp đỡ, động viên, định hướng, hướng dẫn em nghiên cứu và hoàn thành luận văn này. Em xin cảm ơn các thầy cô giáo trong viện Công nghệ thông tin, các thầy cô giáo khoa Công nghệ thông tin ĐH Thái nguyên, đã giảng dạy và giúp đỡ em trong hai năm học qua, cảm ơn sự giúp đỡ nhiệt tình của các bạn đồng nghiệp .

THÁI NGUYÊN 11/2008

Người viết luận văn

Nguyễn Thị Thu Thuỷ