Thạc Sĩ Một số phương pháp chính xác lập lộ trình chuyển động cho Robot

Lời nói đầ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 .






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