喜歡就充值下載吧。。資源目錄里展示的文件全都有，，請(qǐng)放心下載，，有疑問咨詢QQ:414951605或者1304139763 ======================== 喜歡就充值下載吧。。資源目錄里展示的文件全都有，，請(qǐng)放心下載，，有疑問咨詢QQ:414951605或者1304139763 ======================== 濰坊學(xué)院本科畢業(yè)設(shè)計(jì) 生物系統(tǒng)工程（2003）86（2）135-144 DOI：10.1016/S1537-5110（03）00133-8 AE—自動(dòng)化與新興技術(shù) 黃瓜采摘機(jī)器人的無碰撞規(guī)劃 E.J.凡Henten J.海明; B.A.J.凡Tuijl; J.G.短號(hào);研究Bontsema 溫室工程，農(nóng)業(yè)和環(huán)境工程研究所（IMAG BV公司），箱43，NL-6700機(jī)管局瓦赫寧根，荷蘭;電子郵件通訊作者：eldert.vanhenten wur.nl （2002年4月26日收到，2003年7月8號(hào)以修訂后的形式接受; 2003年8月29日在網(wǎng)上發(fā)表） 在農(nóng)業(yè)和環(huán)境工程學(xué)院，對(duì)于黃瓜自動(dòng)收獲機(jī)，其中最大的一個(gè)挑戰(zhàn)方面就是在采摘的過程中實(shí)現(xiàn)一種快速精確的手眼協(xié)調(diào)的操作。這個(gè)程序包含兩個(gè)主要的組成部分。首先，采集信息機(jī)器人的工作環(huán)境，其次，一個(gè)程序可以讓機(jī)器人末端執(zhí)行器對(duì)黃瓜產(chǎn)生無碰撞機(jī)械運(yùn)動(dòng)。這篇文章主要闡述了后者，無碰撞機(jī)械運(yùn)動(dòng)所產(chǎn)生的所謂的路徑搜索算法。在這項(xiàng)研究中這個(gè)A-search算法被應(yīng)用著，用一些數(shù)值的例子對(duì)黃瓜收割應(yīng)用的搜索過程分析說明。得出的結(jié)論是，無碰撞運(yùn)動(dòng)可以用于采摘黃瓜的機(jī)械手的自由度的計(jì)算。這個(gè)A-search算法非常易于實(shí)施和魯棒。當(dāng)找不到解決方案時(shí)這個(gè)算法要不產(chǎn)生一個(gè)解決方案要不就停止工作。這個(gè)有利的財(cái)產(chǎn)然而卻使算法過分的緩慢，結(jié)果表明這個(gè)算法不包括多智能的搜索過程。我們可以知道，為了滿足每10S為一個(gè)單一收獲循環(huán)的要求，還需要做進(jìn)一步的研究，去尋找發(fā)現(xiàn)快速的算法，使用盡可能多的關(guān)于這個(gè)問題特定結(jié)構(gòu)的信息來產(chǎn)生解決方案，如果這個(gè)算法找不到解決方案并能給出明確的信息。 1. 介紹 1996年，農(nóng)業(yè)和環(huán)境工程學(xué)院開始研究自主的黃瓜采摘機(jī)器人的發(fā)展，這個(gè)項(xiàng)目是由荷蘭農(nóng)業(yè)部，食品和漁業(yè)部門支持的。為農(nóng)業(yè)應(yīng)用設(shè)計(jì)機(jī)器人的任務(wù)所提出的議題不涉及其他行業(yè)(Gielinget al., 1996 ; Van Kollenburg-）。機(jī)器人必須處在一個(gè)高度非結(jié)構(gòu)化環(huán)境中，在這里沒有兩個(gè)場(chǎng)景是一模一樣的。農(nóng)作物和水果都易于被機(jī)械損傷應(yīng)給小心處理。機(jī)器必須能夠在不利的條件下運(yùn)轉(zhuǎn)，如相對(duì)較高的溫度和濕度以及光線變化的條件。最后，為了符合成本效益，就機(jī)器人采摘運(yùn)動(dòng)的速度和成功率而言，機(jī)器人需要滿足高的性能特點(diǎn)。在這個(gè)項(xiàng)目中這些具有挑戰(zhàn)性的問題已經(jīng)被一個(gè)機(jī)械工程，傳感技術(shù)（計(jì)算機(jī)視覺等），系統(tǒng)和控制工程，電子、軟件工程，物流，最后但不是最少園藝工程分享的互動(dòng)的方式解決(Van Kollenburg-Crisan et al., 1997 ; Bontsema et al., 1999 ; Meuleman et al., 2000 )。 自動(dòng)收割機(jī)的開發(fā)研制中最具有挑戰(zhàn)性的問題之一就是達(dá)到快速精確的手眼協(xié)調(diào)的，即達(dá)到機(jī)器人在采摘運(yùn)動(dòng)中感官信息的采集和機(jī)器人運(yùn)動(dòng)控制之間的有效相互作用，就像人們做的那樣。在園藝實(shí)踐中，一個(gè)訓(xùn)練有素的工人只需要3-6S采摘和存儲(chǔ)一個(gè)水果，那種表現(xiàn)是很難被打敗的。幸運(yùn)的是，就機(jī)器人的采摘速度而言沒有必要達(dá)到那么高的性能特點(diǎn)。一項(xiàng)任務(wù)分析顯示，考慮經(jīng)濟(jì)可行性，一個(gè)單一采摘運(yùn)動(dòng)可能只需要10S (Bontsemaet al., 1999 )。仍然，機(jī)器人運(yùn)動(dòng)應(yīng)盡可能快的同時(shí)防止機(jī)器手的碰撞，手和收獲水果作物，溫室結(jié)構(gòu)還有機(jī)器人自身的碰撞（如汽車視覺系統(tǒng)）。在荷蘭，黃瓜生產(chǎn)設(shè)施，機(jī)器人運(yùn)行在一個(gè)非常緊張的工作環(huán)境中。最后，為了保證收獲果實(shí)的質(zhì)量，在運(yùn)動(dòng)路徑的各個(gè)部分對(duì)機(jī)械手的速度和加速度加以約束。 為了達(dá)到理想的手眼協(xié)調(diào)，一個(gè)人需要環(huán)境的感官信息的采集和算法去為機(jī)械手計(jì)算這種無碰撞運(yùn)動(dòng)。正像Meuleman et al. (2000) 報(bào)道的那樣。在這個(gè)項(xiàng)目中感覺系統(tǒng)是基于計(jì)算機(jī)視覺的。本文著重論述了收獲機(jī)的機(jī)械手的無碰撞運(yùn)動(dòng)軌跡的快速生成。盡管有相當(dāng)大的研究工作花在自動(dòng)收集蔬菜水果方面，但是這個(gè)問題在農(nóng)業(yè)工程研究中沒有引起人們極大的關(guān)注。(see e.g. Kondoet al., 1996 ; Hayashi& Sakaue, 1996 ; Arima & Kondo, 1999 )。 本文概述如下，在第二節(jié)對(duì)采摘機(jī)器人進(jìn)行了闡述，在第三節(jié)，講述的是一個(gè)單一收獲操作的任務(wù)序列，然后，第四節(jié)，表述的是無碰撞規(guī)劃的自動(dòng)算法的組成。為了能夠深入洞察算法的運(yùn)行，在第五節(jié)對(duì)該算法在第二級(jí)自由度的機(jī)械手上進(jìn)行了解釋說明，第六節(jié)包含一個(gè)應(yīng)用于收獲機(jī)器人身上的six-DOF RV-E2三菱機(jī)械手的運(yùn)動(dòng)規(guī)劃實(shí)驗(yàn)結(jié)果。第七節(jié)包含結(jié)束語(yǔ)和對(duì)未來研究的建議。 2．采摘機(jī)器人 圖1.黃瓜收獲機(jī)器人的功能模型;（a）車輛;（b）廣角相機(jī);（c）七度的自由度機(jī)械手;（d）最終效應(yīng);（e）激光測(cè)距儀和攝像機(jī)的位置當(dāng)?shù)爻上?（f）計(jì)算機(jī)和電子產(chǎn)品;（g）與220伏電源線卷軸;（h）氣動(dòng)泵;（i）供熱管 圖一中，一個(gè)采摘機(jī)器人的功能模型被展示出來。它包含一個(gè)用于溫室走道里的收獲機(jī)進(jìn)行粗定位的自主車輛。這車采用加熱管作為一個(gè)鐵路進(jìn)行指導(dǎo)和支持。它作為一個(gè)移動(dòng)平臺(tái)裝載電源、主動(dòng)泵、各種數(shù)據(jù)收集和控制的電子硬件、一個(gè)用于監(jiān)測(cè)和定位植物上黃瓜位置的廣角攝像系統(tǒng)和一個(gè)用于機(jī)械末端運(yùn)行器定位的七個(gè)自由度的機(jī)械手。這個(gè)機(jī)械手由安裝著六個(gè)自由度的Mitsubishi RV-E2機(jī)械手的滑動(dòng)線路構(gòu)成。這個(gè)RV-E2機(jī)械手包括一個(gè)人形的機(jī)械手臂和球形的手腕。這個(gè)機(jī)械手有個(gè)能夠抓去0.2毫米的穩(wěn)態(tài)精度并能夠在惡劣的溫室氣候（高濕度和高溫度）條件下滿足一般的衛(wèi)生的操作方面的要求。這個(gè)機(jī)械手裝有一個(gè)末端執(zhí)行器。它包括兩部分：一個(gè)爪抓住水果，另一個(gè)爪切割水果從植物上分離出來。這個(gè)末端執(zhí)行器帶有一個(gè)末端激光測(cè)距系統(tǒng)或一個(gè)小相機(jī)。他們是用來在黃瓜附近能夠更好地進(jìn)行運(yùn)動(dòng)控制而獲取感官信息的，如果需要的話。 3.單一收割運(yùn)動(dòng)的任務(wù)序列 圖2. 一個(gè)單一的收獲作業(yè)任務(wù)序列：3D，三維，TCP，工具中心點(diǎn) 圖二展示的是一個(gè)單一的收獲運(yùn)動(dòng)的一個(gè)任務(wù)序列。在采摘操作中接近黃瓜被公認(rèn)為是一個(gè)兩階段的過程。首先，用安裝在車輛上的攝像系統(tǒng)，黃瓜果實(shí)被檢測(cè)到他的成熟認(rèn)定和位置是不確定的。如果我們決定采摘黃瓜則低分辨率圖像的車載攝像機(jī)就用于定位機(jī)器人末端執(zhí)行器鄰近黃瓜附近這一帶。一旦末端執(zhí)行器抵達(dá)鄰近的黃瓜，然后利用末端執(zhí)行器上面的激光測(cè)距系統(tǒng)或攝像系統(tǒng)為最終的準(zhǔn)確的接近黃瓜獲得黃瓜定位環(huán)境的高分辨率的信息。末端執(zhí)行器緊握并消減果子的莖。夾持固定分離的水果最后收獲果實(shí)移動(dòng)到存儲(chǔ)箱。 避障運(yùn)動(dòng)規(guī)劃將用于黃瓜的初步做法以及收獲黃瓜回程箱子，來保證，如機(jī)器人車輛本身的工作空間中的其他對(duì)象，但也源于，如果目前，葉片和溫室建設(shè)的部分都沒有命中。顯然，收獲的黃瓜，增加最終的效應(yīng)，應(yīng)考慮在機(jī)械臂返回到存儲(chǔ)議案的大小。黃瓜的平均長(zhǎng)度為300mm。 4.一個(gè)無碰撞運(yùn)動(dòng)規(guī)劃算法 圖3.無碰撞的自動(dòng)生成程序議案 圖3顯示了一個(gè)程序，自動(dòng)生成赫爾曼（1986年）的工作基礎(chǔ)上的黃瓜采摘機(jī)器人無碰撞運(yùn)動(dòng)的組成部分。無碰撞運(yùn)動(dòng)規(guī)劃依賴于三維（3D）機(jī)器人的物理結(jié)構(gòu)以及在機(jī)器人操作的工作區(qū)的信息。因此，在無碰撞機(jī)器人運(yùn)動(dòng)規(guī)劃的第一步是三維世界描述的收購(gòu)。這個(gè)描述是基于感官信息，如機(jī)器視覺以及先驗(yàn)知識(shí)，例如，采摘機(jī)器人運(yùn)動(dòng)學(xué)的三維結(jié)構(gòu)，如三維模型，在數(shù)據(jù)庫(kù)中。有了這個(gè)信息，在任務(wù)定義階段，機(jī)器人的整體任務(wù)的計(jì)劃。決定最后的位置和方向的效應(yīng)最終結(jié)果中的黃瓜最好的方法。也定義在此階段的具體位置和方向約束等。在階段目標(biāo)的位置和方向的最終任務(wù)定義中定義的效應(yīng)，逆運(yùn)動(dòng)學(xué)，將目標(biāo)配置的manipulator.The目標(biāo)配置跨lated表示作為一個(gè)線性滑軌的翻譯和6的組合七自由度機(jī)械手關(guān)節(jié)的旋轉(zhuǎn)。使用此信息的路徑規(guī)劃，路徑規(guī)劃，采用了搜索技術(shù)找到自由碰撞路徑，從開始操縱其目標(biāo)配置配置。一旦已成功完成的無碰撞路徑規(guī)劃，軌跡規(guī)劃軌跡，可以轉(zhuǎn)換成的無碰撞路徑由機(jī)器人執(zhí)行。通常情況下，路徑規(guī)劃過程中，只有在太空中的無碰撞配置有關(guān)，但沒有速度，加速度和運(yùn)動(dòng)平滑。軌跡規(guī)劃涉及這些因素。 thetrajectory策劃生產(chǎn)的機(jī)器人伺服系統(tǒng)的運(yùn)動(dòng)命令。在執(zhí)行階段執(zhí)行這些命令。運(yùn)動(dòng)規(guī)劃系統(tǒng)的一些部件將在更詳細(xì)地描述以下。 4.1世界的描述（采集） Meulemanet在一份文件中描述的基于機(jī)器視覺的世界描述收購(gòu)的黃瓜采摘機(jī)器人（2000年）。視覺系統(tǒng)能夠偵測(cè)在綠色canopy.Moreover綠色黃瓜，視覺系統(tǒng)決定的黃瓜成熟。最后，利用立體視覺技術(shù)QUES，相機(jī)視覺系統(tǒng)產(chǎn)生的工作空間內(nèi)的攝像頭的視角3D地圖。在這樣的機(jī)器人能夠處理工作面臨的環(huán)境與它的變異。 圖6. 自由度的三菱RV-E2的操縱一個(gè)三維模型 如上所述，先驗(yàn)知識(shí)，例如，機(jī)器人的物理結(jié)構(gòu)所需的無碰撞運(yùn)動(dòng)規(guī)劃。作為一個(gè)例子，圖4顯示了一個(gè)六自由度三菱RV-E2在MATLAB中實(shí)現(xiàn)機(jī)械臂的三維模型。機(jī)器人的三維結(jié)構(gòu)是由矩形和三角形構(gòu)造的多邊形表示。議案的戰(zhàn)略評(píng)估模型用于模擬期間，作為操縱機(jī)器人運(yùn)動(dòng)規(guī)劃期間的工作空間中的結(jié)構(gòu)部件的碰撞檢測(cè)的基礎(chǔ)上。 4.2逆運(yùn)動(dòng)學(xué) 逆機(jī)械臂運(yùn)動(dòng)學(xué)關(guān)節(jié)角度的計(jì)算和翻譯，處理結(jié)果在所需的位置和方向,工具中心點(diǎn)（TCP）機(jī)器人（克雷格，1989年）。 TCP是一個(gè)預(yù)定義的endeffector點(diǎn)。對(duì)于六自由度三菱RV-E2的操縱范戴克（1999年）獲得了逆機(jī)械臂運(yùn)動(dòng)學(xué)的解析解。七自由度機(jī)械手，即三菱RV-E2的機(jī)械臂安裝在一個(gè)線性滑軌，一個(gè)簡(jiǎn)單的逆運(yùn)動(dòng)學(xué)解析解不存在由于在運(yùn)動(dòng)鏈的固有冗余。最近獲得這種冗余機(jī)械臂的逆運(yùn)動(dòng)學(xué)分析數(shù)值混合溶液（申克，2000年）。由于成熟的黃瓜的立場(chǎng)，該算法產(chǎn)生的七自由度機(jī)械臂的無碰撞收獲配置。此外，它可以保證關(guān)節(jié)黃瓜附近的精細(xì)運(yùn)動(dòng)控制有足夠的自由。 4.3路徑規(guī)劃 無碰撞路徑規(guī)劃算法已被大量的研究對(duì)象。例如見latombe（1991）和黃和阿胡加（1992）概述。 一個(gè)無碰撞路徑規(guī)劃主要包括兩個(gè)重要組成部分：搜索算法和碰撞檢測(cè)算法。搜索算法的搜索空間探索一個(gè)可行的，即collisionfree，從起點(diǎn)到目標(biāo)點(diǎn)的議案。在搜查過程中，被選中的碰撞檢測(cè)算法在搜索空間的每一步的可行性。該算法檢查機(jī)器人的碰撞與機(jī)器人的工作空間中的其他結(jié)構(gòu)部件。重要的是要注意，對(duì)于大多數(shù)路徑規(guī)劃者的搜索空間是所謂的配置空間機(jī)器人，其中關(guān)鍵的是從不同的3D工作區(qū)機(jī)器人。在黃瓜收獲機(jī)的7自由度機(jī)械手的情況下，配置空間是由一個(gè)聯(lián)合翻譯和6個(gè)聯(lián)合旋轉(zhuǎn)組合橫跨七維空間。然后，從一開始的位置和方向的工具中心點(diǎn)為無碰撞運(yùn)動(dòng)目標(biāo)的位置和方向在三維工作空間癤的單點(diǎn)無碰撞通過的議案的搜索搜索七維配置從一開始就配置目標(biāo)配置掩膜的空間。在這樣的運(yùn)動(dòng)鏈中的冗余問題很容易規(guī)避。有一到一個(gè)映射的配置空間中的點(diǎn)的位置和方向，在工作區(qū)中的工具中心點(diǎn)。然而，對(duì)于大多數(shù)的機(jī)器人，相反不成立。一個(gè)單一的位置和方向，在工作區(qū)中的工具中心點(diǎn)，然后可以復(fù)制機(jī)器人的多種配置。由于其獨(dú)特的代表性配置空間搜索是首選。然而，碰撞檢測(cè)，需要說明的身體姿勢(shì)操縱在與其他物體在三維工作空間的關(guān)系。因?yàn)槊總€(gè)配置代表一個(gè)單一的姿勢(shì)在三維工作空間的機(jī)械臂，可以很容易地驗(yàn)證碰撞。然后，特別是機(jī)器人的運(yùn)動(dòng)結(jié)構(gòu)，工作空間的障礙可以被映射到配置空間的障礙將會(huì)顯示。 4.3.1.搜索算法 路徑搜索算法應(yīng)該是有效率的，如果存在的話，找到一個(gè)解決方案。后者的財(cái)產(chǎn)被稱為完整性（珍珠，1984年）。通常情況下，算法的完整性，保證不計(jì)算效率。然而，計(jì)算效率是至關(guān)重要的，當(dāng)上線的應(yīng)用程序需要。運(yùn)動(dòng)規(guī)劃的各個(gè)方面取得的洞察力，在這項(xiàng)研究中，上述計(jì)算效率的青睞，該算法的完整性。這樣的選擇的主要原因是一個(gè)完整的算法將找到解決辦法，或停止使用一個(gè)明確定義的停止準(zhǔn)則，如果不能找到一個(gè)解決方案。這是不是真實(shí)的，不保證完整性的算法。他們要么提供一個(gè)解決方案或卡住，恕不另行通知。在本研究中所謂的A *搜索算法（明珠，1984年;近藤，1991年，羅素和Norvig還，1995年）。它很容易實(shí)現(xiàn)和保證完整性。此外，它最大限度地降低成本標(biāo)準(zhǔn)，其中包括一個(gè)在搜索空間旅行距離的措施。該算法是在MATLABB實(shí)施 圖5.在離散化的二維配置空間的正交節(jié)點(diǎn)擴(kuò)展：S，起始節(jié)點(diǎn); G，目標(biāo)節(jié)點(diǎn) 使用配置空間機(jī)器人運(yùn)動(dòng)規(guī)劃的A *算法，離散化使用一個(gè)固定的電網(wǎng)結(jié)構(gòu)如圖5。用戶可以定義網(wǎng)格的大小和分辨率。然后A *算法搜索從一開始就格點(diǎn)的目標(biāo)格點(diǎn)的路徑，同時(shí)最大限度地降低成本函數(shù)f：此成本函數(shù)f包括路徑的成本遠(yuǎn)遠(yuǎn)?;和樂觀的估計(jì)成本從目前的位置目標(biāo)?：在這項(xiàng)研究中，歐拉規(guī)范被用來作為樂觀的估計(jì)到目標(biāo)節(jié)點(diǎn)的成本。A *算法是既完整和優(yōu)化。最優(yōu)保證的路徑獲得最大限度地減少使用成本函數(shù)。. A *算法使用兩個(gè)網(wǎng)格節(jié)點(diǎn)，開放列表和封閉列表清單。開放列表中包含了電網(wǎng)的成本函數(shù)，其中尚未被評(píng)估，而評(píng)估已閉合的名單上的網(wǎng)格節(jié)點(diǎn)的函數(shù)值的節(jié)點(diǎn)。這是假設(shè)的起點(diǎn)和目標(biāo)，可以選擇配置，配合網(wǎng)格節(jié)點(diǎn)或網(wǎng)格節(jié)點(diǎn)，在這些配置的密切鄰里。然后根據(jù)珍珠（1984），A *算法在網(wǎng)格如下操作節(jié)點(diǎn)。 (1)放在開放的起始節(jié)點(diǎn)S。 (2)如果打開是空的，則失敗退出，否則從關(guān)節(jié)點(diǎn)n FO其中f是最低的開放和地點(diǎn)。 (3)如果n等于目標(biāo)節(jié)點(diǎn)G;成功退出追溯從n指針為S得到的解決方案： (4)否則擴(kuò)大N;生成所有其繼承人，并重視它們的指針回到N：對(duì)于每一個(gè)n的繼任者n’： (a) 如果是尚未打開或關(guān)閉，估計(jì)H（n’）（樂觀的估計(jì)成本的最佳途徑，從n’到目標(biāo)節(jié)點(diǎn)G），并計(jì)算F（n’）= G（n’）+ H（n’）其中g(shù)（n’）= G×（N）+ C（N，n’）C（N，n’）從節(jié)點(diǎn)n的過渡成本，節(jié)點(diǎn)n’和G（S）= 0 （b）如果已經(jīng)打開或關(guān)閉，直接收益率最低的G（1）道路沿線的指針; (c)如發(fā)現(xiàn)閉，1所需的指針調(diào)整和重新打開它 (5)轉(zhuǎn)到第2步。 電網(wǎng)擴(kuò)張?jiān)诘?步，可以采取多種形式。在本研究中所謂的正交擴(kuò)充。這種方法是在圖5所示。 圖5還說明起始節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)沒有以配合實(shí)際的起點(diǎn)和目標(biāo)機(jī)器人的配置。在這種情況下，最近的鄰居節(jié)點(diǎn)被選中。 在這個(gè)算法，停止準(zhǔn)則是非常明確的規(guī)定。如果在第3步，從開放列表中刪除的節(jié)點(diǎn)等于目標(biāo)節(jié)點(diǎn)，算法停止。另外，該算法將停止在第2步如果所有的網(wǎng)格節(jié)點(diǎn)進(jìn)行評(píng)估，并開放列表已成為空。在這種情況下，沒有找到一個(gè)解決方案。 路徑搜索過程中碰撞檢測(cè)的處理有兩種方式。首先，碰撞的配置可以通過掃描整個(gè)離散化配置空間的路徑搜索前確定。這將是在一個(gè)高維離散化的空間配置，具有很高的情況下計(jì)算昂貴決議電網(wǎng)。這將是更有效地評(píng)估在搜索過程中的網(wǎng)格節(jié)點(diǎn)的可行性。也就是說，在節(jié)點(diǎn)擴(kuò)展一步，第4步，碰撞檢測(cè)算法檢查是否與該節(jié)點(diǎn)相關(guān)的機(jī)器人配置與環(huán)境或不產(chǎn)生碰撞。由于A *算法通常計(jì)算只有一小部分配置空間，這將產(chǎn)生相當(dāng)大的改善效率。碰撞可以在步驟4a中提到的成本函數(shù)加入一個(gè)大型的罰款處罰。另外，在碰撞中產(chǎn)生的一個(gè)網(wǎng)格點(diǎn)可以直接從省略開放期間電網(wǎng)的擴(kuò)張階段的名單。在這項(xiàng)研究中，后者的做法被使用。 圖6.一個(gè)面向包圍盒模型的六個(gè)自由度的RV-E2的操縱 4.3.2.碰撞檢測(cè)算法 碰撞檢測(cè)算法在MATLAB中實(shí)現(xiàn)根據(jù)報(bào)道由Boyse（1979年）的想法。該算法計(jì)算的交點(diǎn)在工作區(qū)中的其他結(jié)構(gòu)部件表面的機(jī)器人模型的表面。計(jì)算兩個(gè)曲面相交的本質(zhì)歸結(jié)為決定從幾何中使用的標(biāo)準(zhǔn)工具，可以實(shí)現(xiàn)與其他表面的一個(gè)表面的邊緣相交。所有的一切，碰撞檢測(cè)是一項(xiàng)計(jì)算密集型的任務(wù)。因此，在實(shí)時(shí)應(yīng)用，如黃瓜機(jī)器人碰撞檢測(cè)，需要碰撞檢測(cè)的精度和可用計(jì)算時(shí)間之間的權(quán)衡。精確的CAD模型圖。 4包含600個(gè)三角形和矩形表面。一因素15減少計(jì)算時(shí)間，實(shí)現(xiàn)了從所謂的面向邊界建立了一個(gè)不太準(zhǔn)確的模型代替精確的操縱模型盒（更新行動(dòng)）。這種三維機(jī)械手的只有36個(gè)移動(dòng)的表面組成OBB的模型如圖6所示。顯然，一些與OBB的模型精度已提供計(jì)算速度的緣故。對(duì)于目前的調(diào)查，它被認(rèn)為是合理的。 5．例1：碰撞兩個(gè)度的自由操縱運(yùn)動(dòng)規(guī)劃 要說明的方法，結(jié)果與兩兩自由度轉(zhuǎn)動(dòng)關(guān)節(jié)的機(jī)械臂的無碰撞運(yùn)動(dòng)規(guī)劃。圖7（a）顯示了一個(gè)人為的溫室環(huán)境，其中方塊代表黃瓜莖的目標(biāo)是移動(dòng)的路徑（直打下了）操縱的工具中心點(diǎn)背后掛在黃瓜黃瓜冠捷干，沒有擊中任何黃瓜莖。這被認(rèn)為是黃瓜采摘過程中最困難的議案之一。 5.1.結(jié)果 為了說明操作的運(yùn)動(dòng)規(guī)劃算法，圖。 7（b）顯示相關(guān)的兩維的配置空間。一個(gè)離散化步驟五度使用。堅(jiān)實(shí)的黑色方塊，稱為配置的障礙，代表機(jī)器人和黃瓜干之間的碰撞產(chǎn)生的配置。由字母S表示開始配置目標(biāo)配置是由字母G表示：他們代表的開始姿勢(shì)和圖采摘姿態(tài)。 7（一）。路徑搜索的目標(biāo)是要找到一個(gè)起始節(jié)點(diǎn)S和目的節(jié)點(diǎn)G之間的連接：觀察，首先，配置空間的地圖，揭示了真正復(fù)雜運(yùn)動(dòng)規(guī)劃的問題，可能看起來瑣碎的工作空間中。其次，觀察，一條直路從起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)碰撞的結(jié)果，并因此是不可行的。圖7（c）所示的網(wǎng)格節(jié)點(diǎn)，記為*，A *算法的評(píng)估過程中向前搜索從起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)。圖所示的配置空間中的最優(yōu)路徑。如圖7（d）及相關(guān)的無碰撞機(jī)械臂在工作區(qū)的議案快照。 7（E）。觀察，在工作區(qū)中的無碰撞運(yùn)動(dòng)的空間配置結(jié)果無碰撞的議案;機(jī)器人不會(huì)干擾與工作空間的障礙：黃瓜莖。最后，圖7（f）顯示網(wǎng)格節(jié)點(diǎn)A *算法當(dāng)一個(gè)落后的搜索目標(biāo)節(jié)點(diǎn)的起始節(jié)點(diǎn)進(jìn)行評(píng)估。 5.2.討論 結(jié)果表明，在配置空間沸騰的路徑搜索，找到一個(gè)點(diǎn)的運(yùn)動(dòng)軌跡，從一開始就配置目標(biāo)配置。 圖7（c）和（F）清楚地表明，碰撞檢查接續(xù)OFA先驗(yàn)碰撞檢測(cè)路徑搜索過程中，由于A *算法，只有部分評(píng)估在配置空間網(wǎng)格點(diǎn)的優(yōu)勢(shì)。此外，研究結(jié)果表明，如果一個(gè)障礙之間開始配置和位于目標(biāo)配置，大量的網(wǎng)格節(jié)點(diǎn)找到了解決辦法之前，必須進(jìn)行評(píng)估。在這種情況下，A *算法不是很有效，在發(fā)現(xiàn)周圍的配置空間障礙的一種方式。障礙的情況下密切繞過一個(gè)目標(biāo)節(jié)點(diǎn)，一個(gè)落后的搜索可能會(huì)產(chǎn)生較少的解決方案由圖所示的計(jì)算時(shí)間。 7（F）。在這個(gè)例子中向后搜索向前搜索時(shí)取得117而不是146次迭代后的解決方案;減少20％。如果目標(biāo)節(jié)點(diǎn)位于兩者之間的障礙脊巷子盡頭，即使在較高的迭代次數(shù)減少使用向后搜索（結(jié)果未顯示）獲得。最好的搜索方向明確，取決于手頭的特定結(jié)構(gòu)的問題。這兩個(gè)圖。 7條（d）及（e）表明，以實(shí)現(xiàn)最優(yōu)路徑成本函數(shù)的意義，算法往往偷工減料，致使小機(jī)器人和障礙物之間的距離。要牢記這一特點(diǎn)，在實(shí)際運(yùn)動(dòng)規(guī)劃實(shí)驗(yàn)時(shí)，傳感器為基礎(chǔ)的世界描述數(shù)據(jù)不準(zhǔn)確容易。然后可能會(huì)發(fā)生碰撞，不占在運(yùn)動(dòng)規(guī)劃。最后，圖7（d）顯示，由于電網(wǎng)結(jié)構(gòu)和正交擴(kuò)展的路徑搜索過程中的網(wǎng)格節(jié)點(diǎn)，運(yùn)動(dòng)路徑包含了一些尖角。這將導(dǎo)致強(qiáng)不必要的加速和減速的鏈接時(shí)，在實(shí)踐中實(shí)施。在第4節(jié)的建議，為平滑軌跡規(guī)劃的議案等不良行為的來電。 6．例2：碰撞為6度的自由操縱運(yùn)動(dòng)規(guī)劃 這一段演示六自由度三菱RV-E2的機(jī)械臂運(yùn)動(dòng)規(guī)劃方案。圖8（a）顯示了三維視圖六自由度機(jī)械手，在一個(gè)人為的溫室環(huán)境。再次，目標(biāo)是從路徑中的位置移動(dòng)機(jī)器人的工具中心點(diǎn)到黃瓜掛背后的黃瓜干，沒有擊中黃瓜TEMS代表由黑職位。 圖7.黃瓜采摘在一個(gè)人為的溫室環(huán)境經(jīng)營(yíng)度自由操縱的無碰撞運(yùn)動(dòng)規(guī)劃：（a）開始姿勢(shì)（直）和目標(biāo)姿態(tài)與機(jī)械臂的工作空間冠捷挑選黃瓜掛灰色正方形代表;（b）與代表的黑色區(qū)域配置中的碰撞和S的起點(diǎn)和目標(biāo)配置，分別代表?配置空間;（c）配置空間由A采樣黃瓜干背后*算法在從一開始向前搜索到目標(biāo)節(jié)點(diǎn);（d）通過配置空間的無碰撞軌跡;（e）6，到操盤黃瓜的無碰撞運(yùn)動(dòng)的快照;（f）配置A *算法在空間采樣，從向后搜索目標(biāo)的起始節(jié)點(diǎn)1和2是第一和第二關(guān)節(jié)的旋轉(zhuǎn)。 6.1．結(jié)果 由于這個(gè)例子涉及一個(gè)六自由度機(jī)械手，執(zhí)行搜索，在六維的配置空間。這是不可能的可視化配置空間的無碰撞點(diǎn)的運(yùn)動(dòng)，是與前面的例子一樣。因此，只有通過工作區(qū)的無碰撞運(yùn)動(dòng)的快照?qǐng)D。 8（一） - （F）。該議案涉及所有6個(gè)旋轉(zhuǎn)關(guān)節(jié)。從本質(zhì)上講，黃瓜的議案，由兩部分組成。首先所有機(jī)器人向后傾斜，同時(shí)圍繞主垂直軸旋轉(zhuǎn)，然后傾斜前鋒再次攜帶刀具中心點(diǎn)之間的黃瓜莖。其次，同時(shí)，過去三年關(guān)節(jié)旋轉(zhuǎn)，以便能夠定位在背后的黃瓜干黃瓜工具中心點(diǎn)。這樣做，黃瓜干規(guī)避。 6.2．討論 結(jié)果表明，碰撞自由運(yùn)動(dòng)的六自由度機(jī)械手可以發(fā)現(xiàn)。據(jù)預(yù)計(jì)，這一結(jié)果可以擴(kuò)展到七個(gè)自由度的機(jī)械手，在黃瓜采摘設(shè)備使用。然而，這個(gè)例子揭示了A *算法的弱點(diǎn)。對(duì)于正在審議的六自由度機(jī)械手，在六維的配置空間進(jìn)行搜索。然后，由于網(wǎng)格點(diǎn)的大量的，必須進(jìn)行評(píng)估，搜索變得過于緩慢。這部分是由于在MATLAB實(shí)現(xiàn)。該軟件包不是很有效時(shí)，必須執(zhí)行大量的迭代。再次，結(jié)果表明：在運(yùn)動(dòng)軌跡的尖角。當(dāng)需要高速運(yùn)動(dòng)，這些運(yùn)動(dòng)軌跡要平滑，以防止上機(jī)械臂鏈接的重載。 黃瓜采摘機(jī)器人 圖8.（a）-（f）：六快照的無碰撞運(yùn)動(dòng)6自由度RV-E2的操縱掛在黃瓜背后黃瓜莖代表黑色垂直職位 7.結(jié)論 本文提出了一種方法，以達(dá)到適當(dāng)?shù)氖盅蹍f(xié)調(diào)的黃瓜收獲機(jī)器人在農(nóng)業(yè)和環(huán)境工程研究所（IMAG BV）的開發(fā)。本文提出了一個(gè)方案，是能夠生成機(jī)器人無碰撞運(yùn)動(dòng)。一些數(shù)值例子說明了該方法和分析。 本研究的主要結(jié)論是，無碰撞運(yùn)動(dòng)可以計(jì)算六度自由度（DOF），RV-E2的機(jī)械臂在收獲機(jī)使用。據(jù)預(yù)計(jì)，這些結(jié)果可以擴(kuò)展到七自由度機(jī)械手，即RV-E2的操縱器線性滑軌安裝。被發(fā)現(xiàn)的A*搜索算法很容易實(shí)現(xiàn)和強(qiáng)大的。通過這種方式，它提供了很多有識(shí)之士為機(jī)器人運(yùn)動(dòng)規(guī)劃的具體問題。此外，該算法的一個(gè)大優(yōu)勢(shì)是，它可以產(chǎn)生一個(gè)解決方案或停止時(shí)，無法找到一個(gè)解決方案。該財(cái)產(chǎn)的完整性，但是，使得算法望而卻步緩慢。結(jié)果發(fā)現(xiàn)，與本文中所描述的算法涉及的多自由度機(jī)械手運(yùn)動(dòng)軌跡的計(jì)算是計(jì)算非常。至符合所需的周期時(shí)間的10秒為一個(gè)單一的收獲行動(dòng)，需要進(jìn)一步研究，以減少議案所需的計(jì)算時(shí)間規(guī)劃。研究，可沿兩條線。首先，可以減少計(jì)算時(shí)間，通過使用特殊的計(jì)算機(jī)硬件，例如并行處理器。另外，同時(shí)，減少計(jì)算可以通過使用更快和有效地實(shí)現(xiàn)的算法。此外，結(jié)果表明，該算法不包括許多情報(bào)。雖然它試圖產(chǎn)生定向運(yùn)動(dòng)的目標(biāo)，如果它只是配置遇到障礙樣品中的搜索空間網(wǎng)格解決方案，直到發(fā)現(xiàn)不使用有關(guān)的問題，特別是結(jié)構(gòu)的信息點(diǎn)。因此，進(jìn)一步研究需要獲得快速算法，有效地利用有關(guān)的問題，特別是結(jié)構(gòu)的信息，不卡，恕不另行通知。 致謝 這項(xiàng)工作是由荷蘭農(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