Aplkasi metode Medical Axis Transform (MAT) untuk mencari lintasan (Path Tracing) di dalam gedung berdasar data denahnya

SENDARI, Siti, Prof. Adhi Susanto, M.Sc.,Ph.D

2005 | Tesis | S2 Teknik Elektro

Salah satu kemampuan agen cerdas (robot) adalah navigasi, yaitu kemampuan berjalan di dalam gedung, menentukan arah gerakan di dalam gedung tanpa menabrak, dan tanpa bantuan manusia. Hal ini memerlukan kemampuan memahami ruangan/lingkungan di dalam gedung (map learning). Metode pembelajaran lingkungan yang digunakan dalam penelitian ini adalah mencari lintasan (path tracing) menggunakan metode medial axis transform yang secara konseptual jelas dan mudah diimplementasikan. Pencarian lintasan menggunakan medial axis transform dalam penelitian ini dilalukan melalui proses: (1) pra-proses, mengolah data denah sehingga diperoleh data garis penyusun denah; (2) pemotongan denah (cropping) berdasar ruang; (3) proses medial axis transform menggunakan metode path tracing; (4) transformasi menjadi graph; dan (5) proses penggabungan/merging. Hasil penelitian menunjukkan proses medial axis transform menggunakan metode path tracing untuk bangun segiempat memerlukan waktu yang cukup lama dan mempunyai respons eksponensial (polinomial orde dua) untuk ukuran matriks yang semakin besar. Pemotongan denah memberikan ukuran matriks denah menjadi lebih kecil (±100x100), sehingga elapsed time menjadi lebih cepat untuk masing-masing ruang (±26,2 detik). Elapsed time untuk keseluruhan denah 1 adalah 221,35 detik, dengan panjang lintasan total 2490,6 unit, dan denah 2 adalah 181,2 detik dengan panjang lintasan total 1688,5 unit. Hasil akhir dari penelitian ini adalah graph denah gedung yang berupa matriks adjacency. Berdasar matriks adjacency, maka proses pencarian rute (path searching) menjadi lebih mudah dan memerlukan waktu yang singkat (kurang dari 1 detik). Proses path searching dilakukan dengan menggunakan algoritma A*.

One of the intelligent agent (robot) abilities is navigation, so that it can move around in any building without hitting obstacles and unassisted by human. It should learn the environtment that called map learning. The map learning method in this research was path tracing based on the medial axis transform method, which is clear conceptually and easy to implement. In this research, the process of path tracing consisted of (1) pre-process, which processed inchnograph into line data structure; (2) the cropping of ichnograph into the rooms; (3) the medial axis transform process using path tracing method; (4) a transform into the graph; and (5) the merging. The research revealed that the medial axis transform processes for parallelogram needed sufficiently long time and had exponential time responses greater matrix sizes. The cropping process made ichnograph matrix size smaller (±100x100), so that elapsed time became shorter for each rooms (±26.2 seconds). Elapsed time for the first ichnograph was 221.35 seconds for a total length of 2490.6 units and the second ichnograph was 181.2 seconds for a total length of 1688.5 units. The research gave graph (in adjacency matrix form) of a building. The application of the adjacency matrix for path searching process was easier and faster. It’s done by A* algorithms.

Kata Kunci : Agen Cerdas (Robot), Path Tracing, Medial Axis Transform, graph, intelligent agent, medial axis transform, path searching, path tracing , 2-D space, adjacency matrix.