Pemecah labirin rabun optimal

Saya bermain-main dengan demo Labirin Google Blocky , dan ingat aturan lama bahwa jika Anda ingin menyelesaikan labirin, jaga tangan kiri Anda tetap di dinding. Ini berfungsi untuk setiap labirin yang terhubung sederhana dan dapat diimplementasikan oleh transduser terbatas.

Biarkan robot kami diwakili oleh transduser dengan tindakan berikut, dan dapat diamati:

Tindakan: maju ( $\uparrow$ ), belok kiri ( $\leftarrow$ ), belok kanan ( $\rightarrow$ )
Dapat diamati: dinding depan ( $\bot$ ), tidak ada dinding depan ( $\top$ )

Kemudian kita dapat membangun pemecah labirin sebelah kiri sebagai (maaf gambar malas saya):

transduser untuk mengatasi labirin

Dimana melihat diamati akan membuat kita mengikuti tepi yang tepat dari negara sambil melakukan tindakan yang terkait dengan tepi itu. Otomat ini akan menyelesaikan semua labirin yang terhubung sederhana, meskipun mungkin butuh waktu mengikuti jalan buntu. Kami menyebut automaton lebih baik daripada jika: $B$ $A$

mengambil langkah-langkah yang lebih ketat hanya pada jumlah labirin yang terbatas, dan $B$
mengambil langkah-langkah yang sangat sedikit (rata-rata; untuk varian probabilistik) pada jumlah labirin yang tak terbatas. $B$

Dua pertanyaan saya:

Apakah ada robot terbatas yang lebih baik dari yang digambarkan di atas? Bagaimana jika kita mengizinkan transduser probabilistik?
Apakah ada robot yang terbatas untuk memecahkan labirin yang tidak selalu terhubung?

automata finite-automata artificial-intelligence Artem Kaznatcheev
sumber

@jmad dan saya melakukan diskusi yang cukup bermanfaat dalam obrolan tentang pertanyaan ini. Jika Anda berpikir tentang pertanyaan (terutama definisi yang lebih baik daripada ) maka saya sarankan memeriksa transkrip.

Artem Kaznatcheev

Saya gagal melihat bagaimana pertanyaan ini terkait dengan AI (khususnya agen kami untuk tidak mengubah perilaku yang diberikan data contoh), tapi saya bukan ahli dalam bidang itu.

Raphael

@Raphael penyelesaian labirin dan penemuan jalur (dari tinjauan BFS, DFS, ke A *, dan di-lingkungan) adalah kurikulum dasar dalam kursus AI intro. Saya setuju, sebagai intelijen, ini bukan yang sangat menarik, tetapi jika AI telah mengajarkan saya apa pun: sebagian besar AI hanya masalah pencarian.

Artem Kaznatcheev

Jawaban:

Jika saya mengerti pertanyaannya dengan baik, saya pikir Anda dapat menerapkan trik speedup untuk mendapatkan automata lebih cepat pada labirin dengan jumlah tak terbatas (asalkan pintu keluar ditempatkan di salah satu perbatasan): Anda dapat menggunakan kondisi internal untuk menyimpan jumlah langkah yang terbatas dan mengenali jalan buntu seperti yang ada pada gambar:

masukkan deskripsi gambar di sini

$A$

Dengan cara yang sama Anda dapat menyandikan sejumlah terbatas bentuk ukuran tetap yang berbeda untuk menghindari jalan buntu dan mempercepat robot Anda. Akibatnya, tidak ada pemecah labirin rabun "optimal" untuk labirin yang terhubung sederhana dengan jalan keluar yang ditempatkan di perbatasan.

Caranya bekerja jika pintu masuk ditempatkan di dalam labirin dan jalan keluar di perbatasan juga; tetapi jika pintu keluar ditempatkan di dalam labirin, maka itu tidak berfungsi karena semua lokasi harus dikunjungi dan dalam hal ini pemecah rabun Anda optimal.

Jelas Anda tidak dapat menerapkan trik yang sama untuk menyelesaikan labirin yang tidak terhubung secara sederhana (tetapi harus bekerja jika ada batas atas yang tetap pada ukuran setiap komponen yang tidak terhubung).

Vor
sumber

Ini adalah trik keren untuk kasus keluar-masuk pada batas (yang merupakan sub-kelas dari labirin yang terhubung sederhana). Ini menunjukkan bahwa dalam kasus terbatas ini, pemesanan yang saya tentukan tidak memiliki elemen minimum. Saya tidak berpikir itu bisa digeneralisasi ke semua labirin yang terhubung sederhana (yang mana set sebelah kiri berfungsi pada).

Artem Kaznatcheev

@ ArtemKaznatcheev: Saya pikir triknya bekerja pada labirin dengan jalan masuk di dalam labirin dan keluar pada batas juga. Lebih jauh lagi ia bekerja pada labirin (tak terhingga banyaknya) di mana ada kapal selam seperti yang ada di gambar). Saya akan mengedit pertanyaan untuk memperjelas hal ini.

Vor

k

$k$

4 k - 1

$4k-1$

pertanyaan 1

Saya pikir definisi Anda tentang yang lebih baik terlalu ketat dalam arti bahwa yang terbatas terlalu ketat (tapi saya tidak punya definisi yang lebih baik).

$R=(R_i)_i$ $R_i$ $i$ $L$ $A_R$ $A_L$ $R$ $L$ $A_R$ $A_L$

$A_R$ $R$ $A_R$

Transduser probabilistik mungkin dapat dikesampingkan karena transduser deterministik akan lebih cepat pada set labirin yang tak terbatas ini.

Pertanyaan 2 (berkat diskusi dengan OP )

Tidak (sumber: makalah inovatif oleh Lothar Budach. Teorema ini lebih jelas dinyatakan dalam abstrak artikel ini oleh Frank Hoffmann.)

jmad
sumber

ya, kita perlu mendefinisikan beberapa kelas ekivalen pada labirin di bawah transformasi standar (seperti rotasi dan refleksi) untuk membuat dinding kiri dan kanan tangan mengikuti persamaan. Sayangnya, bagian pertanyaan 1 Anda tidak menjawab pertanyaan pertama saya . Anda menunjukkan bahwa ada pemecah yang tak tertandingi (dalam urutan parsial 'lebih baik daripada') (seperti tangan kiri dan tangan kanan jika kita tidak membuat asumsi simetri) tetapi itu tidak membuktikan bahwa tidak ada satu pun yang ada. lebih baik dari tangan kiri.

Artem Kaznatcheev

A

$A$

B

$B$

A \leq B

$A \leq B$

L

$L$

\exists R

$\exists R$

R ≰ L

$R \not\leq L$

L ≰ R

$L \not\leq R$

\forall A

$\forall A$

A ≰ L

$A \not\leq L$

L \leq A

$L \leq A$

@ ArtemKaznatcheev: ya, saya tahu itu tidak menjawab pertanyaan, saya seharusnya lebih jelas. Maksud saya adalah bahwa saya pikir kita bisa menerapkan ini pada LH tetapi juga bahwa terlalu sensitif dengan jenis set yang mudah tak terbatas ini. (Saya pikir hanya jika sangat mirip dengan (subset dari) )

\leq

$≤$

A \leq B

$A≤B$

B

$B$

A

$A$

jmad

Definisi alternatif yang dapat saya pikirkan adalah meminta contoh-contoh buruk menjadi sedikit (alih-alih terbatas); jumlah polinomial atau lebih kecil (mungkin log?) dari contoh buruk dan banyak: super polinomial / jumlah eksponensial dari contoh-baik. Tapi saya benar-benar berpikir ini bahkan lebih ketat, karena harus mengungguli pada contoh BANYAK.

A

$A$

B

$B$

Artem Kaznatcheev

@ArtemKaznatcheev: Anda dapat melakukan sesuatu yang tergantung pada ukuran labirin (sesuatu seperti tetapi keduanya dipertanyakan dan tidak praktis). Kami dapat melanjutkan obrolan .

# {A (M) < B (M) ∣ | M | \leq n} / # {M ∣ | M | \leq n} = o (1)

$\#\{A(M)<B(M) ∣ |M|≤n\}/\#\{M ∣ |M|≤n\} = o(1)$

jmad