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

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

中圖分類號：TP 242" " " " " 文獻(xiàn)標(biāo)志碼：A

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

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

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

1.1 環(huán)境模型

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

1.2 人流量運(yùn)動模型

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

1.2.1 移動規(guī)則

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

1.2.2 避障規(guī)則

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

1.2.3 距離規(guī)則

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

1.2.4 群體規(guī)則

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

1.3 人流量模型仿真

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

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

2.1 仿真機(jī)器人定義

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

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

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

2.2.1 矩形路徑

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

2.2.2 往復(fù)路徑

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

2.2.3 迷宮路徑

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

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

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

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

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

2.3.1 初始設(shè)定

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

2.3.2 時(shí)間步長與最遠(yuǎn)區(qū)域定義

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

（1）

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

2.3.3 時(shí)間步長運(yùn)動策略

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

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

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

（3）

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

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

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

（4）

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

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

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

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

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

3 路徑對比仿真試驗(yàn)

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

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

4 結(jié)語

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

參考文獻(xiàn)

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

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

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

[4]劉娜.基于偏好數(shù)據(jù)的旅游景點(diǎn)路線推薦方法[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.