喜歡就充值下載吧。。資源目錄里展示的文件全都有，，請放心下載，，有疑問咨詢QQ:414951605或者1304139763 ======================== 喜歡就充值下載吧。。資源目錄里展示的文件全都有，，請放心下載，，有疑問咨詢QQ:414951605或者1304139763 ======================== 濰坊學(xué)院本科畢業(yè)設(shè)計 生物系統(tǒng)工程（2003）86（2）135-144 DOI：10.1016/S1537-5110（03）00133-8 AE—自動化與新興技術(shù) 黃瓜采摘機器人的無碰撞規(guī)劃 E.J.凡Henten J.海明; B.A.J.凡Tuijl; J.G.短號;研究Bontsema 溫室工程，農(nóng)業(yè)和環(huán)境工程研究所（IMAG BV公司），箱43，NL-6700機管局瓦赫寧根，荷蘭;電子郵件通訊作者：eldert.vanhenten wur.nl （2002年4月26日收到，2003年7月8號以修訂后的形式接受; 2003年8月29日在網(wǎng)上發(fā)表） 在農(nóng)業(yè)和環(huán)境工程學(xué)院，對于黃瓜自動收獲機，其中最大的一個挑戰(zhàn)方面就是在采摘的過程中實現(xiàn)一種快速精確的手眼協(xié)調(diào)的操作。這個程序包含兩個主要的組成部分。首先，采集信息機器人的工作環(huán)境，其次，一個程序可以讓機器人末端執(zhí)行器對黃瓜產(chǎn)生無碰撞機械運動。這篇文章主要闡述了后者，無碰撞機械運動所產(chǎn)生的所謂的路徑搜索算法。在這項研究中這個A-search算法被應(yīng)用著，用一些數(shù)值的例子對黃瓜收割應(yīng)用的搜索過程分析說明。得出的結(jié)論是，無碰撞運動可以用于采摘黃瓜的機械手的自由度的計算。這個A-search算法非常易于實施和魯棒。當(dāng)找不到解決方案時這個算法要不產(chǎn)生一個解決方案要不就停止工作。這個有利的財產(chǎn)然而卻使算法過分的緩慢，結(jié)果表明這個算法不包括多智能的搜索過程。我們可以知道，為了滿足每10S為一個單一收獲循環(huán)的要求，還需要做進(jìn)一步的研究，去尋找發(fā)現(xiàn)快速的算法，使用盡可能多的關(guān)于這個問題特定結(jié)構(gòu)的信息來產(chǎn)生解決方案，如果這個算法找不到解決方案并能給出明確的信息。 1. 介紹 1996年，農(nóng)業(yè)和環(huán)境工程學(xué)院開始研究自主的黃瓜采摘機器人的發(fā)展，這個項目是由荷蘭農(nóng)業(yè)部，食品和漁業(yè)部門支持的。為農(nóng)業(yè)應(yīng)用設(shè)計機器人的任務(wù)所提出的議題不涉及其他行業(yè)(Gielinget al., 1996 ; Van Kollenburg-）。機器人必須處在一個高度非結(jié)構(gòu)化環(huán)境中，在這里沒有兩個場景是一模一樣的。農(nóng)作物和水果都易于被機械損傷應(yīng)給小心處理。機器必須能夠在不利的條件下運轉(zhuǎn)，如相對較高的溫度和濕度以及光線變化的條件。最后，為了符合成本效益，就機器人采摘運動的速度和成功率而言，機器人需要滿足高的性能特點。在這個項目中這些具有挑戰(zhàn)性的問題已經(jīng)被一個機械工程，傳感技術(shù)（計算機視覺等），系統(tǒng)和控制工程，電子、軟件工程，物流，最后但不是最少園藝工程分享的互動的方式解決(Van Kollenburg-Crisan et al., 1997 ; Bontsema et al., 1999 ; Meuleman et al., 2000 )。 自動收割機的開發(fā)研制中最具有挑戰(zhàn)性的問題之一就是達(dá)到快速精確的手眼協(xié)調(diào)的，即達(dá)到機器人在采摘運動中感官信息的采集和機器人運動控制之間的有效相互作用，就像人們做的那樣。在園藝實踐中，一個訓(xùn)練有素的工人只需要3-6S采摘和存儲一個水果，那種表現(xiàn)是很難被打敗的。幸運的是，就機器人的采摘速度而言沒有必要達(dá)到那么高的性能特點。一項任務(wù)分析顯示，考慮經(jīng)濟可行性，一個單一采摘運動可能只需要10S (Bontsemaet al., 1999 )。仍然，機器人運動應(yīng)盡可能快的同時防止機器手的碰撞，手和收獲水果作物，溫室結(jié)構(gòu)還有機器人自身的碰撞（如汽車視覺系統(tǒng)）。在荷蘭，黃瓜生產(chǎn)設(shè)施，機器人運行在一個非常緊張的工作環(huán)境中。最后，為了保證收獲果實的質(zhì)量，在運動路徑的各個部分對機械手的速度和加速度加以約束。 為了達(dá)到理想的手眼協(xié)調(diào)，一個人需要環(huán)境的感官信息的采集和算法去為機械手計算這種無碰撞運動。正像Meuleman et al. (2000) 報道的那樣。在這個項目中感覺系統(tǒng)是基于計算機視覺的。本文著重論述了收獲機的機械手的無碰撞運動軌跡的快速生成。盡管有相當(dāng)大的研究工作花在自動收集蔬菜水果方面，但是這個問題在農(nóng)業(yè)工程研究中沒有引起人們極大的關(guān)注。(see e.g. Kondoet al., 1996 ; Hayashi& Sakaue, 1996 ; Arima & Kondo, 1999 )。 本文概述如下，在第二節(jié)對采摘機器人進(jìn)行了闡述，在第三節(jié)，講述的是一個單一收獲操作的任務(wù)序列，然后，第四節(jié)，表述的是無碰撞規(guī)劃的自動算法的組成。為了能夠深入洞察算法的運行，在第五節(jié)對該算法在第二級自由度的機械手上進(jìn)行了解釋說明，第六節(jié)包含一個應(yīng)用于收獲機器人身上的six-DOF RV-E2三菱機械手的運動規(guī)劃實驗結(jié)果。第七節(jié)包含結(jié)束語和對未來研究的建議。 2．采摘機器人 圖1.黃瓜收獲機器人的功能模型;（a）車輛;（b）廣角相機;（c）七度的自由度機械手;（d）最終效應(yīng);（e）激光測距儀和攝像機的位置當(dāng)?shù)爻上?（f）計算機和電子產(chǎn)品;（g）與220伏電源線卷軸;（h）氣動泵;（i）供熱管 圖一中，一個采摘機器人的功能模型被展示出來。它包含一個用于溫室走道里的收獲機進(jìn)行粗定位的自主車輛。這車采用加熱管作為一個鐵路進(jìn)行指導(dǎo)和支持。它作為一個移動平臺裝載電源、主動泵、各種數(shù)據(jù)收集和控制的電子硬件、一個用于監(jiān)測和定位植物上黃瓜位置的廣角攝像系統(tǒng)和一個用于機械末端運行器定位的七個自由度的機械手。這個機械手由安裝著六個自由度的Mitsubishi RV-E2機械手的滑動線路構(gòu)成。這個RV-E2機械手包括一個人形的機械手臂和球形的手腕。這個機械手有個能夠抓去0.2毫米的穩(wěn)態(tài)精度并能夠在惡劣的溫室氣候（高濕度和高溫度）條件下滿足一般的衛(wèi)生的操作方面的要求。這個機械手裝有一個末端執(zhí)行器。它包括兩部分：一個爪抓住水果，另一個爪切割水果從植物上分離出來。這個末端執(zhí)行器帶有一個末端激光測距系統(tǒng)或一個小相機。他們是用來在黃瓜附近能夠更好地進(jìn)行運動控制而獲取感官信息的，如果需要的話。 3.單一收割運動的任務(wù)序列 圖2. 一個單一的收獲作業(yè)任務(wù)序列：3D，三維，TCP，工具中心點 圖二展示的是一個單一的收獲運動的一個任務(wù)序列。在采摘操作中接近黃瓜被公認(rèn)為是一個兩階段的過程。首先，用安裝在車輛上的攝像系統(tǒng)，黃瓜果實被檢測到他的成熟認(rèn)定和位置是不確定的。如果我們決定采摘黃瓜則低分辨率圖像的車載攝像機就用于定位機器人末端執(zhí)行器鄰近黃瓜附近這一帶。一旦末端執(zhí)行器抵達(dá)鄰近的黃瓜，然后利用末端執(zhí)行器上面的激光測距系統(tǒng)或攝像系統(tǒng)為最終的準(zhǔn)確的接近黃瓜獲得黃瓜定位環(huán)境的高分辨率的信息。末端執(zhí)行器緊握并消減果子的莖。夾持固定分離的水果最后收獲果實移動到存儲箱。 避障運動規(guī)劃將用于黃瓜的初步做法以及收獲黃瓜回程箱子，來保證，如機器人車輛本身的工作空間中的其他對象，但也源于，如果目前，葉片和溫室建設(shè)的部分都沒有命中。顯然，收獲的黃瓜，增加最終的效應(yīng)，應(yīng)考慮在機械臂返回到存儲議案的大小。黃瓜的平均長度為300mm。 4.一個無碰撞運動規(guī)劃算法 圖3.無碰撞的自動生成程序議案 圖3顯示了一個程序，自動生成赫爾曼（1986年）的工作基礎(chǔ)上的黃瓜采摘機器人無碰撞運動的組成部分。無碰撞運動規(guī)劃依賴于三維（3D）機器人的物理結(jié)構(gòu)以及在機器人操作的工作區(qū)的信息。因此，在無碰撞機器人運動規(guī)劃的第一步是三維世界描述的收購。這個描述是基于感官信息，如機器視覺以及先驗知識，例如，采摘機器人運動學(xué)的三維結(jié)構(gòu)，如三維模型，在數(shù)據(jù)庫中。有了這個信息，在任務(wù)定義階段，機器人的整體任務(wù)的計劃。決定最后的位置和方向的效應(yīng)最終結(jié)果中的黃瓜最好的方法。也定義在此階段的具體位置和方向約束等。在階段目標(biāo)的位置和方向的最終任務(wù)定義中定義的效應(yīng)，逆運動學(xué)，將目標(biāo)配置的manipulator.The目標(biāo)配置跨lated表示作為一個線性滑軌的翻譯和6的組合七自由度機械手關(guān)節(jié)的旋轉(zhuǎn)。使用此信息的路徑規(guī)劃，路徑規(guī)劃，采用了搜索技術(shù)找到自由碰撞路徑，從開始操縱其目標(biāo)配置配置。一旦已成功完成的無碰撞路徑規(guī)劃，軌跡規(guī)劃軌跡，可以轉(zhuǎn)換成的無碰撞路徑由機器人執(zhí)行。通常情況下，路徑規(guī)劃過程中，只有在太空中的無碰撞配置有關(guān)，但沒有速度，加速度和運動平滑。軌跡規(guī)劃涉及這些因素。 thetrajectory策劃生產(chǎn)的機器人伺服系統(tǒng)的運動命令。在執(zhí)行階段執(zhí)行這些命令。運動規(guī)劃系統(tǒng)的一些部件將在更詳細(xì)地描述以下。 4.1世界的描述（采集） Meulemanet在一份文件中描述的基于機器視覺的世界描述收購的黃瓜采摘機器人（2000年）。視覺系統(tǒng)能夠偵測在綠色canopy.Moreover綠色黃瓜，視覺系統(tǒng)決定的黃瓜成熟。最后，利用立體視覺技術(shù)QUES，相機視覺系統(tǒng)產(chǎn)生的工作空間內(nèi)的攝像頭的視角3D地圖。在這樣的機器人能夠處理工作面臨的環(huán)境與它的變異。 圖6. 自由度的三菱RV-E2的操縱一個三維模型 如上所述，先驗知識，例如，機器人的物理結(jié)構(gòu)所需的無碰撞運動規(guī)劃。作為一個例子，圖4顯示了一個六自由度三菱RV-E2在MATLAB中實現(xiàn)機械臂的三維模型。機器人的三維結(jié)構(gòu)是由矩形和三角形構(gòu)造的多邊形表示。議案的戰(zhàn)略評估模型用于模擬期間，作為操縱機器人運動規(guī)劃期間的工作空間中的結(jié)構(gòu)部件的碰撞檢測的基礎(chǔ)上。 4.2逆運動學(xué) 逆機械臂運動學(xué)關(guān)節(jié)角度的計算和翻譯，處理結(jié)果在所需的位置和方向,工具中心點（TCP）機器人（克雷格，1989年）。 TCP是一個預(yù)定義的endeffector點。對于六自由度三菱RV-E2的操縱范戴克（1999年）獲得了逆機械臂運動學(xué)的解析解。七自由度機械手，即三菱RV-E2的機械臂安裝在一個線性滑軌，一個簡單的逆運動學(xué)解析解不存在由于在運動鏈的固有冗余。最近獲得這種冗余機械臂的逆運動學(xué)分析數(shù)值混合溶液（申克，2000年）。由于成熟的黃瓜的立場，該算法產(chǎn)生的七自由度機械臂的無碰撞收獲配置。此外，它可以保證關(guān)節(jié)黃瓜附近的精細(xì)運動控制有足夠的自由。 4.3路徑規(guī)劃 無碰撞路徑規(guī)劃算法已被大量的研究對象。例如見latombe（1991）和黃和阿胡加（1992）概述。 一個無碰撞路徑規(guī)劃主要包括兩個重要組成部分：搜索算法和碰撞檢測算法。搜索算法的搜索空間探索一個可行的，即collisionfree，從起點到目標(biāo)點的議案。在搜查過程中，被選中的碰撞檢測算法在搜索空間的每一步的可行性。該算法檢查機器人的碰撞與機器人的工作空間中的其他結(jié)構(gòu)部件。重要的是要注意，對于大多數(shù)路徑規(guī)劃者的搜索空間是所謂的配置空間機器人，其中關(guān)鍵的是從不同的3D工作區(qū)機器人。在黃瓜收獲機的7自由度機械手的情況下，配置空間是由一個聯(lián)合翻譯和6個聯(lián)合旋轉(zhuǎn)組合橫跨七維空間。然后，從一開始的位置和方向的工具中心點為無碰撞運動目標(biāo)的位置和方向在三維工作空間癤的單點無碰撞通過的議案的搜索搜索七維配置從一開始就配置目標(biāo)配置掩膜的空間。在這樣的運動鏈中的冗余問題很容易規(guī)避。有一到一個映射的配置空間中的點的位置和方向，在工作區(qū)中的工具中心點。然而，對于大多數(shù)的機器人，相反不成立。一個單一的位置和方向，在工作區(qū)中的工具中心點，然后可以復(fù)制機器人的多種配置。由于其獨特的代表性配置空間搜索是首選。然而，碰撞檢測，需要說明的身體姿勢操縱在與其他物體在三維工作空間的關(guān)系。因為每個配置代表一個單一的姿勢在三維工作空間的機械臂，可以很容易地驗證碰撞。然后，特別是機器人的運動結(jié)構(gòu)，工作空間的障礙可以被映射到配置空間的障礙將會顯示。 4.3.1.搜索算法 路徑搜索算法應(yīng)該是有效率的，如果存在的話，找到一個解決方案。后者的財產(chǎn)被稱為完整性（珍珠，1984年）。通常情況下，算法的完整性，保證不計算效率。然而，計算效率是至關(guān)重要的，當(dāng)上線的應(yīng)用程序需要。運動規(guī)劃的各個方面取得的洞察力，在這項研究中，上述計算效率的青睞，該算法的完整性。這樣的選擇的主要原因是一個完整的算法將找到解決辦法，或停止使用一個明確定義的停止準(zhǔn)則，如果不能找到一個解決方案。這是不是真實的，不保證完整性的算法。他們要么提供一個解決方案或卡住，恕不另行通知。在本研究中所謂的A *搜索算法（明珠，1984年;近藤，1991年，羅素和Norvig還，1995年）。它很容易實現(xiàn)和保證完整性。此外，它最大限度地降低成本標(biāo)準(zhǔn)，其中包括一個在搜索空間旅行距離的措施。該算法是在MATLABB實施 圖5.在離散化的二維配置空間的正交節(jié)點擴展：S，起始節(jié)點; G，目標(biāo)節(jié)點 使用配置空間機器人運動規(guī)劃的A *算法，離散化使用一個固定的電網(wǎng)結(jié)構(gòu)如圖5。用戶可以定義網(wǎng)格的大小和分辨率。然后A *算法搜索從一開始就格點的目標(biāo)格點的路徑，同時最大限度地降低成本函數(shù)f：此成本函數(shù)f包括路徑的成本遠(yuǎn)遠(yuǎn)?;和樂觀的估計成本從目前的位置目標(biāo)?：在這項研究中，歐拉規(guī)范被用來作為樂觀的估計到目標(biāo)節(jié)點的成本。A *算法是既完整和優(yōu)化。最優(yōu)保證的路徑獲得最大限度地減少使用成本函數(shù)。. A *算法使用兩個網(wǎng)格節(jié)點，開放列表和封閉列表清單。開放列表中包含了電網(wǎng)的成本函數(shù)，其中尚未被評估，而評估已閉合的名單上的網(wǎng)格節(jié)點的函數(shù)值的節(jié)點。這是假設(shè)的起點和目標(biāo)，可以選擇配置，配合網(wǎng)格節(jié)點或網(wǎng)格節(jié)點，在這些配置的密切鄰里。然后根據(jù)珍珠（1984），A *算法在網(wǎng)格如下操作節(jié)點。 (1)放在開放的起始節(jié)點S。 (2)如果打開是空的，則失敗退出，否則從關(guān)節(jié)點n FO其中f是最低的開放和地點。 (3)如果n等于目標(biāo)節(jié)點G;成功退出追溯從n指針為S得到的解決方案： (4)否則擴大N;生成所有其繼承人，并重視它們的指針回到N：對于每一個n的繼任者n’： (a) 如果是尚未打開或關(guān)閉，估計H（n’）（樂觀的估計成本的最佳途徑，從n’到目標(biāo)節(jié)點G），并計算F（n’）= G（n’）+ H（n’）其中g(shù)（n’）= G×（N）+ C（N，n’）C（N，n’）從節(jié)點n的過渡成本，節(jié)點n’和G（S）= 0 （b）如果已經(jīng)打開或關(guān)閉，直接收益率最低的G（1）道路沿線的指針; (c)如發(fā)現(xiàn)閉，1所需的指針調(diào)整和重新打開它 (5)轉(zhuǎn)到第2步。 電網(wǎng)擴張在第4步，可以采取多種形式。在本研究中所謂的正交擴充。這種方法是在圖5所示。 圖5還說明起始節(jié)點和目標(biāo)節(jié)點沒有以配合實際的起點和目標(biāo)機器人的配置。在這種情況下，最近的鄰居節(jié)點被選中。 在這個算法，停止準(zhǔn)則是非常明確的規(guī)定。如果在第3步，從開放列表中刪除的節(jié)點等于目標(biāo)節(jié)點，算法停止。另外，該算法將停止在第2步如果所有的網(wǎng)格節(jié)點進(jìn)行評估，并開放列表已成為空。在這種情況下，沒有找到一個解決方案。 路徑搜索過程中碰撞檢測的處理有兩種方式。首先，碰撞的配置可以通過掃描整個離散化配置空間的路徑搜索前確定。這將是在一個高維離散化的空間配置，具有很高的情況下計算昂貴決議電網(wǎng)。這將是更有效地評估在搜索過程中的網(wǎng)格節(jié)點的可行性。也就是說，在節(jié)點擴展一步，第4步，碰撞檢測算法檢查是否與該節(jié)點相關(guān)的機器人配置與環(huán)境或不產(chǎn)生碰撞。由于A *算法通常計算只有一小部分配置空間，這將產(chǎn)生相當(dāng)大的改善效率。碰撞可以在步驟4a中提到的成本函數(shù)加入一個大型的罰款處罰。另外，在碰撞中產(chǎn)生的一個網(wǎng)格點可以直接從省略開放期間電網(wǎng)的擴張階段的名單。在這項研究中，后者的做法被使用。 圖6.一個面向包圍盒模型的六個自由度的RV-E2的操縱 4.3.2.碰撞檢測算法 碰撞檢測算法在MATLAB中實現(xiàn)根據(jù)報道由Boyse（1979年）的想法。該算法計算的交點在工作區(qū)中的其他結(jié)構(gòu)部件表面的機器人模型的表面。計算兩個曲面相交的本質(zhì)歸結(jié)為決定從幾何中使用的標(biāo)準(zhǔn)工具，可以實現(xiàn)與其他表面的一個表面的邊緣相交。所有的一切，碰撞檢測是一項計算密集型的任務(wù)。因此，在實時應(yīng)用，如黃瓜機器人碰撞檢測，需要碰撞檢測的精度和可用計算時間之間的權(quán)衡。精確的CAD模型圖。 4包含600個三角形和矩形表面。一因素15減少計算時間，實現(xiàn)了從所謂的面向邊界建立了一個不太準(zhǔn)確的模型代替精確的操縱模型盒（更新行動）。這種三維機械手的只有36個移動的表面組成OBB的模型如圖6所示。顯然，一些與OBB的模型精度已提供計算速度的緣故。對于目前的調(diào)查，它被認(rèn)為是合理的。 5．例1：碰撞兩個度的自由操縱運動規(guī)劃 要說明的方法，結(jié)果與兩兩自由度轉(zhuǎn)動關(guān)節(jié)的機械臂的無碰撞運動規(guī)劃。圖7（a）顯示了一個人為的溫室環(huán)境，其中方塊代表黃瓜莖的目標(biāo)是移動的路徑（直打下了）操縱的工具中心點背后掛在黃瓜黃瓜冠捷干，沒有擊中任何黃瓜莖。這被認(rèn)為是黃瓜采摘過程中最困難的議案之一。 5.1.結(jié)果 為了說明操作的運動規(guī)劃算法，圖。 7（b）顯示相關(guān)的兩維的配置空間。一個離散化步驟五度使用。堅實的黑色方塊，稱為配置的障礙，代表機器人和黃瓜干之間的碰撞產(chǎn)生的配置。由字母S表示開始配置目標(biāo)配置是由字母G表示：他們代表的開始姿勢和圖采摘姿態(tài)。 7（一）。路徑搜索的目標(biāo)是要找到一個起始節(jié)點S和目的節(jié)點G之間的連接：觀察，首先，配置空間的地圖，揭示了真正復(fù)雜運動規(guī)劃的問題，可能看起來瑣碎的工作空間中。其次，觀察，一條直路從起始節(jié)點到目標(biāo)節(jié)點碰撞的結(jié)果，并因此是不可行的。圖7（c）所示的網(wǎng)格節(jié)點，記為*，A *算法的評估過程中向前搜索從起始節(jié)點到目標(biāo)節(jié)點。圖所示的配置空間中的最優(yōu)路徑。如圖7（d）及相關(guān)的無碰撞機械臂在工作區(qū)的議案快照。 7（E）。觀察，在工作區(qū)中的無碰撞運動的空間配置結(jié)果無碰撞的議案;機器人不會干擾與工作空間的障礙：黃瓜莖。最后，圖7（f）顯示網(wǎng)格節(jié)點A *算法當(dāng)一個落后的搜索目標(biāo)節(jié)點的起始節(jié)點進(jìn)行評估。 5.2.討論 結(jié)果表明，在配置空間沸騰的路徑搜索，找到一個點的運動軌跡，從一開始就配置目標(biāo)配置。 圖7（c）和（F）清楚地表明，碰撞檢查接續(xù)OFA先驗碰撞檢測路徑搜索過程中，由于A *算法，只有部分評估在配置空間網(wǎng)格點的優(yōu)勢。此外，研究結(jié)果表明，如果一個障礙之間開始配置和位于目標(biāo)配置，大量的網(wǎng)格節(jié)點找到了解決辦法之前，必須進(jìn)行評估。在這種情況下，A *算法不是很有效，在發(fā)現(xiàn)周圍的配置空間障礙的一種方式。障礙的情況下密切繞過一個目標(biāo)節(jié)點，一個落后的搜索可能會產(chǎn)生較少的解決方案由圖所示的計算時間。 7（F）。在這個例子中向后搜索向前搜索時取得117而不是146次迭代后的解決方案;減少20％。如果目標(biāo)節(jié)點位于兩者之間的障礙脊巷子盡頭，即使在較高的迭代次數(shù)減少使用向后搜索（結(jié)果未顯示）獲得。最好的搜索方向明確，取決于手頭的特定結(jié)構(gòu)的問題。這兩個圖。 7條（d）及（e）表明，以實現(xiàn)最優(yōu)路徑成本函數(shù)的意義，算法往往偷工減料，致使小機器人和障礙物之間的距離。要牢記這一特點，在實際運動規(guī)劃實驗時，傳感器為基礎(chǔ)的世界描述數(shù)據(jù)不準(zhǔn)確容易。然后可能會發(fā)生碰撞，不占在運動規(guī)劃。最后，圖7（d）顯示，由于電網(wǎng)結(jié)構(gòu)和正交擴展的路徑搜索過程中的網(wǎng)格節(jié)點，運動路徑包含了一些尖角。這將導(dǎo)致強不必要的加速和減速的鏈接時，在實踐中實施。在第4節(jié)的建議，為平滑軌跡規(guī)劃的議案等不良行為的來電。 6．例2：碰撞為6度的自由操縱運動規(guī)劃 這一段演示六自由度三菱RV-E2的機械臂運動規(guī)劃方案。圖8（a）顯示了三維視圖六自由度機械手，在一個人為的溫室環(huán)境。再次，目標(biāo)是從路徑中的位置移動機器人的工具中心點到黃瓜掛背后的黃瓜干，沒有擊中黃瓜TEMS代表由黑職位。 圖7.黃瓜采摘在一個人為的溫室環(huán)境經(jīng)營度自由操縱的無碰撞運動規(guī)劃：（a）開始姿勢（直）和目標(biāo)姿態(tài)與機械臂的工作空間冠捷挑選黃瓜掛灰色正方形代表;（b）與代表的黑色區(qū)域配置中的碰撞和S的起點和目標(biāo)配置，分別代表?配置空間;（c）配置空間由A采樣黃瓜干背后*算法在從一開始向前搜索到目標(biāo)節(jié)點;（d）通過配置空間的無碰撞軌跡;（e）6，到操盤黃瓜的無碰撞運動的快照;（f）配置A *算法在空間采樣，從向后搜索目標(biāo)的起始節(jié)點1和2是第一和第二關(guān)節(jié)的旋轉(zhuǎn)。 6.1．結(jié)果 由于這個例子涉及一個六自由度機械手，執(zhí)行搜索，在六維的配置空間。這是不可能的可視化配置空間的無碰撞點的運動，是與前面的例子一樣。因此，只有通過工作區(qū)的無碰撞運動的快照圖。 8（一） - （F）。該議案涉及所有6個旋轉(zhuǎn)關(guān)節(jié)。從本質(zhì)上講，黃瓜的議案，由兩部分組成。首先所有機器人向后傾斜，同時圍繞主垂直軸旋轉(zhuǎn)，然后傾斜前鋒再次攜帶刀具中心點之間的黃瓜莖。其次，同時，過去三年關(guān)節(jié)旋轉(zhuǎn)，以便能夠定位在背后的黃瓜干黃瓜工具中心點。這樣做，黃瓜干規(guī)避。 6.2．討論 結(jié)果表明，碰撞自由運動的六自由度機械手可以發(fā)現(xiàn)。據(jù)預(yù)計，這一結(jié)果可以擴展到七個自由度的機械手，在黃瓜采摘設(shè)備使用。然而，這個例子揭示了A *算法的弱點。對于正在審議的六自由度機械手，在六維的配置空間進(jìn)行搜索。然后，由于網(wǎng)格點的大量的，必須進(jìn)行評估，搜索變得過于緩慢。這部分是由于在MATLAB實現(xiàn)。該軟件包不是很有效時，必須執(zhí)行大量的迭代。再次，結(jié)果表明：在運動軌跡的尖角。當(dāng)需要高速運動，這些運動軌跡要平滑，以防止上機械臂鏈接的重載。 黃瓜采摘機器人 圖8.（a）-（f）：六快照的無碰撞運動6自由度RV-E2的操縱掛在黃瓜背后黃瓜莖代表黑色垂直職位 7.結(jié)論 本文提出了一種方法，以達(dá)到適當(dāng)?shù)氖盅蹍f(xié)調(diào)的黃瓜收獲機器人在農(nóng)業(yè)和環(huán)境工程研究所（IMAG BV）的開發(fā)。本文提出了一個方案，是能夠生成機器人無碰撞運動。一些數(shù)值例子說明了該方法和分析。 本研究的主要結(jié)論是，無碰撞運動可以計算六度自由度（DOF），RV-E2的機械臂在收獲機使用。據(jù)預(yù)計，這些結(jié)果可以擴展到七自由度機械手，即RV-E2的操縱器線性滑軌安裝。被發(fā)現(xiàn)的A*搜索算法很容易實現(xiàn)和強大的。通過這種方式，它提供了很多有識之士為機器人運動規(guī)劃的具體問題。此外，該算法的一個大優(yōu)勢是，它可以產(chǎn)生一個解決方案或停止時，無法找到一個解決方案。該財產(chǎn)的完整性，但是，使得算法望而卻步緩慢。結(jié)果發(fā)現(xiàn)，與本文中所描述的算法涉及的多自由度機械手運動軌跡的計算是計算非常。至符合所需的周期時間的10秒為一個單一的收獲行動，需要進(jìn)一步研究，以減少議案所需的計算時間規(guī)劃。研究，可沿兩條線。首先，可以減少計算時間，通過使用特殊的計算機硬件，例如并行處理器。另外，同時，減少計算可以通過使用更快和有效地實現(xiàn)的算法。此外，結(jié)果表明，該算法不包括許多情報。雖然它試圖產(chǎn)生定向運動的目標(biāo)，如果它只是配置遇到障礙樣品中的搜索空間網(wǎng)格解決方案，直到發(fā)現(xiàn)不使用有關(guān)的問題，特別是結(jié)構(gòu)的信息點。因此，進(jìn)一步研究需要獲得快速算法，有效地利用有關(guān)的問題，特別是結(jié)構(gòu)的信息，不卡，恕不另行通知。 致謝 這項工作是由荷蘭農(nóng)業(yè)，食品和漁業(yè)部的支持。匿名介紹人的建設(shè)性意見表示感謝。 參考文獻(xiàn) [1]Arima S; Kondo N (1999). Cucumber harvesting robot and plant training system. Journal of Robotics and Mechatro-nics, 11(3), 208–212 [2]Bontsema J; Van Kollenburg-Crisan L M; Van Henten E (1999). Automatic harvesting of vegetable fruits, Proceedings of the BRAIN International Symposium 2000 }Progressive Technologies in Agriculture and Environmen towards 21 Century, November 24, 1999, IAM-BRAIN Omiya, Japan, pp 44–51 [3]Boyse J W (1979). Interference detection among solids and surfaces. Communications of the ACM, 22(1), 3–9 [4]Craig J J(1989). Introduction to Robotics. Addison-Wesley,Reading, MA, USA [5]Gieling Th H; Van Henten E J; Van Os E A; Sakaue O;Hendrix A T M (1996). Conditions, demands and technol-ogy for automatic harvesting of fruit vegetables. ActaHorticulturae,440, 360–365 [6] Hayashi S; Sakaue O (1996). Tomato harvesting by robotic system. ASAE Annual International Meeting, Phoenix, Arizona, USA, ASAE Paper No. 96-3067 [7]Herman M (1986). Fast, three-dimensional, collision-free motion planning. Proceedings of the IEEE International Conference on Robotics and Automation, San Francisco,CA, USA, pp 1056–1063 [8] Hwang Y K; Ahuja N (1992). Gross motion planning}a survey. ACM Computing Surveys, 24(3), 219–291 [9] Kondo K (1991). Motion planning with six degrees of freedom by multistrategic bidirectional heuristic free-space enumera-tion. IEEE Transactions on Robotics and Automation, 7(3),267–277 [10] Kondo N; Monta M; Fujiura T(1996). Fruit harvesting robots in Japan. Advances in Space Research, 18(1/2), 181–184 [11] Latombe J C (1991). Robot Motion Planning. Kluwer Academic Publishers, Boston, USA [12] Meuleman J; Van Heulen S F; Kornet J G; Peters D G(2000). Image analysis for robot harvesting of cucumbers. AgEng 2000, Agricultural Engineering International Conference, Warwick, UK, EurAgEng Paper No. 00-AE-003 [13] Pearl J (1984).Heuristics.Intelligent Search Strategies for Com-puter Problem Solving. Addision-Wesley, Reading, MA, USA [14] Russell S; Norvig P (1995). Artificial Intelligence }A mode Approach. Prentice-Hall, Englewood Cliffs, NJ, USA [15] Schenk E J(2000). Modelvorming, voorwaartse kinematica, inverse kinematica met botsingsdetectie en padplanning van een 7 DOF manipulator systeem voor het automatisch oogsten van komkommers. [Modelling, forward kinematics, inverse kinematics with collision detection and motion planning of a 7 DOF manipulator system used for cucumber harvesting]. IMAG, Wageningen, The Netherlands, IMAG Report V2000-77 [16] Van Dijk G(1999). Modelvorming en padplanning van een 6 DOF manipulator voor het oogsten van komkommers. [Modelling and motionplanning of a 6 DOF manipulator used for cucumber harvesting.] IMAG, Wageningen, The Netherlands, IMAG Report V99-04 [17] Van Kollenburg-Crisan L M; Wennekes P; Werkhoven C (1997). Development of a mechatronic system for automatic harvesting of cucumbers. In: Proceedings of BIO-RO-BOTICS 97, The International Workshop on Robotics and Automated Machinery for Bio-productions, Valencia, Spain, pp 143–148 Biosystems Engineering (2003) 86(2), 135144doi:10.1016/S1537-5110(03)00133-8Available online at AEAutomation and Emerging TechnologiesCollision-free Motion Planning for a Cucumber Picking RobotE.J. Van Henten; J. Hemming; B.A.J. Van Tuijl; J.G. Kornet; J. BontsemaDepartment of Greenhouse Engineering, Institute of Agricultural and Environmental Engineering (IMAG B.V.), P.O. Box 43, NL-6700 AAWageningen, The Netherlands; e-mail of corresponding author: eldert.vanhentenwur.nl(Received 26 April 2002; accepted in revised form 8 July 2003; published online 29 August 2003)One of the most challenging aspects of the development, at the Institute of Agricultural and EnvironmentalEngineering (IMAG B.V.), of an automatic harvesting machine for cucumbers was to achieve a fast andaccurate eyehand co-ordination during the picking operation. This paper presents a procedure developed forthe cucumber harvesting robot to pursue this objective. The procedure contains two main components. Firstof all acquisition of sensory information about the working environment of the robot and, secondly, aprogram to generate collision-free manipulator motions to direct the end-effector to and from the cucumber.This paper elaborates on the latter. Collision-free manipulator motions were generated with a so-called pathsearch algorithm. In this research the A*-search algorithm was used. With some numerical examples the searchprocedure is illustrated and analysed in view of application to cucumber harvesting. It is concluded thatcollision-free motions can be calculated for the seven degrees-of-freedom manipulator used in the cucumberpicking device. The A*-search algorithm is easy to implement and robust. This algorithm either produces asolution or stops when a solution cannot be found. This favourable property, however, makes the algorithmprohibitively slow. The results showed that the algorithm does not include much intelligence in the searchprocedure. It is concluded that to meet the required 10s for a single harvest cycle, further research is needed tofind fast algorithms that produce solutions using as much information about the particular structure of theproblem as possible and give a clear message if such a solution can not be found.# 2003 Silsoe Research Institute. All rights reservedPublished by Elsevier Ltd1. IntroductionIn 1996, the Institute of Agricultural and Environ-mental Engineering (IMAG B.V.) began research on thedevelopment of an autonomous cucumber harvestingrobot supported by the Dutch Ministry of Agriculture,Food and Fishery (Gieling et al., 1996; Van Kollenburg-Crisan et al., 1997). The task of designing robots foragricultural applications raises issues not encountered inother industries. The robot has to operate in a highlyunstructured environment in which no two scenes arethe same. Both crop and fruit are prone to mechanicaldamage and should be handled with care. The robot hasto operate under adverse climatic conditions, such ashigh relative humidity and temperature as well aschanging light conditions. Finally, to be cost effective,the robot needs to meet high performance characteristicsin terms of speed and success rate of the pickingoperation. In this project, these challenging issues havebeen tackled by an interdisciplinary approach in whichmechanical engineering, sensor technology (computervision), systems and control engineering, electronics,software engineering, logistics, and, last but not least,horticultural engineering partake (Van Kollenburg-Crisan et al., 1997; Bontsema et al., 1999; Meulemanet al., 2000).One of the most challenging aspects of the develop-ment of an automatic harvesting machine is to achieve afast and accurate eyehand co-ordination, i.e. to achievean effective interplay between sensory informationacquisition and robot motion control during the pickingoperation, just like people do. In horticultural practice,a trained worker needs only 36s to pick and store asingle fruit and that performance is hard to beat.Fortunately, in terms of picking speed a roboticharvester does not have to achieve such high perfor-mance characteristics. A task analysis revealed that, foreconomic feasibility, a single harvest operation may takeARTICLE IN PRESS1537-5110/$30.00135# 2003 Silsoe Research Institute. All rights reservedPublished by Elsevier Ltdup to 10s (Bontsema et al., 1999). Still, robot motionsshould be as fast as possible while preventing collisionsof the manipulator, end-effector and harvested fruit withthe crop, the greenhouse construction and the robot itself(such as the vehicle and vision system). In a Dutchcucumber production facility, the robot operates in avery tight working environment. Finally, to assure thequality of the harvested fruit, constraints have to beimposed on the travelling speed and accelerations of themanipulator during various portions of the motion path.To achieve the desired eyehand co-ordination, oneneeds (real-time) acquisition of sensory information ofthe environment as well as algorithms to calculatecollision-free motions for the manipulator. In thisproject, the sensory system is based on computer vision,as reported by Meuleman et al. (2000). This paperfocuses on the fast generation of collision-free motiontrajectories for the manipulator of the picking machine.This issue has not received much attention in agricultur-al engineering research despite the fact that considerableresearch effort has been spent on automatic harvestingof vegetable fruits (see e.g. Kondo et al., 1996; Hayashi& Sakaue, 1996; Arima & Kondo, 1999).The paper is outlined as follows. In Section 2, theharvesting robot is described. In Section 3, a tasksequence for a single harvest operation is presented.Then Section 4 presents the components of an automaticalgorithm for collision-free motion planning. To obtaininsight into the operation of the algorithm, in Section 5,the approach is illustrated on a two-degrees-of-freedom(DOF) manipulator. Section 6 contains results of amotion planning experiment with the six-DOF RV-E2Mitsubishi manipulator used in the harvest robot.Finally, Section 7 contains concluding remarks andsuggestions for future research.2. The harvesting robotIn Fig. 1 a functional model of the harvesting robot isshown. It consists of an autonomous vehicle used forcoarse positioning of the harvesting machine in the aislesof the greenhouse. This vehicle uses the heating pipes asa rail for guidance and support. It serves as a mobileplatform for carrying power supplies, a pneumaticpump, various electronic hardware for data-acquisitionand control, a wide-angle camera system for detectionand localisation of cucumbers in the crop and a seven-DOF manipulator for positioning of the end-effector.The manipulator consists of a linear slide on top ofwhich a six-DOF Mitsubishi RV-E2 manipulator ismounted. The RV-E2 manipulator includes an anthro-pomorphic arm and a spherical wrist. The manipulatorhas a steady-state accuracy of ?0?2mm and meetsgeneral requirements with respect to hygiene and theoperation under adverse greenhouse climate conditions(high relative humidity and high temperature). Themanipulator carries an end-effector that contains twoparts: a gripper to grasp the fruit and a cutting device toseparate the fruit from the plant. The end-effectorcarries a laser ranging system or a small camera. Theyare used to obtain sensory information for fine motioncontrol of the end-effector in the neighbourhood of thecucumber, if needed.3. Task sequence of a single harvest operationA task sequence of a single harvest operation ispresented in Fig. 2. Approaching the cucumber duringthe picking operation is considered to be a two-stageprocess. First, with the camera system mounted on thevehicle, the cucumber fruit is detected, its ripeness isassessed and its location is determined. In case it isARTICLE IN PRESS(b)(c)(d)(i) (a) (f)(g)(h)(e)Fig. 1. A functional model of the cucumber harvest robot; (a)vehicle; (b) wide angle camera; (c) seven-degrees-of-freedommanipulator; (d) end-effector; (e) laser ranger and position ofcamera for local imaging; (f) computer and electronics; (g) reelwith 220V power line; (h) pneumatic pump; (i) heating pipeNotationctransition costs between two nodesfcost functiongcost of the motion path from node S to thecurrent nodeGgoal nodehoptimistic estimate of the cost to go to thegoal from the current nodennoden0successor of nodeSstart nodeE.J. VAN HENTEN ET AL.136decided to pick the cucumber, the low-resolution imagesof the vehicle-mounted camera are used for positioningthe end-effector in the neighbourhood of the cucumber.Once the end-effector has arrived in the neighbourhoodof the cucumber, then, using the laser ranging system orcamera system mounted on top of the end-effector, high-resolution information of the local environment of thecucumber is obtained for the final accurate approach ofthe cucumber. The end-effector grips and cuts the stalkof the fruit. The gripper fixes the detached fruit andfinally the harvested fruit is moved to the storage crate.Obstacle avoidance motion planning will be used bothfor the initial approach of the cucumber as well as thereturn journey of the harvested cucumber to the crate, toassure that other objects in the work space such as therobot vehicle itself but also stems and, if present, leavesand parts of the greenhouse construction are not hit.Clearly, the harvested cucumber increases the size ofthe end-effector, which should be considered during thereturn motion of the manipulator to the storage. Theaverage length of a cucumber is 300mm.4. A collision-free motion planning algorithmFigure 3 illustrates the components of a program thatautomatically generates collision-free motions for thecucumber picking robot based on the work of Herman(1986). Collision-free motion planning relies on three-dimensional(3D)informationaboutthephysicalstructure of the robot as well as the workspace in whichthe robot has to operate. So, the first step in collision-free robot motion planning is the 3D world descriptionacquisition.Thisdescriptionisbasedonsensoryinformation such as machine vision as well as a prioriknowledgeabout,forinstance,the3Dkinematicstructure of the harvesting robot, e.g. 3D models,contained in a database. With this information, duringthe task definition phase, the overall task of the robot isplanned. It is decided which final position and orienta-tion of the end-effector result in the best approach of thecucumber. Also specific position and orientation con-straints are defined during this phase. In the inversekinematics phase the goal position and orientation of theend-effector, defined during task definition, are trans-lated into the goal configuration of the manipulator.The goal configuration is represented as a combinationof a translation of the linear slide and six rotations ofthe joints of the seven-DOF manipulator. This informa-tion is used by the path planner. The path planneremploys a search technique to find a collision-free pathfrom the start configuration of the manipulator to itsgoal configuration. Once the collision-free path planninghas been completed successfully, the trajectory plannerARTICLE IN PRESSInitialise allsystemsMove vehicledelta x furtheron the railTake stereoimagesImageprocessing(fruit detection)Camera at endposition?Path planningMove TCP tocutting pointGrip fruit andcut stalkMove with fruitto the crate andrelease itMove TCP tohome positionHarvestcompletedMove vehicle tohome positionyesMove globalcamera to 1stpositionMove globalcamera oneposition furthernoyesnoyesyesnoyesno3D localisationnoMove TCP closeto cutting pointMini camerastereo imagesImage processing(high res. 3Dlocalisation)Fruit(s) detected?Vehicle at endof rail?Other fruit inglobal image?Fruit mature?Fig. 2. Task sequence of a single harvest operation: 3D, three dimensional; TCP, tool-centre-pointCUCUMBER PICKING ROBOT137converts the collision-free path into a trajectory that canbe executed by the manipulator. Typically, the pathplanning process is concerned only with collision-freeconfigurations in space, but not with velocity, accelera-tion and smoothness of motion. The trajectory plannerdeals with these factors. The trajectory planner producesthe motion commands for the servomechanisms of therobot.Thesecommandsareexecutedduringtheimplementation phase.Some components of the motion planning system willbe described hereafter in more detail.4.1. World description (acquisition)The machine vision based world description acquisi-tion for the cucumber picking robot is described in apaper by Meuleman et al. (2000). The vision system isable to detect green cucumbers within a green canopy.Moreover, the vision system determines the ripeness ofthe cucumber. And finally, using stereovision techni-ques, the camera vision system produces 3D maps of theworkspace within the viewing angle of the camera. Inthis way the robot is able to deal with the variability inthe working environment with which it is confronted.As stated above, also a priori knowledge about, forinstance, the physical structure of the robot is needed forcollision-free motion planning. As an example, Fig. 4shows a 3D model of the six-DOF Mitsubishi RV-E2manipulator implemented in MATLAB1. The 3Dstructure of the manipulator is represented by polygonsconstructed of rectangles and triangles. The model isused for evaluation of motion strategies during simula-tions and serves as a basis for the detection of collisionsof the manipulator with structural components in theworkspace of the robot during motion planning.4.2. Inverse kinematicsThe inverse manipulator kinematics deal with thecomputation of the set of joint angles and translationsthat result in the desired position and orientation of thetool-centre-point (TCP) of the manipulator (Craig,1989). The TCP is a pre-defined point on the end-effector. For the six-DOF Mitsubishi RV-E2 manip-ulator Van Dijk (1999) obtained an analytic solution ofthe inverse manipulator kinematics. For the seven-DOFmanipulator, i.e. the Mitsubishi RV-E2 manipulatormounted on a linear slide, a straightforward analyticsolution of the inverse kinematics does not exist due totheinherentredundancyinthekinematicchain.Recently a mixed analytic-numerical solution of theARTICLE IN PRESS1000800600400200050050050050000X plane, mmY plane, mmZ plane, mmFig. 4. A three-dimensional model of the six-degrees-of-freedomMitsubishi RV-E2 manipulatorStartWorld descriptionacquisitionInversekinematicsPath planningTrajectoryplanningImplementationEndData baseTask definitionFig. 3. A program for automatic generation of collision-freemotionsE.J. VAN HENTEN ET AL.138inverse kinematics of this redundant manipulator wasobtained (Schenk, 2000). Given the position of the ripecucumber,thealgorithmproducesacollision-freeharvest configuration of the seven-DOF manipulator.Also, it assures that the joints have sufficient freedom forfine-motioncontrolintheneighbourhoodofthecucumber.4.3. Path plannerAlgorithms for collision-free path planning have beenthe object of much research. See e.g. Latombe (1991)and Hwang and Ahuja (1992) for an overview.A collision-free path planner essentially consists oftwo important components: a search algorithm and acollision detection algorithm. The search algorithmexplores the search space for a feasible, i.e. collision-free, motion from a start point to a goal point. Duringthe search, the feasibility of each step in the search spaceis checked by the collision detection algorithm. Thisalgorithm checks for collisions of the manipulator withother structural components in the workspace of therobot.It is important to note that for most path planners thesearch space is the so-called configuration space of therobot, which crucially differs from the 3D workspace ofthe robot. In case of the seven-DOF manipulator of thecucumber harvest machine, the configuration space is aseven-dimensional space spanned by the combination ofone joint translation and six joint rotations. Then, thesearch for a collision-free motion from a start positionand orientation of the tool-centre-point to the goalposition and orientation in the 3D workspace boilsdown to a search for a collision-free motion of a singlepointthroughtheseven-dimensionalconfigurationspace from the start configuration to the goal config-uration. In this way problems with redundancy in thekinematic chain are easily circumvented. There is a one-to-one mapping of a point in the configuration space toa position and orientation of the tool-centre-point in theworkspace.However,formostmanipulators,theopposite does not hold. Then a single position andorientation of the tool-centre-point in the workspace canbe reproduced by several configurations of the manip-ulator. Due to its unique representation a search in theconfiguration space is preferred. For collision detection,however, one needs to describe the physical posture ofthe manipulator in relation with other objects in the 3Dworkspace. Because every configuration represents asingle posture of the manipulator in the 3D workspace,collisionscanbeeasilyverified.Then,giventheparticular kinematic structure of the robot, the work-space obstacles can be mapped into configuration spaceobstacles as will be shown later.4.3.1. The search algorithmA path search algorithm should be efficient and find asolution if one exists. The latter property is referred to ascompleteness (Pearl, 1984). Usually, algorithms thatguarantee completeness are not computationally effi-cient. Computational efficiency, however, is crucialwhen on-line application is required. To obtain insightinto the various aspects of motion planning, in thisresearch, completeness of the algorithm was favouredabove computational efficiency. The main reason forthat choice is that a complete algorithm will either findthe solution or stop using a clearly defined stoppingcriterion if a solution cannot be found. This is not truefor algorithms that do not assure completeness. Theyeither supply a solution or get stuck without furthernotice. In this research the so-called A*-search algorithmwas used (Pearl, 1984; Kondo, 1991; Russell & Norvig,1995). It is easy to implement and guarantees complete-ness. Moreover, it minimises a cost criterion thatincludes a measure for the distance travelled in thesearchspace.ThealgorithmwasimplementedinMATLAB1.To use the A*algorithm for motion planning, theconfiguration space of the robot is discretised using afixed grid structure as shown in Fig. 5. The user candefine both the size and resolution of the grid. Then theA*algorithm searches a path from the start grid point tothe goal grid point while minimising a cost function f:This cost function f includes the cost of the path so farg; and an optimistic estimate of the cost from the currentposition to the goal h: In this research, the Euler normwas used as an optimistic estimate of the cost to go tothe goal node. The A*algorithm is both complete andoptimal. Optimality assures that the path obtainedminimises the cost function used.ARTICLE IN PRESSSGStartconfigurationGoal configurationTranslation or rotation of joint 2Translation or rotation of joint 1Fig. 5. Orthogonal node expansion in a discretised two-dimen-sional configuration space: S; start node; G; goal nodeCUCUMBER PICKING ROBOT139The A*algorithm uses two lists with grid nodes, theOPEN list and the CLOSED list. The OPEN listcontains grid nodes of which the cost function has notyet been evaluated, whereas function values of the gridnodes on the CLOSED list have been evaluated. It isassumed that the start and goal configuration coincidewith grid nodes or that grid nodes in the closeneighbourhood of these configurations can be selected.Then according to Pearl (1984), the A*algorithmmanipulates the nodes in the grid as follows.(1) Put the start node S on OPEN.(2) If OPEN is empty then exit with failure, else removefrom OPEN and place on CLOSED a node n forwhich f is a minimum.(3) If n is equal to the goal node G; exit successfully withthe soluti