Chơng 3
Một số phơng pháp chính xác lập lộ trình
chuyển động
3.1.Giới thiệu chung
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ỉ.
Nhờ có tính chất này nên cách tiếp cận này còn gọi là giải thuật lập lộ trình chính xác.
Khi nghiên cứu những giải thuật này điều quan trọng là việc xem xét cẩn thận
định nghĩa đầu vào :
- Mô hình nào đợc sử dụng để mô hình hoá robot và chớng ngại vật?
- Tập hợp những biến đổi nào đợc áp dụng cho Robot?
- Số chiều của không gian?
- Robot và không gian có thoả mãn tính chất lồi không?
- Chúng có là các phân đoạn tuyến tính?
Chỉ định rõ đợc các đầu vào có thể xác định tập các thể hiện của bài toán mà trên đó
các thuật toán sẽ tác nghiệp. Nếu những thể hiện có những tính chất thuận lợi nhất định
(số chiều của không gian thấp, những mô hình thể hiện là không gian lồi ) thì một
giải thuật tổ hợp có thể cung cấp một giải pháp rất tốt và thực tế. Nếu tập hợp của
những thể hiện quá rộng, thì một yêu cầu phải thoả mãn cả tính chất trọn vẹn
lẫn những giải pháp thực hành có thể là một điều vô lý. Việc xây dựng những
công thức chung của vấn đề lập lộ trình chuyển động có thể không đạt đợc. Tuy
vậy, vẫn tồn tại một số điểm chung để hoàn thành những giải thuật lập lộ trình
chuyển động.
Tại sao cần phải nghiên cứu phơng pháp chính xác lập lộ trình tổ hợp
Có hai lý do cần nghiên cứu những phơng pháp tổ hợp để tiếp cận tới việc lập lộ
trình chuyển động, đó là :
Thứ nhất, trong nhiều ứng dụng, việc lập lộ trình chuyển động có thể chỉ
49
quan tâm đến một lớp đặc biệt, ví dụ không gian chỉ là không gian hai chiều 2D,
và robot chỉ có khả năng tịnh tiến. Khi tập hợp nhiều lớp đặc biệt thì những giải
thuật thanh lịch và có hiệu lực có thể đợc phát triển. Những giải thuật này là đầy

là tập hợp của tất cả các điểm trong tầm với của G, ( S=
)]1,0([
Ê
e
e


trong đó
e([0,1])

C
free
là ảnh của đờng đi e). Đồ thị G đợc gọi một Roadmap nếu nó thỏa
mãn hai điều kiện quan trọng :
1. Tính dễ tiếp cận : Từ bất kỳ q

C
free
, nó phải tính toán đợc một đờng đi hiệu
50
quả và đơn giản

: [ 0, 1 ]

C
free
sao cho

(0) = q và


2
. Nh vậy, những giải pháp không lỗi
bởi vì G luôn giữ liên kết với C
free
. Điều này bảo đảm rằng những giải thuật hoàn
chỉnh thì phát triển.
Việc thỏa mãn những thuộc tính này, một đờng đi là một sự biểu diễn rời
rạc cho một lộ trình chuyển động liên tục mà không làm mất bất without losing
any of the original connectivity information needed cần thiết to solve it kỳ thông
tin kết nối nguyên bản nào để tìm ra lời giải. Một truy vấn, (qI, qG), đợc giải
quyết bởi việc nối cho mỗi truy vấn điểm để xây dựng nên Roadmap và sau đó
biểu diễn một tìm kiếm đồ thị rời rạc trên G. Duy trì tính chất đầy đủ, điều kiện
đầu tiên bảo đảm rằng bất kỳ truy vấn nào cũng có thể đợc nối tới G, và điều
kiện thứ hai bảo đảm rằng sự tìm kiếm luôn luôn thành công nếu tồn tại một giải
pháp.
3.2 vùng Chớng ngại Đa giác
Trớc khi nghiên cứu mẫu chung nhất của vấn đề lập lộ trình tổ hợp, chúng
ta nên tiếp cận những trờng hợp đơn giản và trực quan, đó là một số giải thuật
thanh lịch, minh bạch cho trờng hợp C = R
2
và C
obs
là đa giác. Hầu hết những
điều này không thể trực tiếp đợc mở rộng tới những không gian có số chiều cao
hơn nhng một số nguyên lý chung thì vẫn tơng tự; Bởi vậy, rất cần thiết để tiếp
cận việc lập lộ trình chuyển động chính xác trong không gian hai chiều. Những
giải thuật này cũng có thể trực tiếp áp dụng trong một số các ứng dụng. Việc lập
lộ trình cho một Robot di động có thể đợc mô hình hoá nh một điểm di động
trong một toà nhà mà bản đồ sàn nhà đã đợc mô hình bằng một số đa giác 2D.
51

lần hiệu Minkowski đợc tính toán, chúng cần hợp nhất để thu đợc một cách biểu
diễn dới dạng những đa giác đơn giản, nh những đa giác trong Hình 3.1.
52
To implement the algorithms described in this section, it will be helpful to have a data
structure that allows convenient tiện lọi access to the information contained bao gom in
a model such as Figure 3.1. How is the outer boundary represented?
Thực thi các giải thuật trong phần này sẽ giúp chúng ta có một cấu trúc dữ
liệu để cho phép truy cập thuận tiện vào các thông tin bao gồm các mẫu nh Hình
3.1. Để biểu diễn đợc chúng ta cần phải trả lời đợc những câu hỏi:
- Biểu diễn đờng biên ngoài nh thế nào?
- Những lỗ ở trong những chớng ngại đợc biểu diễn ra sao?
- Làm thế nào chúng ta biết những lỗ nào bên trong những chớng ngại vật?
Những truy vấn này có thể đợc trả lời hiệu quả bởi việc sử dụng cấu trúc dữ liệu
danh sách liên thông hai đầu. Chúng ta sẽ cần biểu diễn những mô hình, nh trong
Hình 3.1, và mọi thông tin khác của những giải thuật lập lộ trình để duy trì trong
thời gian thực hiện.
Có ba bản ghi khác nhau :
Đỉnh : Mỗi đỉnh v chứa đựng một con trỏ tới một điểm ( x, y)

C = R
2
và
một con trỏ tới nửa cạnh nào đó mà v gốc của nó.
Mặt : Mỗi mặt có một con trỏ tới một nửa cạnh trên biên giới bao
quanh mặt;.giá trị con trỏ là NIL nếu mặt là biên giới ở ngoài cùng. Mặt cũng
chứa đựng một danh sách những con trỏ cho mỗi thành phần có quan hệ (nh các
lỗ) mà chứa đựng ở trong mặt đó. Mỗi con trỏ trong danh sách trỏ cho một nửa
cạnh của ranh giới thành phần.
Nửa cạnh: Mỗi nửa cạnh đợc định hớng để phần chớng ngại luôn luôn ở
bên trái nó. Nó chứa đựng năm con trỏ khác nhau. Có một con trỏ tới đỉnh gốc

Randomized Potential Fields
Heuristics for Improving Roadmaps
Hybrid local/global
Visibility Graph
Voronoi Diagram (Maximum-Clearance Roadmaps)
Cell decomposition
ở đây chúng ta tập chung vào các giải thuật lập lộ trình chính xác nh Cell
decomposition, Visibility Graph ,Voronoi Diagram.
3.2.1. Vertical Cell Decomposition (sự phân ly Ô dọc )
Những phơng pháp tổ hợp phải xây dựng một cấu trúc dữ liệu hữu hạn để mã
54
hoá chính xác vấn đề lập lộ trình. Những giải thuật phân ly ô hớng tới việc chia cắt
C
free
thành một tập hợp hữu hạn những vùng gọi là những ô.
Sự phân ly ô cần phải thỏa mãn ba thuộc tính :
1.Việc tính toán một đờng đi từ một điểm bên trong một ô phải dễ dàng. Ví dụ, nếu
mỗi ô lồi, thì bất kỳ cặp điểm nào trong một ô đều có thể nối đợc bởi một đoạn thẳng.
2. Sự cung cấp thông tin cho những ô liền kề có thể dễ dàng đợc rút trích để xây
dựng roadmap.
3. Cho trớc một qI và qG, sự phân ly ô cần phải xác định đợc những ô nào chứa
chúng.
Nếu một sự phân ly ô thỏa mãn những thuộc tính này, thì vấn đề lập lộ trình
chuyển động đợc biến đổi thành vấn đề tìm kiếm đồ thị. Tuy nhiên, trong sự thiết đặt
hiện thời, toàn bộ đồ thị, G, thông thờng đợc biết trớc. Điều này không giả thiết riêng
cho những vấn đề lập lộ trình.
3.2.1.1. Định nghĩa sự phân ly dọc:
Phần này chúng ta giới thiệu một giải thuật mà xây dựng một sự phân ly ô dọc.
C
free

trong C
free
. Mỗi 1-cell là một đoạn dọc đáp ứng nh một cạnh giữa hai 2 - cell. Khi phân
ly chúng phải bảo đảm rằng topology của C
free
đợc biểu diễn chính xác.
Ta đã biết rằng C
free
đã đợc định nghĩa là một tập hợp mở. Mỗi 2- cell thật sự
cũng đợc định nghĩa là một tập hợp mở trong R
2
; nh vậy, nó là phần trong của một hình
thang hoặc hình tam giác và 1- cell là những điểm trên các đoạn thẳng.
3.2.1.2 Định nghĩa roadmap trong phơng pháp
Để điều khiển những truy vấn lập lộ trình chuyển động, một roadmap đợc xây
dựng từ sự phân ly dọc:
Cho mỗi ô C
i
, gọi q
i
là một đỉnh sao cho q
i

C
i
khi đó q
i
đợc gọi là điểm mẫu.
Những điểm mẫu có thể đợc lựa chọn theo nhiều cách, ví dụ nh những trọng tâm trong
các ô, nhng sự lựa chọn đặc biệt không phải là quá quan trọng, có thể tồn tại nhiều

. Nếu không có đờng đi nh vậy nào tồn tại, thì giải thuật tuyên bố
không tồn tại giải pháp. Nếu tồn tại một đờng đi thì cho C
1
, C
2
, . . ., C
k-1
lần lợt đi qua
tất cả những điểm mẫu của các 1 - cell và 2- cell từ C
0
đến C
k
.
Một đờng đi giải pháp có thể đợc hình thành một cách đơn giản bằng cách Nối
những điểm, q
0
, q
1
, q
2
, . . ., q
k-1
, q
k
biểu thị những điểm mẫu dọc theo đờng đi bên
trong G. Đờng đi giải pháp,

: [ 0, 1 ]

C

thuật chung khác. Nhiều vấn đề hình học tính toán bởi máy tính có thể đợc xem xét nh
sự phát triển của những cấu trúc dữ liệu và giải thuật mà khái quát hóa phân loại cho
vấn đề nhiều chiều. Nói cách khác, những giải thuật cẩn thận sắp xếp các thông tin
hình học.
Từ Quét đợc sử dụng khi trình bày những giải thuật này vì có thể hình dung
đó là một đờng (hoặc mặt phẳng) quét ngang qua không gian, chỉ dừng khi đạt đến
trạng thái thay đổi nào đó khi tìm thấy thông tin.
Trên đây mới là sự miêu tả trực quan, còn việc quét cha đợc biểu diễn rõ ràng
bằng giải thuật. Để xây dựng sự phân ly dọc, hình dạng một đờng dọc là đờng quét từ
x = -

tới x =

, giả sử (x, y) là một điểm trong C = R
2
. Dữ liệu đầu vào là tập hợp P
của đỉnh C
obs
. Bởi vậy chúng ta chỉ quan tâm đến những vấn đề xuất hiện ở những điểm
58
này. Sắp xếp những điểm trong P theo thứ tự toạ độ x tăng dần. Giả thiết thông thờng
không có hai điểm nào có cùng tọa độ x. Những điểm trong P sẽ đợc thăm theo thứ tự
đã sắp xếp. Mỗi lần thăm một điểm sẽ đợc coi là một sự kiện. Trớc, sau, và giữa mỗi sự
kiện, một danh sách L chứa một vài cạnh C
obs
sẽ đợc xác nhận. Danh sách này phải đợc
duy trì trong suốt thời gian theo thứ tự những cạnh đến khi nào va phải đờng quét dọc.
Danh sách đợc sắp xếp theo thứ tự tăng dần.
Hình 3.6 : Ví dụ có 14 sự kiện.
Hình 3.7 : Tình trạng của L đợc chỉ ra sau mỗi 14 sự kiện xuất hiện. Trớc hết là L

The roadmap G can be computed from the face pointers of the
doubly connected edge list
Roadmap G có thể đợc tính toán từ những con trỏ thể hiện của hai cạnh có quan
hệ trên danh sách.
Một cách tiếp cận tốt hơn là xây dựng gia tăng G ở mỗi sự kiện. Trên thực tế,
tất cả yêu cầu duy trì một con trỏ đang tồn tại một cách chắc chắn hai cạnh liên quan
trong danh sách có thể đợc lờ đi nếu mong muốn, kéo dài G đợc xây dựng chính xác
và điểm mẫu thu đợc cho mỗi ô dọc. Chúng ta có thể đi là một bớc xa hơn nữa, bởi
quên đi khoảng sự phân ly ô và trực tiếp xây dựng một đồ thị tôpô của những đoạn đ-
ờng đi giữa tất cả điểm mẫu của những ô liền kề.
3.2.2 . Roadmap Đờng đi ngắn nhất -Shortest-Path Roadmaps
60
Thay vào đó của việc phát sinh những đờng đi làm cực đại khoảng trống,
cần có mục đích tìm thấy những đờng đi ngắn nhất. Điều này dẫn tới phơng pháp
Roadmap đờng đi ngắn nhất (Shortest-Path Roadmaps), và cũng đợc gọi đồ thị tầm
nhìn thu nhỏ (Visibility Graph ). ý tởng của nó trớc hết đợc coi là ví dụ đầu tiên của
một giải thuật lập lộ trình chuyển động.
Roadmap đờng đi ngắn nhất đối lập trực tiếp với Roadmap khoảng trống cực
đại bởi vì những đờng đi ngắn nhất cho phép lớt qua những góc của C
obs
. Trong thực
tế, đây là một vấn đề đa ra tơng đối khó bởi vì C
free
là một tập hợp mở. Bởi vì với bất
kỳ đờng đi nào

: [0,1]

C
free

obs
, thì một cạnh giữa chúng đợc xây dựng bên trong G.
- Tiếp tuyến cạnh : Nếu một đờng tiếp tuyến có thể đợc vẽ xuyên qua một cặp
của đỉnh phản xạ, thì một cạnh tơng ứng đợc xây dựng bên trong G.
Một đờng tiếp tuyến, đợc miêu tả trong Hình 3.10, là một đờng liên quan tới hai đỉnh
phản xạ và không đi vào trong C
obs
tại bất kỳ đỉnh này nào. Hơn nữa, các đỉnh này phải
nhìn thấy lẫn nhau.
Một ví dụ của Roadmap kết quả đợc cho thấy trong Hình 3.11.
Hình 3.11 : Roadmap -đờng đi ngắn nhất bao gồm các cạnh giữa đỉnh phản xạ liên
tiếp trên C
obs
và cả những cạnh tiếp tuyến.
Hình 3.12 : Để giải quyết một truy vấn, qI và qG đợc nối tới tất cả đỉnh có thể thấy
62
của roadmap, và thực hiện tìm kiếm trên đồ thị.
Giải quyết một truy vấn, qI và qG đợc nối tới tất cả đỉnh có thể nhìn thấy đợc của
Roadmap ( Hình 3.12), chính điều này làm cho roadmap mở rộng có thể tìm kiếm đợc
một đờng đi giải pháp. Nếu giải thuật của Dijkstra đợc sử dụng, và mỗi cạnh đợc đa
vào một giá trị tơng ứng thì giá của đờng đi chính là độ dài của đờng đi đó, đờng đi
giải pháp kết quả là đờng đi ngắn nhất giữa qI và qG. Đờng đi ngắn nhất cho ví dụ
trong Hình 3.12 đợc cho thấy trong Hình 3.13.
Hình 3.13 : Đờng đi ngắn nhất trong Roadmap mở rộng là đờng đi ngắn nhất giữa qI
và qG.
Đánh giá giải thuật: Nếu tiếp tuyến kiểm tra đợc thực hiện đơn giản, thì kết
quả giải thuật yêu cầu thời gian O(n
3
), trong đó n là số đỉnh của C
obs

dụng của kỹ thuật rôbôt di động bởi vì thật khó để đo và điều khiển chính xác vị trí của
một rôbôt di động. Việc đi dọc theo roadmap khoảng trống cực đại làm giảm bớt
những nguy cơ va chạm vì những điều không chắc chắn này. Phơng pháp Roadmap này
còn những tên khác là Voronoi diagram và Retraction method (phơng pháp thu gọn).
Hình : Các đoạn thẳng làm nên Voronoi Diagram cách ly một tập hợp điểm.
64
Hình: Generalized Voronoi Graph (GVG)- Đồ thị Voronoi tổng quát
Đồ thị Voronoi tổng quát là quỹ tích của những điểm có khoảng cách bằng nhau từ
hai hay nhiều đờng biên của chờng ngại vật bao gồm cả đờng biên của vùng làm việc.

Hình : Đồ thị Voronoi tổng quát ( GVG ) là hình dạng đờng đi xây dựng bởi khoảng
cách bằng nhau từ hai đối tợng đóng là khoảng hở lớn nhất giữa hai chớng ngại vật
65
Nó là đợc xem xét nh một sự khái quát của sơ đồ Voronoi từ trờng hợp những điểm
của đa giác. Mỗi điểm từ một cạnh roadmap cách đều hai điểm trên ranh giới của C
obs
.
Mỗi đỉnh Roadmap tơng ứng với điểm giao nhau của hai hoặc nhiều hơn hai cạnh của
Roadmap và cách đều hai điểm trên ranh giới của C
obs
.
Không gian con: S là một sự biến dạng thu gọn của một không gian tôpô X nếu liên
tục sau homotopy, H : X
ì
[0, 1 ]

X, có thể đợc định nghĩa nh sau:
1. h(x, 0) = x với mọi x

X.

66
phần của những đờng đimà thực sự nằm trên maximum-clearance roadmap đợc xác
định bởi những phần giao nhau của những đờng cong.
Hình : Đồ thị Voronoi đợc xây dựng và làm mịn với những đờng cong
Vài giải thuật tồn tại mà cung cấp tiệm cận tốt hơn thời gian thực thi, nhng chúng khó
thực hiện hơn một cách đáng kể. Giải thuật tốt nhất đợc chạy trong thời gian là
O(nlgn) trong đó n là số của đờng cong Roadmap.
67