互動式銷售機器人路徑優(yōu)化研究

摘 要：為提升互動式銷售機器人廣告投放效果，本文對其路徑進行優(yōu)化。首先，建立環(huán)境模型和人流量運動模 型，獲取隨機運動的人流量分布數(shù)據(jù)，為路徑優(yōu)化提供數(shù)據(jù)支持；其次，采用貪心算法優(yōu)化機器人運動路徑，使其更智能地在人流密集區(qū)域移動；最后，進行仿真對比試驗，試驗結(jié)果表明，與傳統(tǒng)固定路徑相比，優(yōu)化后的路徑具有明顯優(yōu)勢，使機器人在設(shè)定時間長度內(nèi)能夠遇到更多行人。因此，在人流密集的場地，機器人路徑優(yōu)化的作用十分重要，可以增加廣告曝光機會，為商家?guī)砀叩慕?jīng)濟效益。

關(guān)鍵詞：互動式銷售機器人；路徑優(yōu)化；環(huán)境模型；人流量運動模型；貪心算法；仿真

中圖分類號：TP 242" " " " " 文獻標志碼：A

互動式銷售機器人配備多個大屏幕，可在人流密集的商場和車站自主移動，有效傳遞廣告信息并在現(xiàn)場進行銷售。隨著機器人廣泛應(yīng)用，有效優(yōu)化移動路徑，提高廣告可見度和銷售效率成為巨大挑戰(zhàn)。

大多數(shù)路徑優(yōu)化研究主要包括路徑規(guī)劃算法的設(shè)計和實施[1-3]，缺乏結(jié)合環(huán)境模型和人流量運動模型來評估運動路徑的研究。本文建立環(huán)境和人流量運動模型，并基于上述模型運用貪心算法進行路徑優(yōu)化，以增加機器人接觸行人的機會，利用對比仿真試驗分析路徑優(yōu)化的效果。

1 環(huán)境模型和人流量運動模型

1.1 環(huán)境模型

本文創(chuàng)建1張二維平面地圖，其作用是模擬行人在特定區(qū)域內(nèi)的動態(tài)分布情況，環(huán)境模型與人流量運動模型如圖1所示，該地圖無障礙物的虛擬空間，為了更清晰地展示各區(qū)域內(nèi)行人實時分布情況，利用一系列垂直線條將地圖均勻劃分為10個面積相等、互不重疊的區(qū)域，這些區(qū)域由左至右依次編號為1～10，在每個區(qū)域的中心位置實時顯示當(dāng)前時刻該區(qū)域內(nèi)的行人數(shù)量。采用這種可視化方式，可以動態(tài)地觀察行人的運動趨勢，并持續(xù)記錄一段時間內(nèi)的行人數(shù)據(jù)變化，為人流量運動模型仿真提供數(shù)據(jù)基礎(chǔ)。該環(huán)境模型還具備可擴展性，可以增加或減少區(qū)域數(shù)量以及改變區(qū)域面積來滿足不同的模擬仿真需求。

1.2 人流量運動模型

本文創(chuàng)建行人對象類代表虛擬環(huán)境中的行人，該類具有位置、半徑、速度和顏色屬性，在圖1中，每個點代表1個行人。在本模型中，行人的運動過程基于以下4個規(guī)則。

1.2.1 移動規(guī)則

每個行人在每段運動軌跡的開始階段都會隨機選擇移動方向和移動速度，根據(jù)概率分布在特定范圍內(nèi)隨機生成以上數(shù)值，保證運動的不可預(yù)測性。

1.2.2 避障規(guī)則

每個行人在移動過程中會實時檢測地圖邊界和其他行人的位置，當(dāng)接近邊界或他人時及時調(diào)整自己的運動軌跡來有效避免碰撞。

1.2.3 距離規(guī)則

每個行人在移動過程中會保持與其他行人的最短距離，以模擬個體的空間感和社交距離，這個規(guī)則需要實時計算行人間的相對位置，并對移動策略進行動態(tài)調(diào)整。

1.2.4 群體規(guī)則

行人的運動方向不僅取決于隨機生成的移動規(guī)則，還會受到周圍群體行為的影響，每個行人會根據(jù)自己當(dāng)前所處位置和群體的運動趨勢來設(shè)置移動的特定方向和范圍，以模擬人群中的集體行為趨勢。對這些基本規(guī)則進行多樣化組合和權(quán)重設(shè)置，可以模擬高密度人群中行人的復(fù)雜移動行為，并產(chǎn)生豐富的人群集體運動效果。例如，調(diào)整移動規(guī)則中的隨機性參數(shù)可以模擬從緩慢移動到快速通行的人群行為動態(tài)；調(diào)整避障和距離規(guī)則的響應(yīng)時間可以模擬當(dāng)擁擠程度不同時行人的移動趨勢；調(diào)整群體規(guī)則中的集體運動趨勢可以模擬人群的擁堵或疏散等不同情境。

1.3 人流量模型仿真

本文在環(huán)境模型中針對特定的行人總量進行人流量模型仿真，設(shè)定行人總量為800名，在初始時刻，行人在地圖中隨機分布，以保證初始條件的不確定性。在仿真過程中，所有行人始終在地圖內(nèi)部進行移動，逐漸產(chǎn)生定向聚集。仿真模型運行一段時間后，收集不同時間點各個區(qū)域的行人數(shù)量數(shù)據(jù)。為了更直觀地進行展示，采用Matplotlib庫進行數(shù)據(jù)的可視化處理，并執(zhí)行插值操作，以生成平滑曲面，增強數(shù)據(jù)的美觀性。人流量仿真結(jié)果如圖2所示，隨著仿真時間增加，行人逐漸向地圖中的區(qū)域6至區(qū)域8之間聚集，這個仿真結(jié)果將作為后續(xù)路徑對比仿真試驗的行人數(shù)量數(shù)據(jù)基礎(chǔ)。

2 機器人路徑優(yōu)化

2.1 仿真機器人定義

本文設(shè)計1個機器人模型，該模型具有位置、半徑、速度和顏色屬性。在第1.1節(jié)創(chuàng)建的環(huán)境模型中部署機器人，并使其勻速移動，以保證機器人在地圖環(huán)境中的可預(yù)測性。根據(jù)第1.3節(jié)中的人流量仿真結(jié)果運行人流量運動模型。在設(shè)定的時間長度內(nèi)，不同的機器人移動路徑將直接影響其遇到的行人數(shù)量，機器人遇到的行人越多，其產(chǎn)生的廣告效果和購物引導(dǎo)能力越好。

2.2 傳統(tǒng)的機器人路徑模型

傳統(tǒng)的機器人移動路徑通常是固定的，本文模擬了3種不同的機器人路徑，分別為矩形路徑、往復(fù)路徑和迷宮路徑。

2.2.1 矩形路徑

機器人平行并與地圖邊界保持一定距離勻速移動，在每個拐角處直角轉(zhuǎn)彎，繼續(xù)向地圖內(nèi)側(cè)移動，最終移動軌跡形成1個矩形。該路徑簡單，容易操作，如果行人主要在地圖中心區(qū)域活動，那么很難遇到太多行人。

2.2.2 往復(fù)路徑

機器人以往返方式不停地在地圖中軸線上移動，移動軌跡是1條直線，這種路徑貼近中心區(qū)域，但是缺乏全面覆蓋地圖的能力。

2.2.3 迷宮路徑

機器人從地圖左側(cè)逐漸向右側(cè)移動，盡量覆蓋地圖內(nèi)部更多點位，移動軌跡類似迷宮。這種路徑可以在復(fù)雜人流運動環(huán)境中盡可能全面地覆蓋所有區(qū)域，但是仍然缺乏靈活性。綜上所述，傳統(tǒng)的機器人移動路徑在特定條件下各有優(yōu)勢，但是處于復(fù)雜多變的人流運動環(huán)境中都有一定的局限性。3種固定路徑的移動軌跡如圖3所示。

2.3 基于貪心算法的路徑優(yōu)化模型

由圖2可知，在不同時間段與不同區(qū)域，行人數(shù)量的分布是非線性且不均勻的，說明在某些特定時段或者特定區(qū)域內(nèi)，行人數(shù)量可能會急劇變化，傳統(tǒng)的固定路徑策略無法及時應(yīng)對這些變化，導(dǎo)致機器人無法根據(jù)實時行人分布情況調(diào)整動態(tài)路徑，錯失與更多行人相遇的機會。

為了提高機器人的工作效率，使其能在設(shè)定時間長度內(nèi)盡量遇到更多行人，本文基于貪心算法進行機器人路徑優(yōu)化[4-6]。貪心算法（Greedy Algorithm）是一種適用性很廣的算法策略，該算法在每一步都選擇當(dāng)前狀態(tài)下的最優(yōu)解，不斷重復(fù)局部最優(yōu)策略來得到全局最優(yōu)解。首先，定義一個目標函數(shù)，其作用是量化在給定時間步長內(nèi)，當(dāng)機器人移動至不同區(qū)域時可能遇到的行人數(shù)量，該函數(shù)將第1.3節(jié)的人流量仿真結(jié)果作為關(guān)鍵參數(shù)。其次，在給定時間步長內(nèi)，機器人須選擇能使目標函數(shù)的值最大化的區(qū)域作為目標區(qū)域，即能夠遇到最多行人的區(qū)域。最后，多次迭代和優(yōu)化后全局路徑趨向于最優(yōu)。完成上述步驟，機器人能夠靈活應(yīng)對行人分布的動態(tài)變化。

基于貪心算法的路徑優(yōu)化模型詳細設(shè)計步驟如下。

2.3.1 初始設(shè)定

假設(shè)機器人以勻速V在環(huán)境模型內(nèi)運行，設(shè)定時間長度TS，TS可分解為一段段時間不等的時間步長Tstep。根據(jù)貪心算法規(guī)則，在每一段時間步長Tstep內(nèi)，選擇使機器人能夠遇到最多行人的區(qū)域作為目標區(qū)域，規(guī)劃能夠使行人數(shù)量最大化的完整移動路徑。

2.3.2 時間步長與最遠區(qū)域定義

確定第一段時間步長Tstep的長度，在時間步長的開始階段，根據(jù)機器人當(dāng)前所處區(qū)域位置確定其所能到達的最遠區(qū)域，將從當(dāng)前區(qū)域到達最遠區(qū)域所需的時間作為本階段的時間步長長度，這樣可以保證當(dāng)機器人在本時間步長內(nèi)前往任意1個目標區(qū)域時不會出現(xiàn)時間不夠而無法到達的情況。時間步長計算過程如公式（1）所示。

（1）

式中：Tstep為時間步長；Dc，1為從當(dāng)前區(qū)域至區(qū)域1的距離；Dc，10為從當(dāng)前區(qū)域至區(qū)域10的距離；V為機器人速度。

2.3.3 時間步長運動策略

在每一段時間步長Tstep內(nèi)，評估從當(dāng)前區(qū)域前往每個區(qū)域可能遇到的行人數(shù)量Nc，1，假設(shè)機器人位于區(qū)域3，那么就需要分別計算N3，1、N3，2、N3，4、N3，5、...、N3，10，進行比較，選擇能遇到最多行人的區(qū)域作為目標區(qū)域，如公式（2）所示。

Nc，i=Nc，i（middle）+Nc，i（wait） " " " " （2）

式中：Nc，i（middle）為在前往區(qū)域i的過程中遇到的行人數(shù)量；Nc，i（wait）為到達區(qū)域 i 以后，如果所用時間未達到時間步長，那么等待至?xí)r間步長結(jié)束所遇到的行人數(shù)量。對每個區(qū)域在機器人經(jīng)過的時間段內(nèi)的人流量進行積分計算，將這些積分結(jié)果求和，如公式（3）所示。

（3）

式中：Nj為機器人在區(qū)域j遇到的行人數(shù)量；c為當(dāng)前區(qū)域；i為擬到達區(qū)域；為從當(dāng)前區(qū)域開始，一直運行至擬到達區(qū)域所經(jīng)過的每個中間區(qū)域遇到的行人數(shù)量之和；tjs和tje為前往j的開始時間點和到達時間點；Pj（t）為根據(jù)第1.3節(jié)人流量模型仿真得到的j的人流量函數(shù)；t為時間。

由于機器人勻速前進且每個區(qū)域之間的距離相等，因此tfix=tje-tjs，用Pj（t）在該時間段內(nèi)的積分來表示機器人在該區(qū)域內(nèi)遇到的行人數(shù)量。

Nc，i（wait）計算過程如公式（4）所示。

（4）

式中：tie為在最后一個區(qū)域開始等待的時間點，通常也是

Nc，i（middle）結(jié)束的時間點；tiw為最后一個區(qū)域結(jié)束等待的時間點，在第一個時間步長內(nèi)就是Tstep；Pi（t）為最后一個區(qū)域的人流量函數(shù)。

假設(shè)機器人位于區(qū)域3，前往區(qū)域6，那么在途中遇到的行人數(shù)量包括經(jīng)過區(qū)域4、區(qū)域5和區(qū)域6遇到的行人以及等待期間遇到的行人。

2.3.4 算法循環(huán)策略

該時間步長結(jié)束后，將當(dāng)前所在區(qū)域設(shè)為起點，更新剩余時間為設(shè)定時間長度減去前面的時間步長，重復(fù)步驟二、步驟三直至剩余時間小于最新的時間步長為止。綜上所述，基于前述貪心算法策略，在每一個Tstep都選擇Nc，i最大的區(qū)域作為目標區(qū)域，前往該區(qū)域，更新該區(qū)域作為新的起點，剩余時間長度為（TS-Tstep），重復(fù)上述計算過程，直至剩余時間長度小于最新的Tstep為止。

3 路徑對比仿真試驗

本文基于上述模型，在地圖里模擬設(shè)定時間長度內(nèi)機器人運行4種路徑的狀況，其中A為優(yōu)化路徑；B為矩形路徑；C為往復(fù)路徑；D為迷宮路徑。每個路徑后的數(shù)字代表機器人運行該路徑所遇到的行人數(shù)量，該數(shù)字不斷累加，地圖中部每個區(qū)域的數(shù)字代表當(dāng)前時刻該區(qū)域內(nèi)的行人數(shù)量。不同路徑仿真過程如圖4所示，4個機器人同時運行4種路徑，實時統(tǒng)計各種路徑所能遇到的行人數(shù)量，并顯示在地圖中。

不同路徑遇到的行人數(shù)量對比如圖5所示，在仿真初期，優(yōu)化路徑A的行人數(shù)量與固定路徑相差不大，隨著時間推移，路徑A實時監(jiān)測行人流動數(shù)據(jù)，迅速調(diào)整自身移動策略，在每個時間步長內(nèi)都主動前往人流量更大的區(qū)域，遇到了更多的行人，顯著提高了工作效率。固定路徑B、C和D雖然在仿真初期可能會有短暫優(yōu)勢，但是整體表現(xiàn)遠遠落后于優(yōu)化路徑A。隨著時間延長，優(yōu)化路徑A的優(yōu)勢越來越明顯，而3條固定路徑B、C和D在不同時間段遇到的行人數(shù)量始終差異不大，說明它們工作效率相近，無法有效應(yīng)對行人流動的動態(tài)變化。與傳統(tǒng)固定路徑相比，基于貪心算法進行優(yōu)化的機器人移動路徑在人流量非線性變化的環(huán)境模型中具有顯著優(yōu)勢，該優(yōu)勢隨著時間延長越來越明顯。

4 結(jié)語

本文結(jié)合環(huán)境模型、人流量運動模型以及貪心算法提出一種互動式銷售機器人路徑優(yōu)化方法，使用環(huán)境模型和人流量運動模型為路徑優(yōu)化提供數(shù)據(jù)支撐，并使用貪心算法提升機器人工作效率。試驗結(jié)果表明，與固定路徑相比，優(yōu)化路徑具有顯著優(yōu)勢，能夠提升機器人的商業(yè)價值。盡管本研究取得了一定進展，但是需要在實際應(yīng)用中利用現(xiàn)場數(shù)據(jù)驗證成果的可靠性。綜上所述，本研究為互動式銷售機器人路徑優(yōu)化提供了新的思路和方法，為相關(guān)研究提供參考。

參考文獻

[1]王洪斌，郝策，張平，等.基于基于A*算法和人工勢場法的移動機器人路徑規(guī)劃[J].中國機械工程，2019，30（20）：2489-2496.

[2]于振中，李強，樊啟高.智能仿生算法在移動機器人路徑規(guī)劃優(yōu)化中的應(yīng)用綜述[J].計算機應(yīng)用研究，2019，36（11）：3210-3219.

[3]代軍，李志明，李艷琴，等.基于改進Informed-RRT*算法的機器人路徑規(guī)劃[J].河南理工大學(xué)學(xué)報（自然科學(xué)版），2022，41（4）：95-100.

[4]劉娜.基于偏好數(shù)據(jù)的旅游景點路線推薦方法[J].信息技術(shù)，2023（11）：148-152，157.

[5]徐小小，周啟銀，婁成龍，等.基于貪心算法的自動路徑規(guī)劃送藥小車[J].中國新技術(shù)新產(chǎn)品，2023（8）：21-23.

[6]孔欽，劉晨，顧永鑫.基于貪心算法的常態(tài)化防疫交通路線智能推薦系統(tǒng)[J].現(xiàn)代信息科技，2022，6（17）：33-37.