Robot tránh chướng ngại vật

Chương 2 THUẬT TOÁN TRÁNH CHƯỚNG NGẠI VẬT CHO ROBOT TỰ HÀNH GIỚI THIỆU Bài toán lập quỹ đạo di chuyển cho robot tự hành có thể chia làm hai dạng : bài toán toàn cục (global) và bài toán cục bộ (local). Ở bài toán toàn cục, môi trường làm việc của robot được biết trước và từ đó đường đi tránh vật cản được tính toán từ lúc bắt đầu di chuyển. Trong bài toán cục bộ, môi trường làm việc của robot hoàn toàn chưa bíết hoặc chỉ biết một phần. Đối với bài toán này, các cảm biến gắn trên robot sẽ phát hiện vật cản để điều khiển hệ thống dẫn hướng robot từ điểm đầu đến điểm đích mà không chạm vật cản. Bài toán toàn cục tỏ rõ lợi thế là ta đã biết trước có đường đi (tối ưu ) tới đích hay không trước khi robot khởi hành. Tuy vậy nó có hạn chế là đòi hỏi nhiều lệnh tính toán và bộ nhớ và trong thực tế, yêu cầu biết trước tòan bộ môi trường khó khả thi. Trong khi đó, robot tìm đường cục bộ chỉ biết được môi trường xung quanh qua sensor cảm nhận môi trường. Vì thế robot tìm đường cục bộ có thể không hoàn thành việc đến đích (mặc dù thực tế có đường đến đích )trong trường hợp đặc biệt. Tuy nhiên, yêu cầu tính toán, dung lượng nhớ thấp cùng tính linh họat cao như tránh được vật cản ngay khi vật cản di chuyển động. Hiện nay cách kết hợp toàn cục và cục bộ đang ngày càng phổ biến giúp robot có tính linh hoạt cao. Nội dung của luận văn tập trung giải bài toán cục bộ, với robot omni di chuyển trong mặt phẳng với các vật cản tĩnh, đích của robot là khuôn mặt người được bắt bằng một webcam. Robot sẽ di chuyển tới vị trí người đang đứng và tránh các vật cản gặp phải trên đượng đi. Việc phát hiện vật cản được thực hiện bởi 3 cảm biến siêu âm. Phần 2.2 dưới đây sẽ trình bày các phương pháp xác định vật cản bằng cảm biến siêu âm hoặc camera, và sẽ trình bày chi tiết thuật tóan sinh viên lựa chọn để thực hiện đề tài trong phần 2.3. CÁC PHƯƠNG PHÁP TRÁNH VẬT CẢN 2.2.1 Phương pháp bám tường ( wall-following method) Ở phương pháp này, robot di chuyển dọc theo vật cản với một khoảng cách định trước. Phương pháp này thích hợp khi chúng ta không có một bản đồ cụ thể môi trường hay một sự định vị rõ ràng. Phương pháp này còn được áp dụng khi chỉ có những thông tin không đầy đủ, đại loại như “hành lang này sẽ dẫn đến cánh cửa kia ”, robot có thể sử dụng tường để định hướng quỹ đạo hoàn tất nhiệm vụ. Thuật toán sử dụng trong phương pháp bám tường dựa trên sự biểu diễn “nhận thức” (tri giác). Khái niệm này sử dụng thông tin từ các cảm biến siêu âm để thu nhận nhận thức tổng quát về môi trường lân cận. Các thông tin này không có nghĩa là vị trí chính xác của vật cản và hướng của tường. Ngược lại, các nhận thức tổng quát này giúp robot nhận biết chính nó trên một hướng hợp lý hơn là một vị trí chính xác. Các hướng này có thể được mô tả bằng các giá trị ngôn ngữ như là phía trước bên trái, ở đằng xa hoặc rất chậm. Việc mô tả này được thực hiện bằng logic mờ và do đó, logic mờ sẽ là chìa khóa của vấn đề. Một đề tài về robot bám tường đã được tiến hành ở trung tâm nghiên cứu robotic IKERLAN ở Tây Ban Nha đã cho thấy robot có thể tránh được tất cả chướng ngại vật trong nhiều trường hợp thử nghiệm. Với một khoảng cách với tường cho trước là 0.6 m và vận tốc robot đạt được 0.45m/s dưới hai điều kiện : trước tiên robot không bị “mù” theo bất cứ hướng nào, tức là bất kì vật cản nào cũng sẽ bị phát hiện bởi ít nhất một cảm biến và thứ hai, tường và các vật cản phải tĩnh. Vật cản được robot hiểu là một phần của tường và nếu khoảng cách giữa vật cản và tường quá lớn thì nó sẽ bỏ qua. Khái niệm nhận thức tổng quát : Nhược điểm của cảm biến siêu âm là độ phân giải về hướng rất kém. Mặc dù những cảm biến này rất chính xác phản ánh khoảng cách đến vật cản gần nhất bằng tính phản xạ, nhưng vật cản lại có thể nằm bất cứ đâu trong một góc quét của cảm biến. Hơn nữa khoảng cách này lại phụ thuộc vào bề mặt của vật cản, khoảng cách và độ nghiêng của bề mặt so với trục cảm biến. Vì vậy rất khó để ngay lập tức mô tả môi trường xung quanh từ dữ liệu cảm biến đưa về, chẳng hạn như độ cong của bức tường. Khái niệm về nhận thức tổng quát tránh những khó khăn này bởi vì nó không bảo đảm điều gì về việc phác thảo môi trường xung quanh. Thay vào đó, nó hướng tới việc tạo ra một nhận thức chung chung về môi trường xung quanh từ dữ liệu từ cảm biến và biểu diễn lại bằng vector, gọi là vector nhận thức tổng quát. Để đáp ứng yêu cầu thì mỗi cảm biến siêu âm i được gán cho một vector nhận thức , hướng của nó trùng với trục của cảm biến và độ dài là một hàm của khoảng cách đo được theo công thức: (2.1) với và là khỏang cách xa nhất và gần nhất mà một vật cản được phát hiện, thì được giới hạn với các cận 0 và 1 theo công thức: (2.2) Vector tổng quát p thì bao gồm các vectơ thành phần . Hướng của p là hướng của tổng các vector thành phần và chiều dài bằng vector thành phần dài nhất Độ biến thiên vector tổng quát theo thời gian là đại lượng vô hướng tính theo công thức: pi=dpidt=∆di∆t(dmax-dmin) (2.3) pmax=vmaxdmax-dmin với là biến thiên nhận thức khi robot di chuyển trực diện tới vật cản với vận tốc lớn nhất . Hơn nữa, chỉ có giá trị dương của là được xem xét, do đó biến thiên nhận thức tương đối của cảm biến được tính : (2.4) Giá trị lớn nhất của biến thiên tương đối của các cảm biến kí hiệu là: Hình 2.1 Robot tự hành trong 3 tình huống bám biên Hình trên minh họa khái niệm nhận thức tổng quát trong 3 tình huống bám biên của robot. Nhận thức tổng quát khi đối với góc tường (trường hợp a ) thể hiện bởi 3 vector. Một cạnh tường gần hơn được nhận thức bằng một cảm biến, cạnh còn lại được nhận thức bằng hai cảm biến. Nhận thức sau thì không mạnh bằng nhận thức đầu do khoảng cách xa hơn. Mô tả về tình huống này dạng ngôn ngữ như sau: nhận thức tổng quát thì mạnh và liên quan đến phương pháp tuyến về bên phải và nơi nào đó phía trước. Một tình huống hay gặp là robot ở vào vị trí “dead-end” (hình b) khi robot dang di chuyển dọc theo tường bên phải. Khi robot đến cuối đường, vector nhận thức biến thiên nhanh hơn về phía trước. Sự biến thiên nhanh hay chậm tùy thuộc vào vận tốc của robot. Trong trường hợp góc tường mở (hình c), sự biến thiên mạnh hơn ở phía sau bên phải. Khái niệm về nhận thức tổng quát thì hoàn toàn phù hợp với việc mô tả bằng ngôn ngữ với vô số tình huống của robot. Sự mô tả này thì đơn giản, được thực hiện cùng với chuyển động của robot và được dùng như là ngõ vào của bộ luật trong giải thuật dùng logic mờ. Lúc này thì hướng của chính xác của cảm biến không còn quan trong nữa. Với giải thuật này robot có thể dễ dàng bám theo tường ngay cả khi chỉ có một cảm biến phát hiện tường. Một điều cần lưu ý rằng khái niệm nhận thức tổng quát là sự tổng hợp nhận thức các cảm biến, do đó nó có tên là “tổng quát”. Ngay cả những cảm biến theo hướng chuyển động là hướng về phía sau và nhận thức của chúng có vẻ không có giá trị nhưng sự đóng góp của chúng vào nhận thức tổng quát là như nhau. Sử dụng ví dụ ở hình dưới, nếu bỏ qua các cảm biến mà ta cho rằng không đóng góp vào chuyển động của robot thì sẽ dẫn robot theo một hướng sai lầm. Nếu dữ liệu của cảm biến 1 và 8 không được quan tâm thì góc giữa vector và vận tốc v sẽ nhỏ hơn . Theo giá trị ngôn ngữ có thể hiểu rằng: vector nhận thức tổng quát nằm đâu đó ở giữa phía trước và bên trái. Kết quả là robot sẽ di chuyển sang bên phải xa dần bức tường. Nhưng khi nó tiến gần bức tường đối diện thì vector sẽ hướng sang bên phải do thì giảm còn thì tăng. Cứ thế robot sẽ di chuyển qua lại giữa hai bức tường do bức tường mà robot bám theo dường như lúc nào cũng nằm phía sau robot do ta đã bỏ qua các cảm biến cần thiết. Hình 2.2 Robot sẽ di chuyển qua lại hai bức tường nếu ta không xét đến các cảm biến và c. Kết quả thực nghiệm : Hình 2.3 robot đi vào góc nhỏ và có những khe hở nhỏ giữa các bức tường, robot tìm được đường đi ngược lại. Hình 2.4 Robot gặp vật cản khi bám tường, khi đó robot thay đổi quỹ đạo vòng qua vật cản (B-C) rồi trở lại nhiệm vụ bám tường ( C-D) Phương phát phát hiện cạnh ( edge-detection) Một phương pháp cũng khá phổ biến là dựa trên việc phát hiện cạnh (edge-detection). Thuật toán đưa ra trong phương pháp này tìm cách phát hiện vị trí các cạnh đứng và lái robot vòng qua các cạnh “thấy được” đó. Đường nối hai cạnh “thấy được” xem như là biên của vật cản. Phương pháp này cũng có thể dùng cảm biến siêu âm để phát hiện vật cản. Điểm bất lợi của phương pháp này là robot phải dừng lại trước vật cản để thu thập thông tin. Tuy nhiên đây không phải điều khó khắc phục với những máy tính xử lý nhanh trong tương lai. Trong phương pháp dùng cảm biến siêu âm, robot đứng yên khi đang khi thực hiện việc quét toàn cảnh môi trường làm việc. Sau khi áp dụng một số giải thuật line-fitting , một kế họach chuyển động toàn cục được thiết lập cho quỹ đạo kế tiếp của robot. Hạn chế thường gặp của phương pháp này là độ chính xác của cảm biến siêu âm, thường rơi vào các nguyên nhân sau : Khả năng định hướng kém : hạn chế việc xác định vị trí cạnh trong không gian, phụ thuộc vào khỏang cách tới vật cản, và góc giữa bề mặt và trục phát sóng. Hiện tượng đọc chéo : gây ra bởi nhiễu sóng siêu âm từ các nguồn ngoài hay các cảm biến gây nhiễu lẫn nhau. Các nhiễu này thường khó để lọc bỏ và gây khó khăn cho việc tiến hành giải thuật. Sự phản xạ đều : khi góc của mặt phản xạ và trục cảm biến quá lớn, sóng phản xạ sẽ không trở về nơi phát và coi như vật cản không được phát hiện, hoặc nhận biết vật cản nhỏ hơn thực tế. Bất cứ các nguyên nhân nào trên đây cũng đều ảnh hưởng đến thuật toán phát hiện cạnh của vật cản ở một vị trí sai, hậu quả là quỹ đạo đưa ra không phù hợp. 2.2.3 Phương pháp biểu diễn vật cản bằng sơ đồ lưới xác định Một phương pháp biểu diễn xác suất của vật cản trong một mô hình môi trường dạng lưới ( grid-type world model) được phát triển tại đại học Carnegie-Mellon ở Pennsylvania, Mỹ. Mô hình luới xác định này thì đặc biệt phù hợp với điều kiện các dữ liệu thu từ cảm biến thì không chắc chắn, trong trường hợp này là cảm biến siêu âm. Trong lưới xác định ( certainty grid), vùng hoạt động của robot được biểu diễn bằng một mảng hai chiều các phần tử hình vuông, gọi là các cell. Mỗi cell chứa một giá trị xác định ( certainty value) gọi là CV thể hiện mức độ đáng tin cậy rằng có vật cản xuất hiện trong cell đó. Với phương pháp này, CV sẽ được cập nhật bằng một hàm xác suất có xét đến đặc điểm của cảm biến. Với cảm biến siêu âm có một tầm quan sát hình nón sẽ trả về một giá trị đo hướng tâm khoảng cách đến vật cản gần nhất nằm trong vùng hình nón, do đó không xác định cụ thể vị trí góc của vật thể. ( hình dưới thể hiện vùng A trong đó một vật thể phải được định vị để cho ra kết quả đo là d). Nếu một vật thể được phát hiện bởi cảm biến, nhiều khả năng vật thể này gần trục cảm biến hơn là phần biên của hình nón. Trong phương pháp này hàm xác suất sẽ tăng CV của các cell gần trục hơn là CV của các cell ở biên. Hình 2.5 Sơ đồ lưới: một giá trị d đo được chứng tỏ sự tồn tại của vật cản đâu đó trong vùng màu đen Trong thí nghiệm, robot tự hành đứng yên khi thực hiện việc quét toàn cảnh môi trường với 24 cảm biến. Kế tiếp, hàm xác suất được áp dụng với mọi giá trị khoảng cách đo được để cập nhật lưới xác định. Cuối cùng, robot di chuyển đến vị trí mới rồi dừng lại và lặp lại quá trình trên. Khi robot di chuyển hết căn phòng theo cách này thì lưới xác định có thể xem như bản đồ tương đối chính xác của căn phòng. Một quỹ đạo tổng quát có thể được tính toán off-line cho những lần hoạt động về sau. Phương pháp trường thế ( Potential Field Method) Trong phương pháp này, vật cản gây ra một lực đẩy, khi mà mục tiêu lại áp dụng một lực kéo với robot. Vector lực tổng hợp R bao gồm tổng của lực kéo từ mục tiêu và lực đẩy từ vật cản được dùng để tính toán cho một vị trí của robot. Với R là lực gây nên gia tốc trên robot, vị trí mới cho robot được tính toán bằng các thuật toán. Phương pháp Virtual Force Field do Borenstein đưa ra sử dụng luới hai chiều theo hệ tọa độ De-cac, gọi là luới biểu đồ ( histogram grid) C để biễu diễn vật cản. Mỗi ô (i,j) trong lưới được gán một giá trị xác định (certainty value, CV ) kí hiệu là thể hiện độ tin cậy việc tồn tại vật cản tại ô đó. Việc biểu diễn này khá giống với certainty grid ở phần trên, ở histogram grid, các CV được tăng lên khi cảm biến siêu âm xác định sự hiện diện của vật cản tại ô đó. Hình 2.6 Histogram Grid Khái niệm về trường thế được áp dụng vào histogram grid như hình trên. Khi robot di chuyển một cửa sổ ô đi kèm theo nó, nằm trên một vùng hình vuông của C. Ta gọi vùng này là “active region” kí hiệu là và các ô thuộc vùng này gọi là “active cells” kí hiệu là . Trong thí nghiệm, kích thước của cửa sổ là 33x33 ô, và kích thước ô là 10cm x 10cm và cửa sổ luôn bao quanh vị trí hiện tại của robot. Mỗi active cell gây ra một lực đẩy với robot, biên độ lực tỉ lệ thuận và tỉ lệ nghịch với với d là khoảng cách giữa ô và tâm của robot, n là một số dương : (2.5) với : : hằng số lực đẩy : khoảng cách giữa active cell (i,j) và robot : giá trị xác định của active cell (i,j) W : bề rộng của robot : tọa độ hiện tại của robot : tọa độ của active cell (i, j) Tổng tất cả các lực đẩy ký hiệu là : (2.6)Đồng thời, một lực kéo do mục tiêu gây ra tác dụng lên robot : (2.7) với: : hằng số lực kéo : khoảng cách từ mục tiêu đến robot : tọa độ của mục tiêu Tổng lực kéo và lực đẩy sẽ được vector lực kết quả R: (2.8) Hướng của R kí hiệu là , đơn vị deg, dùng làm giá trị tham chiếu cho lệnh chuyển hướng của robot: (2.9) với k: hằng số tỉ lệ chuyển hướng : hướng hiện tại của robot Phương trình này là cơ sở cho việc điều khiển robot. Các hạn chế của phương pháp trường thế : Sập bẫy khi di chuyển đến ngõ cụt tạo bởi nhiều vật cản phức tạp Không qua được khe giữa hai vật cảnHình dưới minh họa trường hợp này, lực đẩy từ hai vật cản 1 và 2 lần lượt là và, tổng hay lực cản này sẽ hướng robot ra xa mục tiêu theo chiều ngược lại, nếu cộng với lực kéo từ mục tiêu thì được lực kết quả R không hướng robot tránh vật cản. Hình 2.7 Trường hợp robot không qua được khe 2 vật cản Dao động khi gặp vật cản : hạn chế này xảy ra ở việc tính toán thuật toán, không phân tích kĩ ở đây. Dao động khi đi trong ngõ hẹp : nguyên nhân do robot nhận được lực đẩy từ cả hai bức tường. 2.2.5 Phương pháp dùng optical flow : Khác với các phương pháp trên, phương pháp này chủ yếu sử dụng camera và đã được sinh viên Phan Tuấn Hải ( 40400725) thực hiện trong luận văn tốt nghiệp, ở đây chỉ trình bày tóm tắt cơ sở lý thuyết và giải thuật. Khi camera di chuyển, nó sinh ra một chuỗi theo thứ tự các frame, mỗi frame là một ánh xạ từ không gian 3D lên một mảng pixel 2D. Giả sử trong ảnh là một cái bàn, các điểm trên cạnh bàn là những điểm cần quan tâm. Khi camera di chuyển thẳng ta sẽ nhận thấy sự di chuyển nhỏ của những điểm này theo chuỗi frame sinh ra. Nếu cái bàn ở xa, sự dịch chuyển quan sát được sẽ nhỏ; khi bàn ở gần, độ dịch chuyển này sẽ lớn hơn. Ta tiến hành tính tóan vector dịch chuyển cho một số điểm nhất định sẽ có thể định hình được vùng di chuyển của vật. Những vùng này gọi là vùng optical flow. Có hai cách tính toán các optical flow : Thuật toán Dense Optical Flow ( Optical Flow đặc) : tính toán các vector này cho mọi điểm trong ảnh Thuật toán Sparse Optical Flow ( Optical Flow thưa) : chỉ sử dụng cho các điểm đặc biệt ( ví dụ như cạnh) Hình 2.8 Optical Flow của bàn tay Ngõ vào của một hệ optical flow là một chuỗi các ảnh thu được từ bên ngoải, chuỗi này sẽ chứa các thông tin để ước lượng các vector di chuyển. Do đó, camera cũng phải di chuyển hết trong suốt quá trình lấy ảnh. Giả sử ảnh đầu tiên được lấy ở thời điểm t, xét điểm (u,v) trên ảnh có cường độ I(u,v,t). Nếu khoảng thời gian giữa hai lần lấy ảnh là đủ nhỏ thì xem như cường độ điểm ảnh đang xét không đổi. Xét cường độ điểm ảnh tại thời điểm t là I(u,v,t). Từ sự di chuyển của camera, cùng một điểm đó, nó sẽ xuất hiện ở frame tiếp theo nhưng ở vị trí khác. Giả sử độ dịch chuyển đó được biểu diễn bằng vector . Khi đó cường độ của điểm ảnh sẽ không đổi : (2.10) trong đó u,v lần lượt là hai trục nằm ngang và thẳng đứng trong hệ tọa độ của miền ảnh. Khai triển Taylor ở vế trái biểu thức: (2.11) Do độ dịch chuyển là rất nhỏ nên các thành phần bậc cao trong khai triển được bỏ qua. Do đó : (2.12) Chia hai vế của biểu thức cho và cho tiến về 0, ta có : (2.13) (2.14) Từ đó ta được : (2.15) và là hai vận tốc của điểm theo hai hướng nằm ngang và thẳng đứng. Biểu thức (2.15) được coi là điều kiện của Optical Flow. Việc tính toán cụ thể được chia thành hai phần : chọn phần tử bằng thuật toán Shi-Tomasi và theo dõi các phần tử đó bằng thuật toán Pyramid Lucas-Kanade. Việc tránh chướng ngại vật dựa trên kỹ thuật cân bằng mà ý tưởng chủ đạo là thị sai của sự dịch chuyển. Khi robot di chuyển thẳng, những vật ở gần sẽ có phần tử di chuyển nhanh hơn những phần tử của vật ở xa. Đồng thời trong phạm vi quan sát thi những vật ở gần hơn sẽ dễ theo dấu hơn nên phần tử được chọn cũng nhiều hơn. Từ ý tưởng đó, robot sẽ di chuyển để tránh xa hường có optical flow lớn nhất ( hai hướng được xét là hướng trái và hướng phải). THUẬT TOÁN DẪN HƯỚNG THÍCH NGHI ( ADAPTIVE NAVIGATION) Thuật toán này được trình bày trong tài liệu tham khảo [2]. Đây là một kĩ thuật dẫn hướng cục bộ với vị trí ban đầu và đích đã biết trước, các vật cản được phát hiện bởi ba cảm biến đo khoảng cách từ robot đến vật cản gần nhất nhưng theo ba hướng khác nhau. Hướng di chuyển của robot được quyết định bởi hướng đến đích và hướng tránh vật cản tính toán được. Điều kiện để thực hiện phương pháp là các vật cản phải đứng yên. Điểm mạnh của phương pháp là chỉ yêu cầu một ít thông tin về môi trường xung quanh so với các phương pháp khác và luật dẫn hướng cũng đơn giản và linh họat hơn sử dụng phương pháp trường thế ( potential field method). Đây chính là phương pháp em chọn để thực hiện đề tài. Mô hình robot và kĩ thuật dẫn hướng thích nghi Xét một bài toán dẫn hướng hai chiều (2D) trong hình (2.9) khi mà vị trí và vận tốc của robot được biểu diễn trong hệ tọa Decac ( x(t), y(t) và v(t) với t là thời gian ). Điểm bắt đầu và kết thúc lần lượt là và (0,0). Góc biểu diễn hướng của robot là , (), được đo so với trục x và có giá trị đầu là . Có khả năng có vật cản trên đường đi của robot nên mục tiêu đặt ra là dẫn hướng robot đến đích đồng thời tránh được vật cản. Các giả định sau được đưa ra để giải bài toán : (A1) : robot chỉ di chuyển về phiá trước (A2) : robot rẽ trái hay phải với bán kính nhỏ nhất (A3) : vận tốc của robot là hằng số, trừ khi tiến đến gần đích Hình 2.9 Mô hình bài toán dẫn hướng thích nghi Phương trình chuyển động của robot : (2.16) Giả định A2 được biểu diễn bằng bất đẳng thức : (2.17) Xét biểu thức dạng toàn phương : (2.18) với là góc điều khiển robot đến đích hoặc tránh vật cản. Nếu như không có vật cản và giả định A2 không được xét đến thi robot sẽ ngay lập tức quay về phía đích lúc bắt đầu và cứ thế chạy đến đích. Đây có thể coi là đường đi tối ưu nhưng không không khả thi với điều kiện của robot. Do đó, luật dẫn hướng sau đây được đưa ra : (2.19) với là hằng số dương. Phương pháp suy giảm Gradient được áp dụng để tìm ra góc dẫn hướng nhằm tối thiểu hóa E(t), là góc định hướng điều kiện. Để hiểu rõ vấn đề, ta xét trường hợp dẫn hướng không có vật cản. Xem như là góc định hướng dẫn robot đến đích. Trong trường hợp này với : (2.20) =tan-1y(t)x(t), với là góc vị trí (gốc tọa độ trùng điểm đích). Khi robot ở xa đích, là hằng số. Do (1.19) là phương trình vi phân bậc nhất với hệ số dương , một cách đơn điệu tiến về trong ngõ dạng bước ( step) và giá trị lớn nhất của là . Có cảm giác rằng robot sẽ lập tức quay về hướng đích và tiến về đích. Tuy nhiên, do thay đổi so với tọa độ của robot ( x(t), y(t)), và cũng thay đổi theo thời gian. Khi robot gần đích, ta phải xét thêm về sự ổn định của luật dẫn hướng này. Cách tránh vật cản Robot sử dụng 3 cảm biến khoảng cách để đo khoảng cách từ nó đến vật cản. Gọi , và là các khoảng cách theo các hướng ở giữa (center), trái (left), phải (right). Hướng cảm biến trái và phải lệch so với cảm biến giữa một góc . Các giả thiết sau được đặt ra cho cảm biến và vật cản: (A4) : Khoảng đo được lớn nhất là , nếu cảm biến không phát hiện vật cản hoặc khoảng cách lớn hơn thi ngõ ra cảm biến là -1. (A5) : Các vật cản được mô hình là các đa giác lồi với các góc ở đỉnh phải lớn hơn . (A6) : Khoảng cách giữa các vật cản thì lớn hơn Giả định (A4) thể hiện tình huống thực tế. Mục đích của giả định (A5) là đảm bảo việc phát hiện vật cản bởi cả ba cảm biến. Giả định (A6) cần thiết cho việc tránh vật cản sẽ được giải thích sau. Trường hợp 3 cảm biến đều phát hiện vật cản : Hình (2.10) mô tả các trường hợp phát hiện vật cản có thể xảy ra. Khi vật cản được phát hiện ở cả 3 hướng và như hình (a), Khoảng cách đến vật cản bên trái lớn hơn bên phải nên robot nên rẽ trái. Đặt là góc trong hình vẽ (a), robot nên rẽ một góc để tránh vật cản và tương tự cho trường hợp . Đem phản ứng này vào luật dẫn hướng, ta được: (2.21) với (2.22) d = max() (2.23) sgn(x) = (2.24) Hình 2.10 Các trường hợp phát hiện vật cản của robot Trường hợp 2 cảm biến phát hiện vật cản : Trong hình b và c, một vật cản được phát hiện phía trước robot (). Trong trường hợp đầu và ( tương tự trường hợp và ). Điều này có nghĩa rằng một khoảng trống không vật cản đang mở ra phía bên trái và luật dẫn hướng được cho bởi: (2.25) Trong trường hợp sau, và , phần không gian bên phải có vẻ thóang hơn bên trái. Tuy nhiên có thể có một vật cản bên phải mà hiện tại robot chưa phát hiện được. Để đảm bảo việc tránh vật cản, robot nên rẽ trái một góc ( như trong hình c) và luật dẫn hướng giống như công thức (1.21). Khi < 0 ( hình d) việc chuyển hướng là không cần thiết vì không có vật cản trên đường di chuyển của robot. Do đó . Trường hợp một cảm biến phát hiện vật cản : Có hai trường hợp được xét đến trong hình e và hình f. Trong trường hợp đầu việc chuyển hướng là không cần thiết do , nên . Trong trường hợp sau, do nên robot phải chuyển hướng. Tuy nhiên do và đều âm nên việc rẽ trái hay rẽ phải là như nhau. Ta quyết định rẽ trái 90 độ: (2.26) Trong tất cả các trường hợp từ a đến f thông tin từ 3 cảm biến không thể bao quát đầy đủ sơ đổ các vật cản trong không gian. Tuy nhiên, do , và được cập nhật theo thời gian thực và thêm giả định A5, robot có thể tránh được vật cản trong hầu hết các trường hợp. Xây dựng thuật toán dẫn hướng thích nghi Một yêu cầu cơ bản là, khi vật cản được phát hiện thì việc tránh vật cản phải được đặt lên trên việc đến đích. Tuy nhiên, nếu việc đến đích bao quát luôn cả việc tránh vật cản thì robot vẫn thực hiện việc đến đích theo công thức (2.20). Bây giờ ta xem xét khả năng robot vẫn đến đích ngay cả khi phát hiện vật cản. Trên hình 2.10 a, b, c, và f, việc chuyển hướng là cần thiết để tránh vật cản. Nếu các bất đẳng thức này được duy trì: (2.27) hoặc (2.28) thì việc chuyển hướng đến đích đủ để tránh vật cản. Do đó góc điều khiển là: Trong hình 2.10 e, chuyển hướng là không cần thiết. tiếp tục được gán bằng nếu điều kiện này xảy ra : > , , (2.29) hoặc < , , (2.30) Trong hình 2.10 d, việc lái cũng không cần thiết. Không giống hình e, vật cản được phát hiện ở cả hai hướng trái và phải nhưng không phát hiện ở giữa nên robot vẫn giữ nguyên hướng. Tổng hợp lại, một thuật tóan để tính tóan góc điều khiển như sau : begin if and then else if then if or then else end if else if and > , or and < , then else end if end. 2.4 TỔNG KẾT CÁC PHƯƠNG PHÁP TRÁNH VẬT CảN : Các phương pháp trên đều có những ưu nhược điểm và phạm vi áp dụng khác nhau. Phương pháp điều khiển bám biên giải quyết được vấn đề sai số của cảm biến siêu âm bằng cách đưa ra khái niệm nhận thức tổng quát và giải thuật mờ, nhưng robot chỉ di chuyển theo quỹ đạo nhất định, không áp dụng được cho môi trường phức tạp. Với phương pháp phát hiện cạnh, đòi hỏi cảm biến siêu âm phải quét hết môi trường làm việc sau đó tính toán để thiết lập quỹ đạo cho robot, do đáp đáp ứng của robot khá chậm. Phương pháp biểu diễn vật cản bằng sơ đồ lưới đòi hỏi số lượng cảm biến lớn để có thể bao quát toàn bộ khu vực hoạt động, tuy nhiên lại khắc phục nhược điểm góc mở lớn của cảm biến siêu âm với việc biểủ diễn dữ liệu bằng hàm xác suất. Phương pháp trường thế đòi hỏi tọa độ của đích đến phải được biết trước, không thích hợp với các mục tiêu di chuyển như là trong đề tài. Phương pháp dùng Optical Flow có ưu điểm là chỉ sử dụng một camera để phát hiện vật cản. Tuy nhiên phương pháp này lại đòi hỏi việc lập trình tính toán khá phức tạp do phải tính các gradient cho các điểm trên hình, do đó thời gian xử lý sẽ lâu. Đối với phương pháp dẫn hướng thích nghi, ta chỉ cần có ba cảm biến siêu âm và giải thuật tương đối đơn giản. Phương pháp này thích hợp cho các môi trường không phức tạp với các vật cản tĩnh và có kích thước đủ lớn. Dù trong thuật toán gốc thì tọa độ của đích đến được xác định trước nhưng ta cũng có thể cải tiến cho các mục tiêu di động, trong đề tài thì mục tiêu di động chính là khuôn mặt người.