Fungsi carian sedang dalam pembinaan.
Fungsi carian sedang dalam pembinaan.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

Open Access
Extension of Counting LTL and Its Application to a Path Planning Problem for Heterogeneous Multi-Robot Systems
Membuka akses
Lanjutan Pengiraan LTL dan Aplikasinya kepada Masalah Perancangan Laluan untuk Sistem Berbilang Robot Heterogen

Kotaro NAGAE, Toshimitsu USHIO

  • pandangan teks lengkap

    330

  • Petikan Ini
  • Free PDF (1.5MB)

Ringkasan:

Kami menangani masalah perancangan laluan untuk sistem berbilang robot heterogen di bawah spesifikasi yang terdiri daripada kekangan temporal dan tugas penghalaan seperti perkhidmatan penghantaran pakej. Robot dibahagikan kepada beberapa kumpulan berdasarkan dinamik dan spesifikasinya. Kami memperkenalkan penerangan ringkas tentang tugasan tersebut, yang dipanggil a bekerja, dan melanjutkan pengiraan LTL untuk mewakili spesifikasi sedemikian. Kami menukar masalah itu kepada masalah ILP. Kami menunjukkan bahawa bilangan pembolehubah dalam masalah ILP adalah kurang daripada kaedah sedia ada menggunakan cLTL+. Melalui simulasi, kami menunjukkan bahawa masa pengiraan kaedah yang dicadangkan adalah lebih cepat daripada kaedah sedia ada.

Jawatankuasa
IEICE TRANSACTIONS on Fundamentals Vol.E107-A No.5 pp.752-761
Tarikh penerbitan
2024/05/01
Diumumkan
2023/10/02
ISSN dalam talian
1745-1337
DOI
10.1587/transfun.2023MAI0001
Jenis Manuskrip
Special Section INVITED PAPER (Special Section on Mathematical Systems Science and its Applications)
kategori

1. Pengenalan

Sistem multi-robot ialah sistem yang terdiri daripada beberapa robot yang bekerja secara kooperatif untuk mencapai spesifikasi yang diberikan kepada sistem. Dalam beberapa tahun kebelakangan ini, sistem multi-robot telah dikaji untuk digunakan dalam banyak bidang kejuruteraan, seperti untuk meningkatkan kecekapan sistem pengeluaran [1] dan untuk menyelamat yang berkesan di tapak bencana [2]. Sistem berbilang robot di mana tidak semua robot mempunyai dinamik dan spesifikasi yang sama dipanggil a sistem multi-robot heterogen [3]. Spesifikasi untuk sistem berbilang robot heterogen terdiri daripada satu set subspesifikasi kompleks seperti "sentiasa elakkan rantau A, lawati wilayah B sebelum melawati wilayah C, dan kemudian melawati wilayah D". Kemudian, kami menentukan kedua-dua tugasan setiap subspesifikasi kepada robot dan perancangan laluan setiap robot dengan mengambil kira dinamik setiap robot, yang merupakan masalah gabungan, dan kutukan dimensi timbul.

Spesifikasi untuk sistem berbilang robot adalah kompleks secara umum dan pendekatan formal berguna untuk menerangkan spesifikasi [4], [5]. Logik temporal linear (LTL) telah digunakan untuk penerangan formal spesifikasi untuk masalah perancangan laluan [6]. Ia juga merupakan pendekatan yang berguna untuk menerangkan spesifikasi kompleks untuk sistem berbilang robot [7]-[9] dan baru-baru ini beberapa sambungan LTL seperti STL [10], CaTL [11], dan swarmSTL [12] telah digunakan untuk sistem berbilang robot. Secara kasarnya, terdapat dua jenis spesifikasi. Satu dipanggil spesifikasi tempatan manakala satu lagi dipanggil global. Spesifikasi tempatan diberikan untuk setiap robot dan laluan untuk setiap robot ditentukan dengan mengambil kira penyelarasan antara robot seperti pengelakan perlanggaran [13]-[15]. Spesifikasi global diberikan untuk sistem berbilang robot dan, selepas diuraikan menjadi subspesifikasi yang diberikan ke dalam setiap robot, laluan untuk setiap robot ditentukan [16]-[19]. Baru-baru ini, logik temporal dua lapis yang terdiri daripada an logik dalaman dan logik luar telah dicadangkan untuk menerangkan spesifikasi tingkah laku kolektif yang dikehendaki untuk sekumpulan robot secara ringkas [20], [21]. Sahin et al. memperkenalkan logik temporal dua lapis yang dipanggil mengira LTL tambah (cLTL+), merumuskan masalah perancangan laluan menggunakan formula cLTL+, dan mencadangkan kaedah untuk mendapatkan laluan untuk robot dengan menukarkannya kepada masalah pengaturcaraan linear integer (ILP) [21]. Walaupun cLTL+ mempunyai keupayaan perihalan yang kaya, ia memerlukan banyak masa pengiraan untuk menyelesaikan masalah perancangan laluan yang spesifikasinya diberikan oleh formula cLTL+. Serpihan cLTL+, dipanggil cLTL, dicadangkan untuk menerangkan sifat keselamatan seperti "Bilangan robot di rantau A adalah kurang daripada lima." dan telah ditunjukkan bahawa masa pengiraan boleh dikurangkan apabila spesifikasi diterangkan oleh formula cLTL. Walau bagaimanapun, kuasa ungkapan cLTL adalah kurang daripada kuasa cLTL+.

Dalam robot mudah alih, banyak masalah praktikal seperti masalah pengambilan dan penghantaran serta masalah penghantaran pakej mengakibatkan pengiraan laluan mereka dari lokasi awal ke lokasi sasaran yang ditentukan [22]-[25]. Terutamanya, disebabkan perkembangan pesat e-dagang, permintaan untuk perkhidmatan penghantaran pakej yang cekap meningkat. Selain itu, penghantaran pakej oleh kenderaan udara tanpa pemandu (UAV) menjadi perkara biasa [26] dan penghantaran pakej automatik bukan sahaja oleh kenderaan darat tetapi juga UAV diberi perhatian. Masalah penghantaran pakej sistem multi-robot heterogen telah dikaji [27], [28]. Tetapi, sepanjang pengetahuan kami, terdapat beberapa kajian tentang masalah penghantaran pakej dengan kekangan sementara untuk sistem berbilang robot heterogen. Kedua-dua kekangan temporal dan penghantaran pakej boleh diterangkan oleh formula cLTL+. Tetapi penghantaran pakej tidak boleh diterangkan oleh formula cLTL supaya ia mengambil banyak masa pengiraan untuk menyelesaikan masalah. Dalam kertas ini, kami memperkenalkan penerangan padat tentang pergerakan dari lokasi permulaan yang ditentukan ke lokasi sasaran yang ditentukan, yang akan dipanggil bekerja dan cadangkan sambungan cLTL dipanggil cLTL dengan kerja (cLTLW) untuk menentukan perkhidmatan penghantaran pakej. Oleh kerana perkhidmatan dilakukan oleh laluan terhingga, semantik cLTLw ditakrifkan melalui laluan terhingga, yang serupa dengan \(\mbox{LTL}_f\) [29], [30]. Kemudian, kami merumuskan masalah perancangan laluan menggunakan cLTLw dan menukarnya kepada masalah ILP. Kami menunjukkan bahawa bilangan pembolehubah dalam masalah ILP adalah kurang daripada kaedah sedia ada menggunakan cLTL+. Melalui simulasi, kami menunjukkan bahawa masa pengiraan kaedah yang dicadangkan adalah lebih cepat daripada kaedah sedia ada.

Kertas kerja disusun seperti berikut. Bahagian 2 menerangkan beberapa tatatanda dan mentakrifkan sistem berbilang robot heterogen. Bahagian 3 ulasan mengira logik temporal linear tambah (cLTL+) yang dicadangkan oleh [21]. Bahagian 4 memperkenalkan tanggapan kerja yang mewakili tugas penghalaan seperti penghantaran pakej dan menangani masalah perancangan laluan dengan kerja dan kekangan temporal. Untuk merumuskan masalah, kami memperkenalkan pengiraan LTL dengan kerja (cLTLw). Bahagian 5 menukarkan masalah perancangan laluan kepada masalah pengaturcaraan linear integer. Bahagian 6 menunjukkan keberkesanan kaedah yang dicadangkan dengan membandingkannya dengan kaedah sedia ada berdasarkan LTL+ secara simulasi. Bahagian 7 menyimpulkan kertas kerja.

2. Sistem Berbilang Robot Heterogen

Dalam kertas ini, set integer bukan negatif dilambangkan dengan \(\mathbb{N}\) dan set nombor asli dilambangkan dengan \(\mathbb{N}^+\). Kardinaliti sesuatu set \(A\) dilambangkan dengan \(|A|\). Biarkan \([i] (i \in \mathbb{N}^+)\) be \(\{ 0, 1, \ldots, i \}\).

Kami menganggap sistem berbilang robot heterogen yang terdiri daripada robot dengan dinamik dan spesifikasi yang berbeza dalam ruang kerja. Kami mewakili ruang kerja dengan dunia grid yang terdiri daripada set terhingga \(S\) daripada sel dan \(S\) akan dipanggil a set negara global. Keadaan setiap robot diwakili oleh sel dalam \(S\) di mana ia berada sekarang. Kemudian, satu set robot yang mempunyai dinamik yang sama dan spesifikasi yang diberikan sama dipanggil a kumpulan. Ditandakan oleh \(G\) ialah set semua kumpulan, dan \(N^g\) ialah set indeks semua robot kepunyaan kumpulan \(g \in G\). Kami menganggap kes di mana tugas diberikan kepada kumpulan \(g\) diterangkan dengan menghalakan satu, yang akan dipanggil a bekerja dalam yang berikut, bahawa satu robot masuk \(g\) melakukan, bilangan robot yang melaksanakan kerja, dan kekangan temporal yang dipenuhi oleh \(g\). Kami menganggap bahawa kerja itu diterangkan oleh sepasang sel: satu mewakili sel di mana ia bermula dan satu lagi ialah sel di mana ia selesai. Sebagai contoh, kami menganggap kumpulan dengan lima robot. Spesifikasi yang diberikan kepada kumpulan ialah terdapat tiga pakej di sel \(A\) yang dihantar ke sel \(B\) menggunakan tiga robot dalam kumpulan dan mereka sentiasa berada dalam sel yang selamat. Kemudian, kerja adalah perkhidmatan penghantaran pakej dari sel \(A\) kepada \(B\), bilangan robot yang terlibat dalam kerja adalah tiga, dan kekangan temporal untuk kumpulan itu ialah semua robot sentiasa berada dalam sel yang selamat. Harap maklum bahawa kami bukan sahaja menentukan laluan yang memenuhi spesifikasi tetapi juga robot dalam kumpulan yang terlibat dalam kerja.

Setiap robot dalam kumpulan \(g \in G\) ialah dinamik yang sama yang dimodelkan oleh sistem peralihan keadaan terhingga.

Definisi 1: Sistem peralihan untuk kumpulan \(g \in G\) ialah tuple \(T^g=(S^g, \Sigma^g, \delta^g, AP_S, AP_\Sigma, L_S^g, L_\Sigma^g)\), Di mana \(S^g\subseteq S\) ialah set keadaan terhingga, \(\Sigma^g\) ialah set input terhingga, \(\delta^g\): \(S^g \times \Sigma^g \rightarrow S^g\) ialah fungsi peralihan yang bersifat deterministik dan separa, \(AP_S\) ialah set terhingga proposisi atom yang berkaitan dengan keadaan, \(AP_\Sigma\) ialah set terhingga proposisi atom yang berkaitan dengan peralihan, \(L_S^g\): \(S^g \rightarrow 2^{AP_S}\) ialah fungsi pelabelan yang berkaitan dengan keadaan, dan \(L_\Sigma^g\): \(S^g \times \Sigma^g \rightarrow 2^{AP_\Sigma}\) ialah fungsi pelabelan yang berkaitan dengan peralihan.

Anggap bahawa \(AP_S \cap AP_\Sigma = \emptyset\). Biarkan \(AP\) be \(AP_S \cup AP_\Sigma\). Ambil perhatian bahawa semua robot berkongsi proposisi atom yang sama. Proposisi atom mungkin tidak muncul dalam fungsi pelabelan satu kumpulan, tetapi ia akan muncul dalam fungsi pelabelan beberapa kumpulan lain. Juga ambil perhatian bahawa negeri ditetapkan \(S^{g}\) daripada setiap kumpulan \(g\) ialah subset daripada set keadaan global \(S\), iaitu, \(S^g \subseteq S (\forall g \in G)\), yang bermaksud tiada robot dalam kumpulan \(g\) melawat mana-mana sel dalam \(S \backslash S^g\). Sebagai contoh, ia sepadan dengan kes di mana kenderaan darat tidak boleh masuk ke sungai atau tasik manakala UAV terbang ke mana-mana di ruang kerja.

Trajektori dan jejak setiap robot \(n \in N^g\) in \(g \in G\) ditakrifkan seperti berikut.

Definisi 2: Urutan terhingga \(\pi^g_n=s^g_n \langle 0 \rangle \sigma^g_n \langle 0 \rangle s^g_n \langle 1 \rangle\) \(\sigma^g_n \langle 1 \rangle \ldots s^g_n \langle h-2 \rangle \sigma^g_n \langle h-2 \rangle s^g_n \langle h-1 \rangle \in (S^g \Sigma^g)^{h-1}S^g\) yang memuaskan \(s^g_n \langle {t+1} \rangle = \delta^g(s^g_n \langle t \rangle , \sigma^g_n \langle t \rangle )\) di mana negeri \(s^g_n \langle t \rangle \in S^g\) dan input \(\sigma^g_n \langle t \rangle \in \Sigma^g\) untuk setiap \(t \in [h-1]\) dipanggil a trajektori dan integer positif \(h\) dipanggil panjang daripada trajektori. Lebih-lebih lagi, jejak \(\rho^g_n\) of \(\pi^g_n\) ditakrifkan sebagai \(\rho^g_n = (L_S^g(s^g_n \langle 0 \rangle ) \cup L_\Sigma^g(s^g_n \langle 0 \rangle, \sigma^g_n \langle 0 \rangle )) (L_S^g(s^g_n \langle 1 \rangle ) \cup L_\Sigma^g(s^g_n \langle 1 \rangle , \sigma^g_n \langle 1 \rangle )) \ldots (L_S^g(s^g_n \langle h-2 \rangle ) \cup L_\Sigma^g(s^g_n \langle h-2 \rangle, \sigma^g_n \langle h-2 \rangle ))L_S^g(s^g_n \langle h-1 \rangle ) \in (2^{AP})^h\). Biarkan \(\rho^g_n \langle t \rangle\) menjadi set proposisi atom yang dipenuhi pada masa \(t\), iaitu untuk setiap \(t \in [h-1]\),

\[\begin{eqnarray*}&&\rho^g_n \langle t \rangle \nonumber \\ &&= \left\{\begin{array}{ll} L_S^g(s^g_n \langle t \rangle ) & \mbox{if } t = h-1, \\ L_S^g(s^g_n \langle t \rangle ) \cup L_\Sigma^g(s^g_n \langle t \rangle , \sigma^g_n \langle t \rangle ) & \mbox{otherwise.} \end{array}\right. \tag{1} \end{eqnarray*}\]

Ditandakan oleh \(\Pi = \{ \pi^g_n \mid g\in G, n \in N^g \}\) adalah koleksi trajektori. Ditandakan oleh \(P = \{ \rho^g_n \mid g \in G, n \in N^g \}\) ialah koleksi jejak yang sepadan. Untuk setiap \(a \in AP_S\) dan masing-masing \(g \in G\), biarkan \([\hspace{-1.5pt}[a ]\hspace{-1.5pt}]^g = \{ s \in S^g \mid a \in L_S^g(s) \}\).

Kami menganggap bahawa paling banyak satu robot boleh kekal dalam setiap sel. Adalah penting untuk mempertimbangkan pengelakan perlanggaran apabila berurusan dengan sistem berbilang robot. Terdapat dua kes perlanggaran apabila robot beralih antara keadaan seperti yang ditunjukkan dalam Rajah 1. Satu kes ialah dua atau lebih robot kekal dalam satu keadaan pada masa yang sama. Kes lain ialah dua robot tinggal di dua negeri berjiran pada masa yang sama, dan mereka bertukar negeri mereka pada masa berikutnya. Yang pertama dipanggil perlanggaran pendua dan yang terakhir dipanggil perlanggaran pertukaran.

Rajah 1  Dua kes perlanggaran.

3. Mengira Linear Temporal Logic Plus

Kami menyemak pengiraan logik temporal linear tambah (cLTL+) dan serpihannya yang dipanggil logik temporal pengiraan (cLTL) yang dicadangkan untuk menerangkan spesifikasi untuk sistem berbilang robot [21]. Kepuasan formula cLTL+ pada asalnya ditakrifkan untuk urutan tak terhingga, tetapi di sini kami mengubah suai semantik tersebut ke atas jujukan terhingga, merujuk kepada \(\mbox{LTL}_f\) [29], [30].

cLTL+ ialah logik dua lapisan yang terdiri daripada satu logik dalaman, yang digunakan untuk menerangkan spesifikasi yang dipenuhi oleh robot tunggal, dan logik luar, yang digunakan untuk menerangkan spesifikasi mengenai bilangan robot yang diperlukan yang memenuhi logik dalaman. Formula logik dalaman atas set \(AP\) proposisi atom ditakrifkan secara rekursif seperti berikut.

\[\begin{equation*} \phi' ::= \mbox{True} \ | \ a \ | \ \neg \phi' \ | \ \phi'_1 \wedge \phi'_2 \ | \ \bigcirc \phi' \ | \ \phi'_1 \ \mathcal{U} \ \phi'_2 , \tag{2} \end{equation*}\]

di mana \(a \in AP\) ialah proposisi atom dan \(\phi'\), \(\phi'_1\), dan \(\phi'_2\) adalah formula logik dalaman. Simbol-simbol tersebut \(\neg\), \(\wedge\), \(\bigcirc\), dan \(\mathcal{U}\) sepadan dengan pengendali Boolean Penafian and konjungsi, dan pengendali temporal seterusnya and sehingga, masing-masing. Pengendali lain yang biasa digunakan boleh diperoleh daripada pengendali ini, seperti perpecahan (\(\phi'_1 \vee \phi'_2 \doteq \neg (\neg \phi'_1 \wedge \neg \phi'_2)\)), akhirnya (\(\diamondsuit \phi' \doteq \mbox{True} \ \mathcal{U} \ \phi'\)), sentiasa (\(\square \phi' \doteq \neg (\diamondsuit \neg \phi')\)), dsb. Set semua formula logik dalaman yang ditakrifkan oleh (2) dilambangkan dengan \(\Phi'\). Kepuasan logik dalaman \(\phi'\) dengan jejak yang terhad \(\rho \in (2^{AP})^h\) pada masa \(t \in [h-1]\), yang dilambangkan dengan \(\rho, t \models \phi'\), ditakrifkan seperti berikut, di mana \(h\) ialah panjang surih.

  • 1).  \(\rho, t \models \mbox{True}\);
  • 2). Untuk sebarang proposisi atom \(a \in AP\), \(\rho, t \models a\) jika dan hanya jika \(a \in \rho \langle t \rangle\);
  • 3).  \(\rho, t \models \phi'_1 \wedge \phi'_2\) jika dan hanya jika \(\rho, t \models \phi'_1\) and \(\rho, t \models \phi'_2\);
  • 4).  \(\rho, t \models \neg \phi'\) jika dan hanya jika \(\rho, t \nvDash \phi'\);
  • 5).  \(\rho, t \models \bigcirc \phi'\) jika dan hanya jika \(t<h-1\) and \(\rho, t+1 \models \phi'\);
  • 6).  \(\rho, t \models \phi'_1\ \mathcal{U} \ \phi'_2\) jika dan hanya jika ada \(l(0 \leq l \leq h-1-t)\) seperti itu \(\rho, t+l \models \phi'_2\) and \(\rho, t+l' \models \phi'_1\) untuk semua \(l'(0 \leq l' < l)\).

Proposisi atom dipanggil a cadangan pengiraan temporal (tcp) digunakan dalam sintaks formula logik luar. Cadangan pengiraan temporal \(tcp = [\phi', m, gset] \in \Phi' \times \mathbb{N} \times 2^G\) ialah proposisi atom yang benar jika bilangan robot yang memenuhi formula logik dalaman \(\phi'\) dan milik \(g \in gset\) sekurang-kurangnya \(m\). Formula logik luar ke atas set \(AP\) proposisi atom ditakrifkan secara rekursif seperti berikut.

\[\begin{equation*} \mu' ::= \mbox{True} \ | \ tcp \ | \ \neg \mu' \ | \ \mu'_1 \wedge \mu'_2 \ | \ \bigcirc \mu' \ | \ \mu'_1 \ \mathcal{U} \ \mu'_2 , \tag{3} \end{equation*}\]

di mana \(tcp\) ialah usul pengiraan temporal dan \(\mu'\), \(\mu'_1\), dan \(\mu'_2\) adalah formula logik luar. Semantik formula logik luar ditakrifkan untuk pengumpulan jejak. Kepuasan formula cLTL+ \(\mu'\) dengan pengumpulan jejak \(P\) pada masa \(t \in [h-1]\), yang dilambangkan dengan \(P, t \models \mu'\), ditakrifkan seperti berikut.

  • 1).  \(P, t \models \mbox{True}\);
  • 2). untuk sebarang cadangan pengiraan temporal \(tcp = [\phi', m, gset] \in \Phi' \times \mathbb{N} \times 2^G\), \(P, t \models tcp\) jika dan hanya jika \(|\{(n, g)| g \in gset, n \in N^g, \rho^g_n, t \models \phi' \}| \geq m\);
  • 3).  \(P, t \models \mu'_1 \wedge \mu'_2\) jika dan hanya jika \(P, t \models \mu'_1\) and \(P, t \models \mu'_2\);
  • 4).  \(P, t \models \neg \mu'\) jika dan hanya jika \(P, t \nvDash \mu'\);
  • 5).  \(P, t \models \bigcirc \mu'\) jika dan hanya jika \(t<h-1\) and \(P, t+1 \models \mu'\);
  • 6).  \(P, t \models \mu'_1\ \mathcal{U} \ \mu'_2\) jika dan hanya jika ada \(l(0 \leq l \leq h-1-t)\) seperti itu \(P, t+l \models \mu'_2\) and \(P, t+l' \models \mu'_1\) untuk semua \(l'(0 \leq l' < l)\).

cLTL ialah serpihan cLTL+ di mana logik dalaman dihadkan kepada sintaks berikut.

\[\begin{equation*} \phi' ::= a, \tag{4} \end{equation*}\]

di mana \(a\in AP\) adalah proposisi atom.

4. Masalah Perancangan Laluan

Kami menganggap masalah perancangan laluan untuk sistem berbilang robot heterogen yang terdiri daripada berbilang kumpulan untuk memenuhi spesifikasi yang diwakili oleh kerja dan beberapa kekangan sementara. Kerja ini dilakukan oleh robot tunggal. Kami menganggap bahawa kerja diwakili oleh sepasang sel permulaan dan sel sasaran, yang bermaksud bahawa robot memulakan kerja di sel permulaan dan menyelesaikannya apabila robot mencapai sel sasaran. Ambil perhatian bahawa spesifikasi mungkin memerlukan kerja dilakukan beberapa kali. Sebagai contoh, kami mempertimbangkan kes di mana terdapat lima pakej pada sel menatap yang dihantar ke sel sasaran dan setiap robot boleh menghantar satu pakej sekaligus. Kemudian, Penghantaran pakej dari sel permulaan ke sel sasaran adalah kerja dan spesifikasinya ialah kerja dilakukan lima kali. Contoh kekangan temporal ialah "tiada robot memasuki sel yang tidak selamat". Spesifikasi diberikan kepada setiap kumpulan tetapi tidak kepada setiap robot. Oleh itu, kami menentukan kedua-dua tugasan kerja kepada robot dan perancangan laluan untuk robot yang diberikan.

Kami menganggap bahawa kekangan temporal diterangkan oleh cLTL. Kerja tidak boleh diterangkan oleh cLTL tetapi oleh cLTL+. Oleh itu, spesifikasi dengan kerja dan pengiraan temporal diterangkan oleh cLTL+ dan memerlukan banyak masa pengiraan untuk mengira laluan robot. Untuk mengurangkan masa pengiraan, kami memperkenalkan jenis proposisi atom yang baru dipanggil a \(work\) dan tentukan logik novel yang dipanggil mengira LTL dengan kerja (cLTLw) itu adalah lanjutan daripada cLTL. Kemudian, menggunakan logik yang dicadangkan, kami merumuskan masalah perancangan laluan di bawah spesifikasi dengan kerja dan kekangan temporal.

4.1 Satu Kerja

Kami memberikan perwakilan rasmi karya seperti berikut.

Definisi 3: Kerja \(w\) ditakrifkan oleh sepasang proposisi atom \(w = (a^s_{w}, a^c_{w})\), Di mana \(a^s_{w} \in AP_S\) ialah proposisi atom “permulaan kerja \(w\)"Dan \(a^c_{w} \in AP_S\) ialah proposisi atom “penyelesaian kerja \(w\)".

Anggap bahawa \([\hspace{-1.5pt}[a^s_{w} ]\hspace{-1.5pt}]^g \cap [\hspace{-1.5pt}[a^c_{w} ]\hspace{-1.5pt}]^g = \emptyset\) untuk setiap \(g \in G\). Untuk kesederhanaan, untuk setiap \(g \in G\), \([\hspace{-1.5pt}[a^s_w ]\hspace{-1.5pt}]^g \neq \emptyset\) bererti \([\hspace{-1.5pt}[a^c_w ]\hspace{-1.5pt}]^g \neq \emptyset\). Biarkan \(W\) menjadi satu set kerja yang terhad. Setiap kerja diwakili oleh sepasang proposisi atom "permulaan kerja" dan "penyiapan kerja" dan merupakan perwakilan padat bagi spesifikasi yang berkaitan dengan dua sel. Perkhidmatan penghantaran pakej [27], [28] adalah contoh tipikal kerja.

4.2 Mengira LTL dengan Kerja

Kami mencadangkan logik novel yang dipanggil mengira logik temporal linear dengan kerja (cLTLw), di mana kerja yang ditakrifkan dalam Definisi 3 dianggap seperti proposisi atom. cLTLw terdiri daripada dua LTL dipanggil cLTLw segera and cLTLw terkumpul. Atas jejak yang panjangnya \(h\), formula cLTLw segera dinilai berdasarkan surih masa hadapan daripada masa semasa, manakala formula cLTLw terkumpul dinilai berdasarkan surih lalu sehingga masa semasa. Kedua-dua cLTLw segera dan cLTLw terkumpul adalah logik dua lapisan yang terdiri daripada logik dalam dan logik luar. Yang pertama menerangkan kerja yang dilakukan oleh robot tunggal dan proposisi atom yang digunakan dalam logik luar. Yang terakhir menerangkan spesifikasi mengenai bilangan robot yang diperlukan yang terlibat dalam kerja-kerja dan kekangan temporal untuk kumpulan robot. Sintaks logik dalaman bagi cLTLw segera dan terkumpul adalah biasa, manakala logik luarnya berbeza.

Sintaks logik dalaman cLTLw ialah lanjutan daripada cLTL yang ditakrifkan oleh (4) dengan memperkenalkan tiga operator temporal baharu yang berkaitan dengan kerja, iaitu, ia ditakrifkan dalam satu set \(AP\) proposisi atom dan satu set \(W\) karya seperti berikut:

\[\begin{equation*} \phi ::= a \ | \ \mathcal{P} w \ | \ \mathcal{S} w \ | \ \mathcal{C} w , \tag{5} \end{equation*}\]

di mana \(a \in AP\) ialah proposisi atom dan \(w \in W\) adalah kerja. Simbol-simbol tersebut \(\mathcal{P}\), \(\mathcal{S}\), dan \(\mathcal{C}\) sepadan dengan operator temporal \(perform\), \(start\), dan \(complete\), masing-masing. Dalam perkara berikut, pengendali ini akan dipanggil pengendali kerja. Set semua formula logik dalaman cLTLw yang ditakrifkan oleh (5) dilambangkan dengan \(\Phi\). Ambil perhatian bahawa operasi logik konvensional seperti konjungsi dan penolakan tidak digunakan dalam formula logik dalaman, yang sama dengan sintaks cLTL. Kepuasan formula logik dalaman \(\phi\) atas jejak yang terhad \(\rho \in (2^{AP})^h\) pada masa \(t \in [h-1]\) dilambangkan dengan \(\rho, t \models \phi\), Di mana \(h\) ialah panjang \(\rho\). Semantik rumus logik dalaman ditakrifkan seperti berikut:

  • 1). Untuk sebarang proposisi atom \(a \in AP\), \(\rho, t \models a\) jika dan hanya jika \(a \in \rho \langle t \rangle\);
  • 2).  \(\rho, t \models \mathcal{P} w\) jika dan hanya jika ada \(l(0 \leq l \leq t)\) seperti itu \(\rho, l \models a^s_w\) and \(\rho, l' \nvDash a^c_w\) bagi apa apa \(l' (l < l' \leq t)\);
  • 3).  \(\rho, t \models \mathcal{S} w\) jika dan hanya jika \(\rho, t \models a^s_w \wedge (t > 0 \rightarrow \rho, t - 1 \nvDash \mathcal{P} w)\);
  • 4).  \(\rho, t \models \mathcal{C} w\) jika dan hanya jika \(t > 0 \wedge \rho, t \models a^c_w \wedge \rho, t - 1 \models \mathcal{P} w\).

Secara intuitif, operator perform adalah benar jika robot telah memulakan kerja atau sedang melaksanakannya. Permulaan dan operator lengkap adalah benar jika robot telah memulakan dan menyelesaikan kerja masing-masing. Pengendali ini diilhamkan oleh pengendali masa lalu [31].

Sebagai contoh, kami menganggap jejak terhingga

\[\rho = \rho \langle 0 \rangle \rho \langle 1 \rangle \rho \langle 2 \rangle \rho \langle 3 \rangle =\{a^s_w\}\{a^c_w\}\{a^s_w\}\{a^c_w\}.\]

Kemudian, \(\mathcal{P} w\) and \(\mathcal{S} w\) adalah benar pada \(t=0, 2\) and \(\mathcal{C} w\) adalah benar pada \(t=1, 3\). Sebaliknya, kami menganggap jejak

\[\rho = \rho \langle 0 \rangle \rho \langle 1 \rangle \rho \langle 2 \rangle \rho \langle 3 \rangle =\{a^s_w\}\{a^s_w\}\{a^c_w\}\{a^c_w\}.\]

Kemudian, \(\mathcal{S} w\) adalah benar pada \(t=0\) and \(\mathcal{C} w\) adalah benar pada \(t=2\) dan tidak juga \(\mathcal{S} w\) tidak \(\mathcal{C} w\) adalah benar pada \(t=1, 3\). \(\mathcal{P} w\) adalah benar pada \(t=0, 1\). Perhatikan bahawa \(\rho, t \models \mathcal{C} w\) tidak pernah benar pada masanya \(t=0\). Jika \(\rho, t \models \mathcal{C} w\), robot berpuas hati \(a^c_w\) at \(t\) and \(a^s_w\) at \(t' (< t)\). Oleh itu, bilangan robot yang bergerak dari negeri itu \(s_1 \in [\hspace{-1.5pt}[a^s_w ]\hspace{-1.5pt}]\) kepada negeri \(s_2 \in [\hspace{-1.5pt}[a^c_w ]\hspace{-1.5pt}]\) adalah sama dengan robot yang memuaskan \(\mathcal{C} w\).

Dari segi logik luar cLTLw, proposisi pengiraan temporal (tcp) cLTL+ menerangkan kumpulan robot yang akan dinyatakan secara eksplisit [21]. Logik luar cLTLw segera dan cLTLw terkumpul dipanggil logik luar segera dan juga logik luar terkumpul, masing-masing. Pertama, kami mentakrifkan sintaks logik luar segera dan memperkenalkan proposisi yang dipanggil an tcp dilanjutkan \(tcp_{ins} = [\phi, m, gset] \in \Phi \times \mathbb{N} \times 2^G\) (tcp segera) yang mengira bilangan robot dalam kumpulan \(g \in gset\) memenuhi formula logik dalaman \(\phi\). Formula logik luar segera atas satu set \(AP\) proposisi atom dan satu set \(W\) kerja ditakrifkan secara rekursif seperti berikut:

\[\begin{equation*} \mu ::= \mbox{True} \ | \ tcp_{ins} \ | \ \neg \mu \ | \ \mu_1 \wedge \mu_2 \ | \ \bigcirc \mu \ | \ \mu_1 \ \mathcal{U} \ \mu_2 , \tag{6} \end{equation*}\]

di mana \(tcp_{ins}\) ialah tcp segera dan \(\mu\), \(\mu_1\), dan \(\mu_2\) ialah formula logik luar segera. Simbol-simbol tersebut \(\neg\), \(\wedge\), \(\bigcirc\), dan \(\mathcal{U}\) sepadan dengan pengendali Boolean Penafian and konjungsi, dan pengendali temporal seterusnya and sehingga, masing-masing. Pengendali lain yang biasa digunakan boleh diperoleh daripada pengendali ini, seperti perpecahan (\(\phi_1 \vee \phi_2 \doteq \neg (\neg \phi_1 \wedge \neg \phi_2)\)), akhirnya (\(\diamondsuit \phi \doteq \mbox{True} \ \mathcal{U} \ \phi\)), sentiasa (\(\square \phi \doteq \neg (\diamondsuit \neg \phi)\)), dsb. Semantik formula logik luar segera ditakrifkan untuk pengumpulan jejak. Kepuasan formula cLTLw segera \(\mu\) dengan pengumpulan jejak \(P\) pada masa \(t \in [h-1]\) dilambangkan dengan \(P, t \models \mu\) dan ditakrifkan seperti berikut:

  • 1).  \(P, t \models \mbox{True}\);
  • 2). untuk \(tcp_{ins} = [\phi, m, gset] \in \Phi \times \mathbb{N} \times 2^G\), \(P, t \models tcp_{ins}\) jika dan hanya jika \(|\{(n, g)| g \in gset, n \in N^g, \rho^g_n, t \models \phi \}| \geq m\);
  • 3).  \(P, t \models \phi_1 \wedge \phi_2\) jika dan hanya jika \(P, t \models \phi_1\) and \(P, t \models \phi_2\);
  • 4).  \(P, t \models \neg \phi\) jika dan hanya jika \(P, t \nvDash \phi\);
  • 5).  \(P, t \models \bigcirc \phi\) jika dan hanya jika \(t<h-1\) and \(P, t+1 \models \phi\);
  • 6).  \(P, t \models \phi_1\ \mathcal{U} \ \phi_2\) jika dan hanya jika ada \(l(0 \leq l \leq h-1-t)\) seperti itu \(P, t+l \models \phi_2\) and \(P, t+l' \models \phi_1\) untuk semua \(l'(0 \leq l' < l)\).

Dalam logik luar terkumpul, tcp lanjutan \(tcp_{acc} = [\phi, m, gset] \in \Phi \times \mathbb{N} \times 2^G\) (tcp terkumpul) ialah cadangan yang mengira bilangan kali robot dalam kumpulan \(g \in gset\) memenuhi formula logik dalaman \(\phi\) mengikut masa tertentu \(t\). Formula logik luar terkumpul ke atas set \(AP\) proposisi atom dan satu set \(W\) kerja ditakrifkan secara rekursif seperti berikut:

\[\begin{equation*} \theta ::= \ tcp_{acc} \ | \ \neg \theta \ | \ \theta_1 \wedge \theta_2 , \tag{7} \end{equation*}\]

di mana \(tcp_{acc}\) ialah tcp terkumpul dan \(\theta\), \(\theta_1\), dan \(\theta_2\) adalah formula logik luar terkumpul. Ambil perhatian bahawa operator temporal tidak ditakrifkan dalam logik luar terkumpul. Semantik formula logik luar terkumpul ditakrifkan untuk pengumpulan jejak. Kepuasan formula cLTLw terkumpul \(\theta\) dengan pengumpulan jejak \(P\) pada masa \(t \in [h-1]\) dilambangkan dengan \(P, t \models \theta\) dan ditakrifkan seperti berikut:

  • 1). untuk \(tcp_{acc} = [\phi, m, gset] \in \Phi \times \mathbb{N} \times 2^G\), \(P, t \models tcp_{acc}\) jika dan hanya jika \(|\{(n, g, t')| g \in gset, n \in N^g, t' \leq t, \rho^g_n, t' \models \phi \}| \geq m\);
  • 2).  \(P, t \models \theta_1 \wedge \theta_2\) jika dan hanya jika \(P, t \models \theta_1\) and \(P, t \models \theta_2\);
  • 3).  \(P, t \models \neg \theta\) jika dan hanya jika \(P, t \nvDash \theta\).

Jelas sekali, sebarang formula cLTLw ditukar kepada formula cLTL+. Walau bagaimanapun, kami tidak boleh menggunakan operator temporal \(\bigcirc\) and \({\mathcal U}\), dan pengendali Boolean \(\land\) and \(\neg\) dalam logik dalaman cLTLw, yang merupakan sekatan yang sama bagi cLTL, manakala kita boleh menggunakannya dalam logik dalaman cLTL+. Jadi, kuasa ungkapan cLTLw adalah kurang daripada cLTL+.

4.3 Rumusan Masalah

Kami mempertimbangkan masalah perancangan laluan berikut untuk sistem berbilang robot heterogen.

Masalah 1: Diberi panjang \(h\), satu set semua kumpulan \(G\), sistem peralihan \(T^{g}\) untuk setiap \(g \in G\), set keadaan awal \(\{s^g_n \langle 0 \rangle | g \in G, n \in N^g\}\) untuk semua robot, formula cLTLw segera \(\mu\), dan formula cLTLw terkumpul \(\theta\) lebih \(AP\) and \(W\), mensintesis koleksi \(\Pi\) trajektori untuk semua robot supaya fungsi kos tertentu \(Cost\) diminimumkan di bawah kekangan \(P, 0 \models \mu\), dan \(P, h-1 \models \theta\) tanpa perlanggaran, di mana \(P\) ialah koleksi jejak yang sepadan dengan \(\Pi\).

5. Kaedah Cadangan

Dalam bahagian ini, kami menyelesaikan Masalah 1 dengan menukarnya kepada masalah pengaturcaraan linear integer (ILP).

5.1 Pengekodan Dinamik

Sistem peralihan yang diberikan \(T^g\) daripada robot kumpulan \(g \in G\), kami mentakrifkan pemalar binari \(A^{g}(s_1, \sigma, s_2) \in \{0, 1\}\) untuk setiap \(s_1, s_2 \in S^{g}\) dan masing-masing \(\sigma \in \Sigma^{g}\) seperti berikut. \(A^{g}(s_1, \sigma, s_2) = 1\) jika dan hanya jika \(\delta^g(s_1, \sigma) = s_2\). Kami memperkenalkan pembolehubah binari \(u^g(t, s, \sigma)\) untuk mewakili pengedaran negeri dan input robot pada setiap masa. \(u^g(t, s, \sigma) = 1\) jika dan hanya jika wujud robot dalam kumpulan \(g\) iaitu dalam negeri \(s \in S^g\) dengan memilih input \(\sigma \in \Sigma^g\) pada masa \(t \in [h-1]\). Perhatikan bahawa, walaupun \(u^g(t, s, \sigma)\) at \(h - 1\) ditentukan, kami tidak mengambil kira input pada masa \(h-1\). Diberikan \(A^g(s, \sigma, s')\) bersamaan dengan \(T^g\), dan satu set keadaan awal \(\{s^g_n \langle 0 \rangle | n \in N^g \}\) daripada semua robot dalam kumpulan \(g\), dinamik robot dalam kumpulan \(g \in G\) diwakili seperti berikut. Untuk setiap \(s \in S^g\),

\[\begin{align} & \sum_{\sigma \in \Sigma^g} u^g(0, s, \sigma) = |\{ n | s^g_n \langle 0 \rangle = s, n \in N^g \}|, \tag{8} \\ & u^g(t, s, \sigma) \leq \sum_{s' \in S^g} A^g(s, \sigma, s') \ (t \in [ h-1 ], \sigma \in \Sigma^g), \tag{9} \\ & \sum_{\sigma \in \Sigma^g} u^g(t+1, s, \sigma) \nonumber \\ & \hspace{2mm} = \sum_{ s' \in S^g, \sigma' \in \Sigma^g } A^g(s', \sigma', s) u^g(t, s', \sigma') \ (t \in [ h-2 ]). \tag{10} \end{align}\]

Persamaan (8) ialah pengekodan bagi keadaan awal, Pers. (9) bermaksud bahawa, jika \(\delta^g(s, \sigma)\) tidak ditentukan, maka \(u^g(t, s, \sigma)=0\), dan Pers. (10) menjamin pemeliharaan bilangan robot pada setiap masa \(t \in [h-1]\).

5.2 Pengekodan Kekangan cLTLw

Mari \(b', b_0, \ldots, b_I\) Untuk \(I \in \mathbb{N}^+\) menjadi pembolehubah Boolean. Kemudian, kata hubung (11) ditukarkan kepada ketaksamaan linear seperti berikut.

\[\begin{align} b' = b_0 \wedge \ldots \wedge b_I, \tag{11} \end{align}\]

jika dan hanya jika

\[\begin{align} b' &\leq b_i \ (i \in [ I ]), \tag{12} \\ b' &\geq \sum_{i \in [ I ]} b_i - I. \tag{13} \end{align}\]

Begitu juga, penukaran cerai (14) kepada ketaksamaan linear adalah seperti berikut.

\[\begin{align} b' = b_0 \vee \ldots \vee b_I, \tag{14} \end{align}\]

jika dan hanya jika

\[\begin{align} b' &\geq b_i \ (i \in [ I ]), \tag{15} \\ b' &\leq \sum_{i \in [ I ]} b_i. \tag{16} \end{align}\]

Untuk pengekodan proposisi atom, kami takrifkan \(V^g_a(s) \in \{ 0, 1 \}\) untuk setiap \(a \in AP_S\) dan masing-masing \(s \in S^g\), dan \(V^g_a(s, \sigma) \in \{ 0, 1 \}\) untuk setiap \(a \in AP_\Sigma\), masing-masing \(s \in S^g\), dan masing-masing \(\sigma \in \Sigma^g\) seperti berikut. Untuk setiap \(g \in G\),

\[\begin{aligned} V^g_a(s) = 1 &\mbox{ if and only if }a \in L^g_S(s), \\ V^g_a(s, \sigma) = 1 &\mbox{ if and only if } a \in L^g_\Sigma(s, \sigma). \end{aligned}\]

Pengekodan proposisi atom dan penafian \(\neg\) adalah sama dengan yang terdapat dalam cLTL+ dan ditinggalkan. Lihat Persamaan. (A\(\cdot\)7)-(A\(\cdot\)11) Lampiran untuk pengekodan.

Kami memperkenalkan pembolehubah binari \(p^g_w(t, s)\), \(s^g_w(t, s)\), \(c^g_w(t, s)\in \{0, 1\}\) untuk setiap kerja \(w\) seperti itu \(p^g_w(t, s) = 1\), \(s^g_w(t, s) = 1\), dan \(c^g_w(t, s) = 1\) jika dan hanya jika terdapat robot dalam kumpulan \(g\in G\) tinggal di negeri itu \(s \in S^g\) pada masa \(t\) jejak siapa \(\rho\) memuaskan \(\rho, t \models \mathcal{P} w\), \(\rho, t \models \mathcal{S} w\), dan \(\rho, t \models \mathcal{C} w\), masing-masing. Kemudian, pengendali kerja dikodkan seperti berikut. Untuk setiap \(t \in [ h-2 ]\) dan masing-masing \(s \in S^g\),

\[\begin{align} & p^g_w(0, s) = s^g_w(0, s), \tag{17} \\ & s^g_w(0, s) = V^g_{a^s_w}(s) \sum_{\sigma \in \Sigma^g} u^g(0, s, \sigma), \tag{18} \\ & c^g_w(0, s) = 0, \tag{19} \\ &\nonumber p^g_w(t + 1, s) = s^g_w(t + 1, s) \\ &\nonumber \vee \Bigg( \bigg( \sum_{s' \in S^g, \sigma \in \Sigma^g} A^g(s', \sigma, s) \Big( u^g(t, s', \sigma) \wedge p^g_w(t, s') \Big) \bigg)\\ &\wedge \Big( 1-c^g_w(t + 1, s) \Big) \Bigg), \tag{20} \\ &\nonumber s^g_w(t + 1, s) = \Bigg( 1 - \\ &\nonumber \sum_{s' \in S^g, \sigma \in \Sigma^g} A^g(s', \sigma, s) \Big( u^g(t, s', \sigma) \wedge p^g_w(t, s') \Big) \Bigg)\\ & \wedge \Bigg( V^g_{a^s_w}(s) \sum_{\sigma \in \Sigma^g} u^g(t + 1 , s, \sigma) \Bigg), \tag{21} \\ &\nonumber c^g_w(t + 1, s) = \Bigg( V^g_{a^c_w}(s) \sum_{\sigma \in \Sigma^g} u^g(t + 1 , s, \sigma) \Bigg)\\ &\wedge \Bigg( \sum_{s' \in S^g, \sigma \in \Sigma^g} A^g(s', \sigma, s) \Big( u^g(t, s', \sigma) \wedge p^g_w(t, s') \Big) \Bigg). \tag{22} \end{align}\]

Persamaan (17) mewakili bahawa, jika robot memulakan kerja pada masa \(t=0\), kemudian robot melakukan kerja. Persamaan (18) mewakili bahawa, jika robot memenuhi proposisi atom "permulaan kerja" pada masa \(t=0\), kemudian robot memulakan kerja. Persamaan (19) mewakili bahawa, \(\rho, t \models \mathcal{C} w\) tidak pernah benar pada masanya \(t=0\). Persamaan (20) mewakili bahawa, untuk setiap kerja \(w \in W\), jika robot itu memuaskan \(\mathcal{P} w\) pada masa \(t+1\) atau jika robot itu memuaskan \(\mathcal{P} w\) pada masa \(t\) dan tidak memuaskan \(\mathcal{C} w\) pada masa \(t+1\), kemudian robot melakukan kerja pada masa \(t+1\). Persamaan (21) mewakili bahawa, untuk setiap \(w \in W\), jika robot itu memuaskan \(a_w^s\) pada masa \(t+1\) dan tidak memuaskan \(\mathcal{P} w\) pada masa \(t\), kemudian robot memulakan kerja pada masanya \(t+1\). Persamaan (22) mewakili bahawa, untuk setiap kerja \(w \in W\), jika robot itu memuaskan \(a_w^c\) pada masa \(t+1\) and \(\mathcal{P} w\) pada masa \(t\), kemudian robot menyelesaikan kerja pada masanya \(t+1\). Kerana bilangan robot di setiap negeri \(s \in S\) adalah paling banyak satu, untuk setiap satu \(s \in S^g\) dan masing-masing \(t \in [h-1]\), \(\sum_{s' \in S^g, \sigma \in \Sigma^g} A^g(s', \sigma, s) \Big( u^g(t, s', \sigma) \wedge p^g_w(t, s') \Big)\) and \(\sum_{\sigma \in \Sigma^g} u^g(t + 1 , s, \sigma)\) adalah \(0\) or \(1\). Oleh itu, Pers. (20)-(22) ditakrifkan dengan baik. Formula logik dalaman digunakan dalam tcp segera dan tcp terkumpul. Untuk mengira bilangan robot yang memenuhi formula logik dalaman \(\phi\) pada masa \(t\), kami memperkenalkan pembolehubah integer bukan negatif \(f^g_{\phi}(t) \in \mathbb{N}\), yang mewakili bilangan robot dalam kumpulan \(g\) memenuhi formula logik dalaman \(\phi\) pada masa \(t\). Untuk setiap \(a \in AP_S\) dan masing-masing \(t \in [ h-1 ]\),

\[\begin{equation*} f^g_a(t) = \sum_{s \in S^g, \sigma \in \Sigma^g} V^g_a(s) u^g(t, s, \sigma). \tag{23} \end{equation*}\]

Bagi setiap \(a \in AP_{\Sigma}\) dan masing-masing \(t \in [ h-2 ]\),

\[\begin{equation*} f^g_a(t) = \sum_{s \in S^g, \sigma \in \Sigma^g} V^g_a(s, \sigma) u^g(t, s, \sigma), \tag{24} \end{equation*}\]

dan untuk setiap satu \(a \in AP_{\Sigma}\),

\[\begin{equation*} f^g_a(h-1) = 0. \tag{25} \end{equation*}\]

Bagi setiap \(w \in W\) dan masing-masing \(t \in [ h-1 ]\),

\[\begin{align} f^g_{\mathcal{P} w}(t) &= \sum_{s \in S^g} p^g_w(t, s), \tag{26} \\ f^g_{\mathcal{S} w}(t) &= \sum_{s \in S^g} s^g_w(t, s) , \tag{27} \\ f^g_{\mathcal{C} w}(t) &= \sum_{s \in S^g} c^g_w(t, s) . \tag{28} \end{align}\]

Untuk formula logik luar segera, kami memperkenalkan pembolehubah binari \(y^{\mu}(t) \in \{ 0, 1 \}\) untuk setiap \(t \in [ h-1 ]\) seperti itu \(y^{\mu}(t) = 1\) jika dan hanya jika \(P, t \models \mu\). Kemudian, tcp segera \(\mu = tcp_{ins} = [\phi, m, gset]\) dikodkan oleh ketaksamaan berikut untuk setiap satu \(t \in [ h-1 ]\).

\[\begin{align} m > \sum_{g \in gset} f^g_{\phi}(t) - M y^{\mu}(t) \geq m - M, \tag{29} \end{align}\]

di mana \(M\) adalah nombor positif yang cukup besar memuaskan \(M \geq |\{ n | g \in gset, n \in N^g \}| + 1\). Perhatikan bahawa, jika \(y^\mu(t) = 1\), maka ketaksamaan di sebelah kanan berkurangan kepada \(\sum_{g \in gset} f^g_{\phi}(t) \geq m\). Lebih-lebih lagi, ketidaksamaan di sebelah kiri berpuas hati. Sebaliknya, jika \(y^\mu(t) = 0\), maka ketidaksamaan berkurangan kepada \(m > \sum_{g \in gset} f^g_{\phi}(t)\). Oleh itu, \(y^{tcp_{ins}}(t) = 1\) jika dan hanya jika \(P, t \models tcp_{ins}\). Pengekodan pengendali lain diringkaskan dalam [32] dan ditinggalkan di sini. Kemudian, untuk formula cLTLw segera \(\mu\), set pembolehubah dan ketaksamaan yang digunakan untuk pengekodannya ditandakan dengan \(var(\mu)\) and \(ILP(\mu)\), masing-masing. Begitu juga, untuk kekangan formula logik luar terkumpul, kami memperkenalkan pembolehubah binari \(x^\theta \in \{ 0, 1 \}\) seperti itu \(x^\theta = 1\) jika dan hanya jika \(P, h-1 \models \theta\) untuk panjang yang diberikan \(h\). Tcp terkumpul \(\theta = tcp_{acc} = [\phi, m, gset]\) dikodkan oleh ketaksamaan berikut.

\[\begin{align} m > \sum_{g \in gset, t \in [ h-1 ]} f^g_{\phi}(t) - M x^\theta \geq m - M, \tag{30} \end{align}\]

di mana \(M\) adalah nombor positif yang cukup besar, khususnya, \(M \geq h |\{ n | g \in gset, n \in N^g \}| + 1\). Pengekodan pengendali lain, cth penolakan dan konjungsi, adalah sama seperti dalam logik luar segera. Kemudian, untuk formula cLTLw terkumpul \(\theta\), set pembolehubah dan ketaksamaan yang digunakan untuk pengekodannya ditandakan dengan \(var(\theta)\) and \(ILP(\theta)\), Masing-masing.

5.3 Pengekodan Pengelakan Perlanggaran

Kami menggunakan pengekodan kekangan cLTLw untuk mengelakkan perlanggaran kerana kami boleh menerangkan keadaan mengelakkan perlanggaran oleh cLTLw. Oleh kerana kita menganggap bahawa, untuk setiap sel dalam \(S\), paling banyak satu robot boleh kekal pada masa yang sama, kami mempunyai ketaksamaan berikut untuk mengelakkan perlanggaran pendua. Untuk setiap \(s \in S\) dan masing-masing \(t \in [ h-1 ]\),

\[\begin{align} \sum_{g \in \{g| g \in G, s \in S^g\}} \sum_{\sigma \in \Sigma^g} u^g(t, s, \sigma ) \leq 1 . \tag{31} \end{align}\]

Jika ada \(\sigma_1 \in \Sigma^{g_1}\) and \(\sigma_2 \in \Sigma^{g_2}\) seperti itu \(\delta^{g_1}(s_1, \sigma_1) = s_2, \delta^{g_2}(s_2, \sigma_2) = s_1\) Untuk \(s_1, s_2 \in S\) and \(g_1, g_2 \in G\), kami mengekodkan pengelakan perlanggaran swap oleh ketaksamaan berikut. Untuk setiap \(t \in [ h-1 ]\),

\[\begin{align} \nonumber &\sum_{\sigma \in \Sigma^{g_1}} A^{g_1}(s_1, \sigma, s_2) u^g(t, s_1, \sigma)\\ &\quad + \sum_{\sigma \in \Sigma^{g_2}} A^{g_2}(s_2, \sigma, s_1) u^g(t, s_2, \sigma_2) \leq 1 . \tag{32} \end{align}\]

5.4 Penukaran kepada Masalah ILP

Menggunakan pengekodan di atas, Masalah 1 ditukar kepada masalah ILP berikut.

Masalah 2: Diberi fungsi kos \(Cost\) yang pembolehubahnya \(\{ u^g(t, s, \sigma) | g \in G, t \in [ h-1 ], s \in S^g, \sigma \in \Sigma^g \}\), \(var(\mu)\), dan \(var(\theta)\). Cari nilai optimum mereka yang meminimumkan \(Cost\) tertakluk kepada Persamaan. (8)-(10), \(ILP(\mu)\), \(ILP(\theta)\), \(x^\theta = 1\), \(y^{\mu}(0) = 1\), dan Persamaan. (31) dan (32).

Urutan yang optimum \(\sigma^g_n \langle 0 \rangle, \ldots, \sigma^g_n \langle h-2 \rangle\) input bagi setiap robot \(n \in N^g\) daripada kumpulan \(g \in G\) Masalah 1 diperolehi oleh penyelesaian yang optimum \(\{ u^g(t, s, \sigma) | g \in G, t \in [ h-2 ], s \in S^g, \sigma \in \Sigma^g \}\) Masalah 2. Ingat bahawa sistem peralihan \(T^g\) adalah deterministik bagi setiap kumpulan \(g \in G\). Oleh itu, urutan yang optimum \(s^g_n \langle 1 \rangle \ldots s^g_n \langle h-1 \rangle\) keadaan bagi setiap robot ditentukan oleh \(\delta^g (s^g_n \langle t \rangle, \sigma^g_n \langle t \rangle) = s^g_n \langle t+1 \rangle\) untuk setiap \(t \in [h-2]\).

6. Contoh

Kami mempertimbangkan masalah perancangan laluan di ruang kerja dengan \(s_c \times s_c\) sel seperti yang ditunjukkan dalam Rajah 2 (\(s_c = 7\)), di mana panjang trajektori setiap robot adalah \(h\), \(G = \{g_1, g_2 \}\), \(|N^{g_1}| = |N^{g_2}| = N\), dan setiap robot boleh kekal atau bergerak ke mana-mana empat sel jiran melainkan ia meninggalkan ruang kerja pada setiap masa. Kami akan memanggil satu set sel a rantau. Kami mengenakan pengelakan perlanggaran yang ditunjukkan dalam Rajah 1 dan kekangan berikut.

Rajah 2  Ilustrasi ruang kerja dengan \(7\times 7\) sel-sel.

  • Robot masuk \(g_1\) mesti bergerak dari rantau R1 ke rantau R4 dan robot masuk \(g_2\) mesti pergi dari rantau R2 ke rantau R3 sekurang-kurangnya \(requ \in \mathbb{N}\) kali sambil mengelak lebih daripada \(proh \in \mathbb{N}\) robot yang tinggal di R5 pada masa yang sama.

Mari \(r_1, \ldots, r_5 \in AP_S\) menjadi proposisi atom yang tinggal di kawasan R1, …, R5, masing-masing. Kekangan diterangkan oleh \(P,0 \models \mu\) and \(P, h-1 \models \theta\), Di mana \(P\) ialah koleksi jejak robot dan \(\mu\) and \(\theta\) ialah formula cLTLw berikut.

\[\begin{align} \mu &= \square \neg [r_5, proh, G], \tag{33} \\ \theta &= [\mathcal{C} w_1, requ, \{g_1\}] \wedge [\mathcal{C} w_2, requ, \{g_2\}], \tag{34} \end{align}\]

di mana \(w_1 = (r_1, r_4)\in W\) and \(w_2 = (r_2, r_3) \in W\). Sebaliknya, kekangan itu juga diterangkan oleh \(P,0 \models \mu'\), Di mana \(\mu'\) ialah formula cLTL+ berikut.

\[\begin{align} \mu' &= \square \neg [r_5, proh, G] \nonumber \\ &\quad \land [(\diamondsuit r_4)\wedge(\neg r_4 \ \mathcal{U} \ r_1), requ,\{g_1\}] \nonumber \\ &\quad \land [(\diamondsuit r_3) \wedge (\neg r_3 \ \mathcal{U} \ r_2), requ, \{g_2\}]. \tag{35} \end{align}\]

Kami mengekodkan kekangan yang diberikan oleh Pers. (35) menggunakan kaedah yang dicadangkan dalam [21]. Lihat Lampiran untuk pengekodan semantik Pers. (2). Kami membandingkan kaedah berasaskan cLTLw dengan kaedah berasaskan cLTL+. Kami menganggap fungsi kos yang ditakrifkan oleh bilangan robot yang bergerak antara sel. Dalam kaedah berasaskan cLTLw, kami mempertimbangkan masalah pengoptimuman untuk meminimumkan fungsi kos berikut.

\[\begin{equation*} -\sum_{t = 0}^{h-1} \sum_{g \in G, s \in S} u^{g}(t, s, stay), \tag{36} \end{equation*}\]

di mana \(stay\) ialah input yang membuatkan robot kekal dalam sel yang sama. Fungsi kos ialah jumlah bilangan pemilihan input \(stay\) untuk semua robot. Oleh itu, secara intuitif, pengurangan fungsi kos sepadan dengan penindasan pergerakan berlebihan robot. Dalam simulasi, Kami menggunakan komputer dengan 1.8 GHz Intel Core i7 dan 16 GB RAM. Masalah ILP diselesaikan menggunakan Gurobi [33]. Kemudian, kami memperoleh purata masa pengiraan dan bilangan pembolehubah dengan menghasilkan 10 kes dengan keadaan awal yang berbeza untuk setiap \(s_c\in \{7,8,9,10,20,30\}\).

Keputusan ditunjukkan dalam Jadual 1. Pengiraan telah digugurkan pada 86400 saat dan masa pengiraan untuk kes ditetapkan kepada 86400 saat apabila kita mengira purata masa pengiraan dalam Jadual 1. Untuk \(s_c=20\) and \(s_c=30\), masalah berdasarkan formula cLTL+ tidak dapat diselesaikan kerana ingatan tidak mencukupi. Ditunjukkan bahawa masalah berdasarkan formula cLTLw mengambil masa pengiraan yang kurang dan mempunyai pembolehubah yang lebih sedikit daripada yang berdasarkan formula cLTL+ untuk semua kes. Ditunjukkan dalam Rajah 3 ialah contoh laluan semua robot untuk \(s_c=7\).

Jadual 1  Hasil simulasi.

Rajah 3  Contoh trajektori semua robot antara selang masa \([0,\ 9]\) di ruang kerja dengan \(7 \times 7\) sel, di mana bulatan merah dan biru mewakili robot dalam kumpulan 1 dan 2, masing-masing.

Kami menggunakan pembolehubah \(u^g(t,s,\sigma)\) yang mewakili pengedaran keadaan dan input robot. Bilangan pembolehubah \(u^g(t,s,\sigma)\) is \(h\sum_{g\in G}|S^g|\cdot|\Sigma^g|\) dan tidak bergantung pada bilangan robot. Sebaliknya, dalam pengekodan cLTL+, kami memperkenalkan pembolehubah yang mewakili trajektori setiap robot secara eksplisit, iaitu \(w_n^g(t,s)\) dalam Lampiran, dan bilangan mereka ialah \(h\sum_{g\in G}|S^g|\cdot |N^g|\)1. Oleh itu, kami menjangkakan bahawa bilangan pembolehubah yang digunakan dalam pengekodan berdasarkan cLTLw adalah kurang daripada yang berdasarkan cLTL+ apabila bilangan robot cukup besar. Tetapi, pembolehubah \(u^g(t,s,\sigma)\) jangan nyatakan keadaan semasa dan input semasa setiap robot secara eksplisit. Oleh itu, kita perlu mengira trajektori yang betul bagi setiap robot tanpa perlanggaran daripada pembolehubah \(u^g(t,s,\sigma)\) dengan andaian bahawa keadaan awal setiap robot diketahui. Oleh kerana, dalam pengekodan pengendali \({\mathcal P}\), \({\mathcal S}\), dan \({\mathcal C}\) diberikan oleh Persamaan. (17)-(22), pembolehubah pada masa yang lebih besar daripada \(t+1\) tidak muncul dan kami sentiasa boleh mengenal pasti semua trajektori robot dari \(u^g(t,s,\sigma)\). Walau bagaimanapun, pengekodan bagi \(\bigcirc\) and \({\mathcal U}\) memerlukan keadaan dan input robot pada masa akan datang. Lihat Persamaan. (A\(\cdot\)12) dan (A\(\cdot\)13) Lampiran untuk pengekodan mereka. Oleh itu, kita tidak boleh mengekod operator menggunakan pembolehubah \(u^g(t,s,\sigma)\).

7. Kesimpulan

Kami menganggap masalah perancangan laluan untuk sistem berbilang robot heterogen, di mana spesifikasi terdiri daripada kerja dan kekangan temporal. Untuk menerangkan spesifikasi secara ringkas, kami memperkenalkan logik baru yang dipanggil cLTLw, yang merupakan lanjutan daripada cLTL. Kemudian, kami menukar masalah itu kepada masalah pengaturcaraan linear integer (ILP). Kami menunjukkan bahawa bilangan pembolehubah yang digunakan dalam masalah ILP adalah kurang daripada itu dalam kaedah sedia ada menggunakan cLTL+. Melalui simulasi, kami menunjukkan bahawa masa pengiraan kaedah yang dicadangkan adalah lebih cepat daripada kaedah sedia ada. Ia adalah kerja masa depan untuk mempertimbangkan spesifikasi yang lebih rumit seperti pengumpulan dan penghantaran pakej.

Penghargaan

Kerja ini disokong sebahagiannya oleh Geran JSPS KAKENHI No. 21H01353, Jepun, dan Subsidi Penyelidikan Pache Universiti Nanzan IA-2 untuk tahun akademik 2023.

Rujukan

[1] S. Hoshino, H. Seki, Y. Naka, and J. Ota, “Multirobot coordination for flexible batch manufacturing systems experiencing bottlenecks,” IEEE Trans. Automat. Sci. Eng., vol.7, no.4, pp.887-901, 2010.
CrossRef

[2] J.P. Queralta, J. Taipalmaa, B.C Pullinen, V.K. Sarker, T.N. Gia, H. Tenhunen, M. Gabbouj, J. Raitoharju, and T. Westerlund, “Collaborative multi-robot search and rescue: Planning, coordination, perception, and active vision,” IEEE Access, vol.8, pp.191617-191643, 2020.
CrossRef

[3] Y. Rizk, M. Awad, and E.W. Tunstel, “Cooperative heterogeneous multi-robot systems: A survey,” ACM Comput. Survey, vol.52, no.2, pp.1-31, 2019.
CrossRef

[4] M. Luckcuck, M. Farrell, L.A. Dennis, C. Dixon, and M. Fisher, “Formal specification and verification of autonomous robotic systems: A survey,” ACM Comput. Surv., vol.52, no.5, pp.1-41, 2019.
CrossRef

[5] C. Mahulea, M. Kloetzer, and R. González, Path Planning of Cooperative Mobile Robots Using Discrete Event Models, IEEE Press, 2020.
CrossRef

[6] C. Belta, B. Yordanov, and E.A. Gol, Formal Methods for Discrete-Time Dynamical Systems, Springer, 2017.
CrossRef

[7] M. Kloetzer and C. Belta, “Automatic deployment of distributed teams of robots from temporal logic motion specifications,” IEEE Trans. Robot., vol.26, no.1, pp.48-61, 2010.
CrossRef

[8] K. Kobayashi, T. Nagami, and K. Hiraishi, “Optimal control of multi-vehicle systems with temporal logic constraints,” IEICE Trans. Fundamentals, vol.E98-A, no.2, pp.626-634, 2015.
CrossRef

[9] L. Lindemann, J. Nowak, L. Schönbächler, M. Guo, J. Tumova, and D.V. Dimarogonas, “Coupled multi-robot systems under linear temporal Llogic and signal temporal logic tasks,” IEEE Trans. Control Syst. Technol., vol.29, no.2, pp.858-865, 2021.
CrossRef

[10] A.T. Buyukkocak, D. Aksaray, and Y. Yazıcıoğlu, “Planning of heterogeneous multi-agent systems under signal temporal logic specifications with integral predicates,” IEEE Robot. Autom. Lett., vol.6, no.2, pp.1375-1382, 2021.
CrossRef

[11] K. Leahy, Z. Serlin, C.I. Vasile, A. Schoer, A.M. Jones, R. Tron, and C. Belta, “Scalable and robust algorithms for task-based coordination from high-level specifications (ScRATCHeS),” IEEE Trans. Robot., vol.38, no.4, pp.2516-2535, 2022.
CrossRef

[12] R. Yan, Z. Xu, and A. Julius, “Swarm signal temporal logic inference for swarm behavior analysis,” IEEE Robot. Autom. Lett., vol.4, no.3, pp.3021-3028, 2019.
CrossRef

[13] M. Guo and D.V. Dimaroganas, “Multi-agent plan reconfiguration under local LTL specifications,” The International Journal of Robotics Research, vol.34, no.2, pp.218-235, 2015.
CrossRef

[14] I. Filippidis, D.V. Dimaroganas, and K. Kyriakopoulos, “Decentralized multi-agent control from local LTL specifications,” Proc. 51st IEEE Conf. CDC, pp.6235-6240, 2012.
CrossRef

[15] J. Tumova and D.V. Dimaroganas, “Multi-agent planning under local LTL specifications and event-based synchronization,” Automatica, vol.70, pp.239-248, 2016.
CrossRef

[16] Y. Kantaros and M.M. Zavlanos, “Sampling-based optimal control synthesis for multirobot systems under global temporal tasks,” IEEE Trans. Autom. Control, vol.64, no.5, pp.1916-1931, 2018.
CrossRef

[17] M. Kloetzer and C. Mahulea, “Path planning for robotic teams based on LTL specifications and Petri net models,” Discrete Event Dyn. Syst., vol.30, pp.55-79, 2020.
CrossRef

[18] K. Leahy, A. Jone, and C.-I. Vasile, “Fast decomposition of temporal logic specifications for heterogeneous teams,” IEEE Robot. Autom. Lett., vol.7, no.2, pp.2297-2304, 2022.
CrossRef

[19] X. Luo and M.M. Zavlanos, “Temporal logic task allocation in heterogeneous multi-robot systems,” IEEE Trans. Robot., vol.38, no.6, pp.3602-3621, 2022.
CrossRef

[20] Z. Xu and A.A. Julius, “Census signal temporal logic inference for multiagent group behavior analysis,” IEEE Trans. Autom. Sci. Eng., vol.15, no.1, pp.264-277, 2018.
CrossRef

[21] Y.E. Sahin, P. Nilsson, and N. Ozay, “Multirobot coordination with counting temporal logics,” IEEE Trans. Robot., vol.36, no.4, pp.1189-1206, 2020.
CrossRef

[22] Y. Dumas, J. Derosiers, and F. Soumis, “The pickup and delivery problem with time windows,” European Journal of Operational Research, vol.54, pp.7-22, 1991.
CrossRef

[23] Y. Morihiro, T. Miyamoto, and S. Kumagai, “Routing autonomous vehicles in the improving initial task assignment and avoiding deadlock method,” IEICE Trans. Fundamentals, vol.E91-A, no.11, pp.3229-3236, Nov. 2008.
CrossRef

[24] T. Miyamoto and K. Inoue, “Local and random searches for dispatch and conflict-free routing problem of capacitated AGV systems,” Computres & IndustrialEngineering, vol.91, pp.1-9, 2016.
CrossRef

[25] Z. Chen, J. Alonso-Mora, X. Bai, D.D. Harabor, and P.J. Stuckey, “Integrated task assignment and path planning for capacitated multi-agent pickup and delivery,” IEEE Robot. Autom. Lett., vol.6, no.3, pp.5816-5823, 2021.
CrossRef

[26] K. Dorling, J. Heinrichs, G.G. Messier, and S. Magierowski, “Vehicle routing problems for drone delivery,” IEEE Trans. Syst., Man, Cybern., Syst., vol.47, no.1, pp.70-85, 2017.
CrossRef

[27] N. Mathew, S.L. Smith, and S.L. Waslander, “Planning paths for packages delivery in heterogeneous multirobot teams,” IEEE Trans. Autom. Sci. Eng., vol.12, no.4, pp.1298-1308, 2015.
CrossRef

[28] X. Bai, M. Cao, W. Yan, and S.S. Ge, “Efficient routing for precedence-constrained package delivery for heterogeneous vehicles,” IEEE Trans. Autom. Sci. Eng., vol.17, no.1, pp.248-260, 2020.
CrossRef

[29] G.D. Giacomo, E.M. Wolff, and M.Y. Vardi, “Linear temporal logic and linear dynamic logic on finite traces,” Proc. Twenty-Third International Joint Conference on Artificial Intelligence, pp.854-860, 2013.

[30] J. Li, G. Pu, Y. Zhang, M.Y. Vardi, and K.Y. Rozier, “SAT-based explicit LTLf satisfiability checking,” Artificial Intelligence, vol.289, article no.103369, 2020.
CrossRef

[31] O. Lichtenstein, A. Pnueli, and L.D. Zuck, “The glory of the past,” Proc. Conference on Logics of Programs, Lecture Notes in Computer Science, vol.193, pp.431-424, 1985.
CrossRef

[32] K. Nagae, “Path planning for heterogeneous multi-robot systems under counting LTL specifications with package delivery,” Master Thesis, Division of Mathematical Science for Social Systems, Department of Systems Innovation, Graduate School of Engineering Science, Osaka University, 2023.

[33] https://www.gurobi.com/
URL

Lampiran: Pengekodan Formula cLTL+

Kami mengekod formula cLTL+ untuk trajektori terhingga bagi setiap robot dengan mengubah suai pengekodan yang diberikan oleh [21], di mana pengekodan untuk trajektori tak terhingga dicadangkan. Ingat bahawa setiap robot \(n \in N^g\) daripada kumpulan \(g \in G\) dimodelkan oleh sistem peralihan \(T^g=(S^g, \Sigma^g, \delta^g, AP_S, AP_\Sigma, L_S^g, L_\Sigma^g)\). Biarkan \(h\) menjadi panjang trajektorinya. Kemudian, untuk trajektori \(\pi^g_n=s^g_n \langle 0 \rangle \sigma^g_n \langle 0 \rangle s^g_n \langle 1 \rangle\) \(\sigma^g_n \langle 1 \rangle \ldots s^g_n \langle h-2 \rangle \sigma^g_n \langle h-2 \rangle s^g_n \langle h-1 \rangle \in (S^g \Sigma^g)^{h-1}S^g\) daripada robot itu \(n \in N^g\), kami mentakrifkan pembolehubah binari berikut \(w_n^g(t,s)\in \{0, 1\}\), Di mana \(t \in [h-1]\) and \(s \in S^g\).

\[\begin{equation*} w_n^g(t,s) = \left\{ \begin{array}{cl} 1 & \mbox{if } s=s^g_n \langle t \rangle, \\ 0 & \mbox{otherwise.} \end{array} \right. \tag{A$\cdot $1} \end{equation*}\]

Kemudian, trajektori \(\pi_n^g\) dikodkan oleh persamaan berikut. Untuk setiap \(s \in S^g\), kita ada

\[\begin{align} & w^g_n(0,s) = \left\{ \begin{array}{ll} 1 & \mbox{if }s=s_n^g\langle 0\rangle, \\ 0 & \mbox{otherwise}, \end{array} \right. \tag{A$\cdot $2} \\ & w^g_n(t+1,s) \leq \sum_{s' \in S} B^g(s',s) w^g_n(t,s'), \tag{A$\cdot $3} \\ & \sum_{s \in S^g} w^g_n(t,s)= 1. \tag{A$\cdot $4} \end{align}\]

di mana \(B^g(s',s)\) ditakrifkan oleh

\[\begin{equation*} B^g(s',s) = \left\{ \begin{array}{ll} 1 & \mbox{if } \exists \sigma \in \Sigma^g.\ s=\delta^g(s',\sigma), \\ 0 & \mbox{otherwise}. \end{array} \right. \tag{A$\cdot $5} \end{equation*}\]

Ditandakan oleh \(\rho_n^g\) adalah jejak trajektori \(\pi_n^g\). Ingat bahawa formula logik dalaman cLTL+ diterangkan oleh Pers. (2). Kemudian, untuk formula logik dalaman \(\psi\) daripada cLTL+, kami memperkenalkan pembolehubah binari berikut \(z^{g,\psi}_n(t)\) untuk setiap \(t \in [h-1]\) untuk mewakili kepuasan \(\psi\) at \(t\).

\[\begin{equation*} z^{g,\psi}_n(t) = \left\{ \begin{array}{cl} 1 & \mbox{if } \rho_n^g, t \models \psi, \\ 0 & \mbox{otherwise.} \end{array} \right. \tag{A$\cdot $6} \end{equation*}\]

Kemudian, kami menggunakan pengekodan berikut untuk operasi logik yang ditakrifkan oleh Pers. (2).

  • Untuk proposisi atom \(a\), Jika \(a \in AP_S\), kemudian, untuk setiap \(t \in [h-1]\), kita ada
    \[\begin{align} \sum_{s \in S^g,\sigma \in \Sigma^g} V_a(s)\ w^g_n(t,s)\geq & z_{n}^{g,a}(t), \tag{A$\cdot $7} \\ \sum_{s \in S^g,\sigma \in \Sigma^g} V_a(s)\ w^g_n(t,s) < & z_{n}^{g,a}(t) +1. \tag{A$\cdot $8} \end{align}\]
    Ambil perhatian bahawa, untuk mana-mana \(s\) and \(s' \in S^g\), jika ada \(\sigma\in\Sigma^g\) seperti itu \(s'=\delta^g(s, \sigma)\), Maka \(\sigma\) adalah unik. Justeru, jika \(a \in AP_{\Sigma}\), kemudian, untuk setiap \(t \in [h-2]\), kita ada
    \[\begin{align} &\sum_{s,s'\in S,\sigma\in\Sigma}V_a(s,\sigma)A^g(s,\sigma,s')\{w^g_n(t,s) \notag \\ &\qquad\qquad \wedge w^g_n(t+1,s')\} \geq z^{g,a}_n(t) \tag{A$\cdot $9} \\ &\sum_{s,s'\in S,\sigma\in\Sigma}V_a(s,\sigma)A^g(s,\sigma,s')\{ w^g_n(t,s)\notag \\ &\qquad \qquad \wedge w^g_n(t+1,s')\} < z^{g,a}_n(t)+1 \tag{A$\cdot $10} \end{align}\]
  • Untuk \(\psi=\neg \phi\), Di mana \(\phi\) ialah formula logik dalaman cLTL+, kami ada
    \[\begin{equation*} z_{n}^{g,\psi}(t) =1-z_{n}^{g, \phi}(t), \quad \forall t \in [h-1]. \tag{A$\cdot $11} \end{equation*}\]
  • Untuk operasi \(\land\), pengekodannya diperoleh daripada Pers. (11)-(13), secara langsung, dan ditinggalkan.
  • Untuk \(\psi=\bigcirc \phi\), Di mana \(\phi\) ialah formula logik dalaman cLTL+, kami ada
    \[\begin{equation*} z_{n}^{g,\psi}(t)=\left\{ \begin{array}{ll} z_{n}^{g,\phi}(t+1) & \mbox{if } t \in [h-2], \\ 0 & \mbox{if } t=h-1. \end{array} \right. \tag{A$\cdot $12} \end{equation*}\]
  • Untuk \(\psi=\phi_1 {\mathcal U} \phi_2\), Di mana \(\phi_1\) and \(\phi_2\) adalah formula logik dalaman cLTL+, kami ada
    \[\begin{align} z_{n}^{g,\psi}(t) \notag \\ &= \left\{ \begin{array}{ll} z_{n}^{g,\phi_2}(t) \\ \vee (z_{n}^{g, \phi_1}(t) \land z_{n}^{g,\psi}(t+1)) & \mbox{if } t \in [h-2], \\ z_{n}^{g,\phi_2}(h-1) & \mbox{if } t=h-1. \end{array} \right. \tag{A$\cdot $13} \end{align}\]

Mari \(P\) menjadi koleksi jejak semua robot. Formula logik luar cLTL+ diberikan oleh Pers. (3) dan kami menyediakan pengekodan bagi \(tcp=[\psi, m, gset]\) dan tinggalkan operator lain yang sama seperti yang digunakan dalam formula logik dalaman. Kami memperkenalkan pembolehubah binari \(y^{tcp}(t)\) untuk setiap \(t \in [h-1]\).

\[\begin{align} y^{tcp}(t)=\left\{ \begin{array}{cl} 1 & \mbox{if } P,t \models tcp, \\ 0 & \mbox{otherwise}. \end{array} \right. \tag{A$\cdot $14} \end{align}\]

Kemudian, untuk setiap \(t \in [h-1]\), kita ada

\[\begin{equation*} m> \sum_{g \in gset, n \in N^g} z_n^{g,\psi}(t) -My^{tcp}(t) \geq m-M, \tag{A$\cdot $15} \end{equation*}\]

di mana \(M\) adalah nombor positif yang cukup besar memuaskan \(M\geq \sum_{g \in G}|N^g| +1\).

Tambahan pula, \(t\)-input ke \(\sigma^g_n \langle t \rangle\) (\(t \in [h-2]\)) ditentukan oleh \(s'=\delta^g(\sigma^g_n \langle t \rangle, s)\), Di mana \(s\) and \(s'\) adakah negeri-negeri itu memuaskan \(w_n^g(t+1, s')=1\) and \(w_n^g(t,s)=1\).

Nota kaki

1. Dalam simulasi ini, kami menganggap bahawa, untuk mana-mana \(s\) and \(s' \in S^g\), terdapat paling banyak satu input \(\sigma \in \Sigma^g\) memuaskan \(s'=\delta^g(s, \sigma)\). Jika andaian ini tidak berlaku, kami memperkenalkan pembolehubah binari \(w_n^g(t,s,\sigma)\) itu bermakna bahawa keadaan semasa adalah \(s\) dan input \(\sigma\) dikeluarkan pada masanya \(t\). Kemudian, bilangan pembolehubah ialah \(h\sum_{g\in G}|S^g|\cdot |N^g|\cdot |\Sigma^g|\).

Pengarang

Kotaro NAGAE
  Osaka University

received the B.S. and M.S. degrees in Engineering Science from Osaka University in 2021 and 2023, respectively. His research interest includes planning of multi-robot systems.

Toshimitsu USHIO
  Nanzan University

received B.S., M.S. and Ph.D degrees in 1980, 1982 and 1985, from Kobe University. He was a Research Assistant at the UC Berkeley in 1985. From 1986 to 1990, he was a Research Associate in Kobe University. He joined Osaka University in 1994, and was a Professor in 1997. He joined Nanzan University as a professor in 2023. His research interests include control of discrete event systems and nonlinear systems. He is a member of IEEE.

Kata kunci