2.2.4. Bài toán l p l trình chuy n đ ng cho robot.ậ ộ ể ộ
Bài toán l p l trình có th đ c phát bi u nh sau:ậ ộ ể ượ ể ư
Cho đ i t ng v i v trí ban đ u và v trí đích v i m t t p cácố ượ ớ ị ầ ị ớ ộ ậ
ch ng ng i v t có các v trí khác nhau trong không gian làm vi c. Yêuướ ạ ậ ị ệ
c u tìm ra m t đ ng đi liên t c t v trí ban đ u đ n v trí đích sao choầ ộ ườ ụ ừ ị ầ ế ị
chánh đ c nh ng va tr m v i nh ng v t c n trên đ ng đi. Quá trìnhượ ữ ạ ớ ữ ậ ả ườ
xác đ nh l trình có th chia làm hai thao tác chính đó là: xây d ng khôngị ộ ể ự
gian tr ng thái và tìm đ ng.ạ ườ
Có th tóm t t bài toán nh sauể ắ ư
Đ u vào (Input): ầ
Nh ng mô t hình h c c a ng i máy, môi tr ng và nh ngữ ả ọ ủ ườ ườ ữ
ch ng ng i v t, v trí ban đ u và v trí đích.ướ ạ ậ ị ầ ị
Đ u ra (output): ầ
Đ ng đi t v trí đ u đ n v trí đích ho c thông báo khôngườ ừ ị ầ ế ị ặ
t n t i đ ng điồ ạ ườ
M t s ký hi u và khái ni m c b n:ộ ố ệ ệ ơ ả
- Nh ng ch ng ng i v t: là nh ng không gian đã b chi m ch .ữ ướ ạ ậ ữ ị ế ỗ
Robot không th di chuy n t i các v trí này.ể ể ớ ị
- Không gian tr ng: là nh ng không gian ch a b chi m ch . Robotố ữ ư ị ế ỗ
có th di chuy n t i các v trí này.ể ể ớ ị
- Ký hi u A: là ng i máyệ ườ
- W: là không gian c lit n i mà robot ho t đ ngơ ơ ơ ạ ộ
- B1,..., Bm là nh ng ch ng ng i v t c đ nh phân tán trong Wữ ướ ạ ậ ố ị
- FW: Không gian di chuy n c đ nh.ể ố ị
- FA: Không gian di chuy n c a ng i máy.ể ủ ườ
- Tr ng thái q c a A là m t tr ng thái v t lý (v trí và s đ nhạ ủ ộ ạ ậ ị ự ị
h ng) c a A.ướ ủ
- Không gian tr ng thái c a A là không gian C bao g m t t c cácạ ủ ồ ấ ả
hình tr ng có th c a Aạ ể ủ
- Không gian tr ng ố
=∩∈==
==
φ
φφ m
i
i
m
i
iFree CBA(q):CqCB/CC
11
hay
không gian tr ng là các ph n t ố ầ ử q sao cho q
∈
CFree
- Ký hi u v trí đ u c a robot là ệ ị ầ ủ qrobot v trí đích là ịqgoal