PERANCANGAN PROGRAM APLIKASI MOBILEPENCARIAN LOKASI DALAM GEDUNG MENGGUNAKAN ALGORITMA A-STAR Aditya Giri Hertanto Binus University, Jakarta Barat, DKI Jakarta, Indonesia
ABSTRAK Pencarian lokasi dalam gedung menjadi masalah ketika seorang pengunjung masuk ke dalam suatu gedung bertingkat dengan wilayah yang luas dan padat. Berbeda dengan pencarian lokasi di luar ruangan yang dapat dengan mudah menggunakan teknologi GPS dan beragam sistem navigasi yang tersedia di semua perangkat, pencarian lokasi dalam gedung tidak dapat menggunakan teknologi tersebut karena ketebalan struktur gedung yang dapat melemahkan penerimaan sinyal satelit GPS. Mall Central Park (PT Central Prima Kelola) yang memiliki struktur gedung bertingkat, ratusan tenant dan area rekreasi yang sangat besar juga menghadapi permasalahan ini. Algoritma A* (A-star), sebuah algoritma pencarian rute yang selama ini lebih sering digunakan pada aplikasi permainan komputer, akan diimplementasikan ke dalam perangkat bergerak sebagai algoritma yang dapat membantu perhitungan dan penyajian rute terbaik yang akan dilewati oleh pengunjung Mall Central Park. Dengan perkembangan teknologi smartphone saat ini yang semakin canggih dan terjangkau, memungkinkan penulis untuk merancang sebuah aplikasi mobile directory dengan fitur navigasi di dalam gedung tanpa menggunakan teknologi GPS. Dalam penerapannya, aplikasi mobile yang berjalan pada
sistem operasi Android ini dapat membantu pengunjung melakukan pencarian suatu lokasi dalam gedung dengan baik.
Kata Kunci:A* (A-star), indoor, navigasi, smartphone, mobile, Android, rute terpendek.
1. Pendahuluan Kemajuan teknologi saat ini membuat masyarakat mulai mendigitalisasikan semua perangkat pendukung yang biasa mereka gunakan, salah satu contohnya adalah peta. Peta digital yang telah dilengkapi dengan sistem navigasi kini sudah banyak dipakai di kendaraan-kendaraan umum maupun pribadi. Dengan dukungan teknologi GPS (Global Positioning System), sistem navigasi ini dapat mengetahui dimana posisi pengguna sekarang, dan menunjukan jalur terbaik yang akan dilewati untuk mencapai suatu tujuan. Proses digitalisasi peta ini juga dapat kita temukan di bangunan-bangunan bertingkat. Mulai dari kompleks industri hingga pusat perbelanjaan mulai menyediakan sistem informasi (peta direktori) ini untuk para pengguna gedung (khususnya para pengunjung). Idealnya sistem informasi ini dapat memberikan gambaran yang jelas tentang arah yang harus dilewati dan tujuannya, tetapi pada prakteknya untuk bangunan dengan lahan yang luas dan bertingkat-tingkat pengguna sering merasa kehilangan arah di tengah perjalanan. Perangkat GPS umumnya tidak mendapat sinyal yang baik ketika berada di area tertutup dan berlapis-lapis seperti di dalam bangunan. Sedangkan untuk teknologi pemancaran ulang (re-radiating) GPSmenggunakan pemancar dalam ruangan sampai saat ini belum dapat dikatakan ekonomis jika hanya untuk aplikasi sistem navigasi dalam ruangan.
Untuk menyelesaikan permasalahan ini, dibutuhkan suatu aplikasi sistem navigasi bergerak yang dapat berjalan dengan baik tanpa menggunakan teknologi GPS. Dengan semakin terjangkau dan majunya teknologi smartphone dan perangkat bergerak lainnya, aplikasi navigasi yang dibangun di dalam perangkat bergerak berbasis sistem operasi Android adalah salah satu solusi yang efektif dan ekonomis untuk dikembangkan. (Le, et al. 2009) Selama ini algoritma A* lebih sering digunakan untuk menghadirkan kemampuan Artificial Intelegence pencarian jalur pada suatu karakter dalam permainan komputer. Pada aplikasi ini, algoritma A* akan melakukan perhitungan jarak dari graf yang telah tersedia, dengan merepresentasikan setiap titik sebagai jalur yang dapat dilewati oleh pengunjung. Di antara titik-titik tersebut adapun titik yang merepresentasikan suatu area toko yang menjadi input sebagai lokasi awal atau tujuan akhir dari proses pencarian jalur terbaik ini.
2. Metode Menurut Munir (2009), Metode A* tanpa fungsi heuristic yang baik akan memperlambat pencarian dan dapat menghasilkan rute yang tidak tepat. Fungsi heuristic yang sempurna akan membuat metode A* langsung menuju final node tanpa harus mencari kearah lain. Sehingga jika fungsi heuristic-nya terlalu underestimate akan menyebabkan algoritma ini beranggapan bahwa ada rute lain yang lebih baik. Untuk fungsi heuristic yang underestimate, bila nilainya terlalu rendah akan menyebabkan algoritma ini seperti algortima Djikstra’s yang mencari ke segala arah yang mungkin. Hal ini dikarenakan tidak ada informasi yang cukup mengenai masalah yang dihadapi, sehingga menyebabkan metode A* melakukan pencarian lebih banyak dan lebih lama.
Dalam ilmu komputer, A* (disebut “A star”) adalah sebuah graph atau metode tree search yang digunakan untuk mencari jalan dari sebuah node awal ke node tujuan (goal node) yang telah ditentukan, metode ini menggunakan “estimasi heuristic” h(x) pada setiap node untuk mengurutkan setiap node x berdasarkan estimasi rute terbaik yang melalu node tersebut. Dalam prosesnya metode ini akan mengunjungi setiap node berdasarkan urutan yang dihasilkan dari estimasi heuristic ini. Metode A* adalah salah satu contoh dari metode best-first search. Metode A* dikembangkan oleh Peter Hart, Nils Nilsson, dan Bertram Raphael, mereka juga menyebut metode tersebut dengan sebutan algoritma A, dengan menggunakan metode ini dan dengan heuristic yang tepat menghasilkan sebuah hasil yang optimal, yaitu A*. Secara umum, depth-first search (DFS) dan breadth-first search (BFS) adalah dua kasus spesial dari metode A*. Algoritma Djikstra’s merupakan kasus yang paling special dari A*, di mana h(x) = 0 untuk semua x. Dalam masalah pencarian rute di mana metode A* sering digunakan, A* secara bertahap membangun semua rute yang mengarah mulai dari titik awal sampai akhirnya mencapai titik akhir. Metode A* hanya membangun rute yang mungkin digunakan untuk mencapai tujuan. Untuk mengetahui rute mana yang memungkinkan mengarah ke titik akhir, A* menggunakan estimasi heuristic jarak dari sembarang node ke node tujuan. Dalam kasus pencarian rute, ini bisa jadi sama dengan jarak lurus antara dua titik, di mana biasanya merupakan perkiraan dari jarak jalan. Hubungan antara heuristic dengan algoritma A*: a. Apabila h(n) selalu bernilai 0, maka hanya g(n) yang akan berperan, dan A* berubah menjadi Algoritma Dijkstra, yang menjamin selalu akan menemukan jalur terpendek.
b. Apabila h(n) selalu lebih rendah atau sama dengan ongkos perpindahan dari titik n ke tujuan, maka A* dijamin akan selalu menemukan jalur terpendek. Semakin rendah nilai h(n), semakin banyak titik-titik yang diperiksa A*, membuatnya semakin lambat. c. Apabila h(n) tepat sama dengan ongkos perpindahan dari n ke tujuan, maka A* hanya akan mengikuti jalur terbaik dan tidak pernah memeriksa satupun titik lainnya, membuatnya sangat cepat. Walaupun hal ini belum tentu bisa diaplikasikan ke semua kasus, ada beberapa kasus khusus yang dapat menggunakannya. d. Apabila h(n) kadangkala lebih besar dari ongkos perpindahan dari n ke tujuan, maka A* tidak menjamin ditemukannya jalur terpendek, tapi prosesnya cepat. e. Apabila h(n) secara relatif jauh lebih besar dari g(n), maka hanya h(n) yang memainkan peran, dan A* berubah menjadi BFS.
OPEN = priority queue containing START CLOSED = empty set while lowest rank in OPEN is not the GOAL: current = remove lowest rank item from OPEN add current to CLOSED for neighbors of current: cost = g(current) + movementcost(current, neighbor) if neighbor in OPEN and cost less than g(neighbor): remove neighbor from OPEN, because new path is better if neighbor in CLOSED and cost less than g(neighbor): ** remove neighbor from CLOSED if neighbor not in OPEN and neighbor not in CLOSED: set g(neighbor) to cost add neighbor to OPEN set priority queue rank to g(neighbor) + h(neighbor) set neighbor's parent to current reconstruct reverse path from goal to start by following parent pointers
3. Identifikasi Pada September 2010, Mall Central Park mulai mengembangkan media edirectory yang dapat diakses melalui kioskLCD Touch Screen dan website. LCD Touch Screen ini terdapat pada setiap lantai gedung Mall Central Park.
Gambar 1 Diagram Sistem e-Directory Mall Central Park saat ini
e-Directory ini menampilkan floorplan dan berbagai informasi tentang tenant, news, promo, dan event. Setiap user yang datang dapat menggunakan perangkat eDirectory secara bergantian. Untuk melakukan update konten pada e-Directory ini, admin dapat langsung terhubung dengan database lokal yang terdapat pada kiosk tersebut. Setiap kiosk ini dapat terhubung dengan kantor manajemen (admin) menggunakan jaringan lokal yang ada.
Aplikasi e-Direcctory yangg terdapat pada setiiap kiosk ini berjalaan m menggunakan n platform Adobe A Air ppada kompu uter dengan sistem operrasi Window ws. Sedangkan untuk u directtory yang ddiletakkan pada p websitee Mall Cenntral Park, ee D Directory berrjalan mengg gunakan Adoobe Flash.
G Gambar 2 Tampilan T e-D Directory paada kiosk dann website
Kioskke-Directory yang disebaar pada setiaap lantai inii sebenarnyaa sudah dapat m mencukupi kebutuhan k user tentang segala infoormasi menggenai Mall Central Parkk. N Namun nilai investasi untuk u setiap kiosk yangg sangat tinnggi mengakkibatkan Maall C Central Park tidak t dapat menyediakan m nnya di setiaap sudut Malll. Untuk k akses e-D Directory m melalui webssite, user masih m diharruskan untuuk m memiliki pluug-inAdobe Flash Playyer supaya dapat menngakses apliikasi tersebuut dengan baik, sedangkan perangkat bergerak b yanng umum paada saat ini seperti tabllet dan smartphhone sebagian besar sudah mullai meningggalkan plug g-in tersebuut diikarenakan masalah m pennggunaan ressource yang terlalu besaar. Hal ini mengakibatka m an
akses e-Directory di dalam Mall Central Park hanya terbatas pada pemilik laptop dan pengguna kiosk saja. Selain masalah infrastruktur diatas, masalah lain yang terdapat pada bangunan bertingkat dan luas adalah pencarian lokasi. Walaupun Mall Central Park telah menyediakan e-Directory, tetap saja masih banyak pengunjung yang kesulitan untuk mencari lokasi tujuan mereka dengan cepat dan tepat. Terlebih untuk pengunjung yang baru pertama kali datang ke Mall Central Park, tentu belum mengerti tentang struktur, akses, dan apa saja yang ditawarkan di dalam Mall. Penulis mengajukan sebuah solusi untuk memperluas jangkauan pengguna dan jumlah e-Directory menggunakan aplikasi mobile yang berjalan pada sistem operasi Android. Selain fitur e-Directory, pada aplikasi ini juga terdapat sebuah fitur routing atau pencarian lokasi yang ditenagai oleh algoritma A* layaknya sistem navigasi di luar ruangan yang sudah umum. Aplikasi ini dapat terhubung langsung dengan Web Server yang sudah ada, sehingga memudahkan admin untuk melakukan manajemen konten yang akan di push ke semua media direktori.
4. Pengumpulan Data Untuk menambahkan fitur navigasi pada aplikasi ini, maka diperlukan beberapa tambahan data yang belum terdapat pada aplikasi e-Directory sebelumnya. Berikut adalah data-data yang disiapkan untuk perancangan aplikasi ini: a. Floorplan 2D b. Koordinat node (tenant, transport, dan path) c. Jarak antar node dan adjacent node
Setelah data-data tersebut telah siap, maka data tersebut dapat diintegrasikan ke dalam aplikasi mobile. Langkah-langkah yang digunakan untuk mengumpulkan data-data tersebut dapat dilihat pada gambar di bawah ini.
Gambar 3 Teknik Pengumpulan Data
Untuk mendapatkan ketepatan lokasi dan kemudahan untuk memasukkan data-data yang telah disiapkan ke dalam aplikasi. Setiap daerah yang menjadi jalur akses pada aplikasi ini akan ditandai dengan node-node yang saling berhubungan,
node-node inni diletakkaan pada griid yang tellah disediakkan untuk menghasilka m an koordinat yanng akurat.
Gambarr 4 Teknik peenempatan nnode pada Grrid untuk meendapatkan koordinat k
Ga ambar 5 Laapisan layer yyang digunaakan pada flooorplan
5. Desain D Menu urut Krug (2 2005), aplikaasi atau situs web yang baik, haruss membiarkaan pengguna meenyelesaikann pekerjaan mereka m denggan mudah ddan langsungg. Supaya useer
dapat langsung memahami dengan mudah apa saja yang dapat dilakukan dengan aplikasi ini, maka layout utama aplikasi ini dibuat dengan model dashboard dan action bar. Model desain aplikasi ini dipopulerkan oleh Google pada sesi Android UI Design Patterns, Google I/O 2010(Fulcher et al., 2010).
Gambar 6Struktur Menu Aplikasi Mobile Directory
6. Implementasi Di bawah ini adalah hasil implementasi dari aplikasi Mobile Directory di Mall Central Park.
Gambar 7Screenshot Mobile Directory
Gambar 8Screenshot Mobile Directory
7. Evaluasi Berdasarkan hasil pengujian yang dilakukan penulis dan pihak Mall Central Park, pada aplikasi ini masih terdapat beberapa kekurangan dan keunggulan yang ditemukan. a. Aplikasi Mobile Directory ini memiliki beberapa keunggulan sebagai berikut: b. Dengan menggunakan hardware ujicoba, hasil kalkulasi pencarian rute terbaik dapat ditampilkan sangat cepat. c. Mayoritas pengguna perangkat Android dapat menggunakan aplikasi ini dengan baik. Mengacu pada statistik yang dikemukakan oleh Google (2012), aplikasi ini berjalan pada versi platform Android yang paling populer (Android 2.3.3-2.3.7), dengan 58.1% dari seluruh perangkat di seluruh dunia dapat menjalankan aplikasi ini. Disebutkan pula oleh Google (2012), bahwa terdapat 18.4% (untuk resolusi 320x480) dan 67.1% (untuk resolusi 480x800) dari total perangkat Android yang mendukung resolusi layout yang digunakan pada aplikasi ini. d. Aplikasi ini dilengkapi tombol shortcut untuk langsung melakukan pencarian rute dan melakukan panggilan dari halaman detil toko. e. Fitur pinch-to-zoom yang populer di kalangan pengguna smartphone diimplementasikan pada aplikasi ini dengan baik untuk melakukan pembesaran atau pengecilan tampilan floorplan. f. Kemudahan untuk mendapatkan informasi news dan promotions paling terkini menggunakan koneksi internet. g. Aplikasi ini masih dapat digunakan ketika koneksi internet tidak tersedia, karena database toko disimpan pada database lokal. h. Proses pencarian rute dikalkulasi langsung oleh aplikasi ini, tanpa menggunakan koneksi internet ke server.
i. User interface yang menarik, intiutif dan sesuai dengan coporate identity Mall Central Park.
Tidak dapat dipungkiri bahwa aplikasi Mobile Directory ini masih memiliki beberapa kelemahan yang dapat diperbaiki pada pengembangan berikutnya, kelemahan-kelemahan tersebut adalah: a. Aplikasi ini tidak menyimpan cache dari informasi yang telah di download. b. Events dan Promotions belum dilengkapi gambar yang representatif. c. Belum menjangkau semua daerah di dalam Mall, seperti: toilet, musholla, dan lahan parkir. d. Proses manajemen data masih langsung akses ke dalam database, belum disediakan backend interface yang lebih mudah.
8. Simpulan Berdasarkan hasil pengamatan dan pembelajaran terhadap hasil dari penulisan skripsi ini, penulis dapat mengambil beberapa kesimpulan sebagai berikut: a. Ujicoba internal yang dilakukan pihak manajemen Mall Central Park menunjukkan bahwa sistem ini dapat berfungsi sebagai alternatif media direktori selain kiosk dan website, dan algoritma A* yang digunakan untuk mencari rute terbaik dalam modul Directions terbukti dapat digunakan untuk menampilkan rute terbaik yang dapat memudahkan pengunjung dalam pencarian suatu lokasi di dalam Mall Central Park. b. Walaupun tanpa adanya positioning system, program navigasi dalam ruangan ini dapat berjalan dengan baik layaknya program navigasi umum yang berjalan di luar ruangan menggunakan GPS.
Program dapat diintegrasikan dengan sistem yang saat ini sedang berjalan di Mall Central Park, penambahan yang perlu diadakan pada sistem hanya berupa penambahan Web Service yang berguna untuk penghubung antara database dengan aplikasi mobile.
Melihat hasil implementasi dan kemungkinan untuk penelitian lebih lanjut dari aplikasi ini, di bawah ini adalah beberapa saran yang dapat berguna untuk pengembangan berikutnya: a. Sistem pengumpulan data koordinat saat ini masih menggunakan cara konvensional, kedepannya dapat digunakan pemetaan floorplan dan node menggunakan shapefile. Shapefile adalah sebuah tipe data spasial yang memiliki informasi geografis tambahan di dalamnya. Dengan menggunakan tipe data ini diharapkan dapat mempercepat proses pengembangan, dan proses update apabila terjadi perubahan struktur dan lokasi gedung. b. Mengadakan pengumpulan data yang lebih dalam, sehingga semua wilayah dapat tercakup dalam aplikasi ini. Wilayah yang belum tercakup ini seperti: lahan parkir, fasilitas umum, dan taman. c. Menambahkan fitur pembacaan QR Code dan NFC sebagai input lokasi, sehingga kedepannya user tidak perlu melakukan input lokasi awal secara manual. d. Menambahkan fitur untuk pencarian rute antar lantai, sehingga semua area dapat ditelusuri dengan baik oleh pengunjung. e. Memindahkan akses fitur pencarian rute ke Dashboard, supaya user dapat mengetahui tentang keberadaan fitur tersebut.
Daftar Pustaka [1] Dharwiyanti, S., & Wahono, R. S. (2006). Pengantar unified modeling language (UML). Diperolehdari http://ilmukomputer.org/2006/08/25/pengantar-uml/ [2] Fulcher, R. N., Chris and Palmer, J., & Robertson, C. (2010). Android UI design patterns. Diperoleh01-06-2012 dari http://www.google.com/events/io/2010/sessions/android-ui-designpatterns.html [3] Google Android. Platform versions. (2012). Diperoleh01-02-2012 dari http://developer.android.com/resources/dashboard/platform-versions.html [4] Google Android. Screen sizes and densities. (2012). Diperoleh01-02-2012 dari http://developer.android.com/resources/dashboard/screens.html [5] Jackson, Wallace. (2011). Android apps for absolute beginner. New York: Apress. [6] Krishnaswamy, Nikhil. (2009). Comparison of efficiency in pathfinding algorithms in game development. Chicago: DePaul University. [7] Krug, Steve. (2006). Don’t make me think! A common sense approach to web usability. (2nd Edition). California: New Riders. [8] Kusrini. (2007). Strategi perancangan dan pengelolaan basis data. Yogyakarta: ANDI [9] Le, M. H. V., Saragas, D., & Webb, N. (2009). Indoor navigation system for handheld devices. Massachusetts: Worcester Polytechnic Institute. [10] Lester, Patrick. A* pathfinding for beginners. (2005). Diperoleh29-01-2012 dari http://www.policyalmanac.org/games/aStarTutorial.htm [11] Munir, Rinaldi. (2005). Matematika diskrit. (Edisi Ketiga). Bandung: Informatika. [12] Munir, Rinaldi. (2009). Diktat strategi algoritma. Bandung: ITB.
[13] Patel, Amit. Amit’s A* pages. (2011). Diperoleh18-01-2012 dari http://theory.stanford.edu/~amitp/GameProgramming/ [14]Prastowo, B. N. SQLite DBMS. (2010). Diperoleh22-01-2012 dari http://ploworks.wg.ugm.ac.id/public.php?filein=news&artikel=F9C3ACF02E 20689E [15] Putra, D. A. R. Sistem operasi mobile. (2010). Diperoleh22-01-2012 dari http://iyozdamnation.wordpress.com/2010/11/14/sistem-operasi-mobile/ [16] Russel, S., & Norvig, Peter. (2010). Artificial intelligence. A modern approach. New Jersey: Pearson Education. [17] Sulianta, Feri. (2010). IT ergonomics. Jakarta: Elex Media. [18] Suryani, Erma. (2006). Pemodelan & simulasi. Yogyakarta: Graha Ilmu. [19] Weisstein, E. W. Algorithm. n.d. Diperoleh24-01-2012 dari: http://mathworld.wolfram.com/Algorithm.html
MOBILE APPLICATION PROGRAM DESIGNLOCATION SEARCH IN THE BUILDING USING A-STAR ALGORITHM Aditya Giri Hertanto Binus University, Jakarta Barat, D KI Jakarta , Indon esia
AB STRACT Location Search es in the build ing beco mes a p roblem when a visitor enters into a high rise buildin g with a vast and dense territory . Contrast to the search of outdoor locations that can easily use GPS technology and a variety of navigation systems are available in all devices, location searches at the building can not use these technologies because of the thickness of the building structure which can weaken the GPS satellite signal recep tion. Central Park M all (PT Central Prima Kelola) which has the high rise buildin gs, hundreds of tenants and a huge recreation area is also facing this problem. A* (A-star) Algorithm, a routing algorithm that has been more frequently used in comp uter games, will be imp lemented into the mobile device as an algorithm that can help the calcu lation and presentation of the best route that will be passed by the visitors of Central Park M all. With the current develop ment of smartphone technology , which is more sop histicated and affordable, allowin g the author to design a mobile directory app lication with the navigation features in the build in g without using GPS technolo gy. In its imp lementation, this mobile ap plication running on the Android op erating sy stem will help visitors to search a location within the buildin g as well. Keyword s:A* (A-sta r), indoor, navigation, smartphone, mobile, Android, shortest pa th.
1. Introduction Technological advances m ake people begin to digitize all the support they use, like map s. Digital map s that have been equip ped with the navigation system is now widely used in public and private transp ortation. With the support of GPS (Global Positioning Sy stem), this navigation system can find out where the user's current p osition, and shows the best p ath that will be p assed to achieve a destination. The process of digitizing these maps can also be found in mu ltilevel buildin gs. Rangin g from industrial co mp lexes to shopp ing centers began p rovidin g information system (map directory ) to the users of the building ( esp ecially visitors). Ideally, this information sy stem can p rovide a clear p icture of the direction that must be passed and the goal, but in practice for buildings with vast land and terraced, users often f eel disoriented in the middle of the course. GPS devices generally don't get a decent signal when in a closed ar ea and multi-lay ered as in the buildin g. As for the re-transmission technology (re-radiating) using a GPS transmitter in the room, so far it wasn't economical if only for indoor navigation system app lications. To resolve this problem, we need a mobile navigation sy stem app lication that can run well without using GPS technolo gy . With the rap id advancement and more affordable smartp hone/mobile device techno lo gy, navigation ap p lications that are built on a mobile d evice (usin g on Android operating sy stem) is one of the effective and econom ical solutions to be developed. (Le, et al. 2009) Over the p ast, A* algorithm is more often used to represent the Artificial Intelegence's capability in a pathfinding for a computer gam e's character. In this app lication, the A* algor ithm will calcu late the distance from the predefin ed graph, with each p oint rep resenting a pathway that can be passed by visitors. Among these
p oints, there's p oints that rep resent a store area, which will becom e an inp ut for the starting location or beco me an inp ut for destination of this best p ath searches p rocess.
1. Methods Accordin g to M unir (2009), A* M ethod without a good heuristic fun ction will slow down the search and could result in an inap p rop riate route. Perfect heuristic function will m ake A* method go directly to the final node without having to look the other way. So if the heuristic function is too under estimate this will cause the algorithm assumes that there is a better route. For underestimate heuristic function, when the value is too low, it will cause the algor ithm p erform like Djikstra’s algorithms looking into all p ossible directions. This is because there is not enough information about the encountered p roblems, causin g the A* method to search more and lon ger. In comp uter science, A* (called "A star") is a gr ap h or tree search method, that used to find the way of an in itial nod e to the destination nod e (goal node) that has been determined, this method uses "heuristic estimate" h (x) on each node to sort every x node based on estimates the best route through the node. In the p rocess, this method will be visitin g each node based on ord er generated from this heur istic estimate. A* Method is an examp le of best-first search methods. A* Methods was develop ed by Peter Hart, Nils Nilsson, and Bertram Rap hael, they also call the method as algorithm A, using this methods and with the proper heuristic p roduces an optimal result, i.e. A*. In general, depth-first search (DFS) and breadth-first search (BFS) are two sp ecial cases of the A* methods. Djikstra's algorithm is the most special case of A*, where h (x) = 0 for all x.
In the routing p roblem in which the method is often used A*, A* gradu ally build up all the routes that lead from the starting p oint until finally reachin g the end p oint. A* M ethod only build routes that may be used to achieve the goal. To find out which route allows the lead to the end point, A* using a heuristic estimate of the distance from any node to destination node. In the case of routing, this could be the same as the straight d istance between two p oints, which is usually the ap proximate distance from the road.The relationship between heuristic and A* algorithm: a. When h (n) is alway s value 0, only g (n), which will p lay a role, and A * ch ange to Dijkstra algorithm, which guarantees always will find the shortest p ath. b. If h (n) is alway s lower than or equal to the cost of disp lacement of the point n to the goal, then A* is guaranteed to always find the shortest p ath. The lower the value of h (n), the more that examined points A*, making it more slower. c. If h (n) exactly equal to the cost of moving from n to the goal, then A* will only follow the best path and never examine on e other point, making it very fast. While this may not necessarily be applied to all cases, there are some sp ecial cases that can be use. d. If h (n) som etimes greater than the cost of moving fro m n to the go al, then A* does not guarantee find ing the shortest path, but the p rocess is quick. e. If h (n) are r elatively much lar ger than g (n), then the only h (n), which p lay s a role, and A* changed to BFS.
OPEN = p riority queue containing START CLOS ED = empty set while lowest rank in OPEN is not the GOAL: current = remove lowest rank item from OPEN add current to CLOSED for neighbors of current: cost = g(current) + movem entcost(current, neighbor) if neighbor in OPEN and cost less than g(neighbor): remove neighbor from OPEN, because n ew path is better if neighbor in C LOSED and cost less than g(neighbor): ** remove neighbor from CLOSED if neighbor not in OPEN and neighbor not in CLOSED: set g(neighbor) to cost add neighbor to OPEN set priority queue rank to g(neighbor) + h(neighbor) set neighbor's p arent to current reconstruct reverse p ath from goal to start by following p arent p ointers
2. Identification In September 2010, the Central Park Mall began to develop e-d irectory media that can be accessed via the Touch Screen LCD kiosk and website. LCD Touch Screen is located on each f loor of the Central Park M all building.
Picture 1 Central Park Mall current e-Directory system
The e-Directory featured floorp lan and a variety of information about the tenant, news, p romotion, and events. Every user who come to use the e-Directory interchan geably . To update the content on the e-Directory, the administrator can directly connect to the local d atabase that contained in the kiosk. Each k iosk is able to connect to the management office (admin) to use existing lo cal n etworks. The e-Directory that located on each kiosk is run using the Adobe Air p latform on comp uters with Windows op erating sy stems. As for the directory that is p laced on the Central Park Mall website, e-Directory runs using Adobe Flash.
Picture 2e-Directory interface on kiosk and website
The e-Directory Kiosk which deployed on each f loor has actually been able to meet the needs of the user on any information about the Central Park Mall. But the investments for each kiosk was v ery high, r esulting in Central Park Mall can not p rovide it in every corner of the Mall. To access the e-Directory through website, users are required to have a Adobe Flash Player plug-in in, while today's common mobile dev ices such as tablets and smartp hones have started to leave the p lug-in due to the resources p roblems. This resulted in limited access to the e-Directory , only to the owner of the lap top and kiosk users only . In addition to the above infrastructure issues, other issues contained in the multi-story buildings and the area is the location search. Although the Central Park M all has p rovided the e-Directory, there's still a lot of visitors who have diff iculties to find their destination quickly and precisely . Esp ecially for first-time visitors who
come to Central Park Mall, certainly not understand about the structure, access, and what is offered on the Mall. Authors propose a solution to extend the reach of users and the number of eDirectory using mobile ap plications which runs on the Android op erating system. In addition to the features of e-Directory, the app lication also contained a routing or location search feature p owered by the A* algor ithm like a com mon outdoor navigation systems. This app lication can be connected d irectly to the existing Web server, and making it easier for adm inistrators to perform content management by p ushing content to all media dir ectory.
3. Data Collection To add navigation features on this application, it would require some additional data that has not availab le in p revious e-Directory. Here are the data p rep ared for this application design: a. 2D Floorplan b. Node’s Coordinates (tenant, transp ort, and path) c. Distance between node and adjacent node
After the data is ready , then the data can be integrated into mob ile app lications. The steps used to collect these data can be seen in the image b elow.
Picture 3Data Collection Technique
To get p recise location and ease for enter the data that have been prepared into the app lication. Any area that became an access p oint on this ap plication will be marked with interconnected nodes, these nodes were laid out on a p rovided grid to gen erate accurate coordinates.
Picture 4Node p lacement technique on gr id, to get coordinates
Picture 5Lay ersused in floorp lan
4. Design Accordin g to Krug (2005), an app lication or a good web site, should allow users complete their work easily and instantly . So that user can directly understand easily what to do with this app lication, the app lication's main lay out is made with action bars and dashboard models. This app lication design model p opularized by
Google in the Android UI Design Patterns session, Google I / O 2010 (Fulcher et al., 2010).
Picture 6 M obile Directory application structure
5. Implementation Below are the imp lem entation result of M obile Directory App lication on Central Park Mall.
Picture 7 Mobile Directory screenshot
Picture 8 Mobile Directory screenshot
6. Evaluation Based on the results of tests p erformed by the author and Central Park M all management, in this application there are some d isadvantages and advantages. Mobile App lication Directory has several advantages as follows: a. By using the testing hardware, p athfinding calculation results can be display ed very quick. b. The majority of Android device users can use this application p rop erly . Referring to the statistics presented by Google (2012), this app lication runs on a version of the most p opular Android p latform (Android 2.3.3-2.3.7), with 58.1% of all devices across the world can run this app lication. Also mentioned by Google (2012), that there is 18.4% (for a resolution of 320x480) and 67.1% (for 480x800 resolution) of the total Android device that supports a resolution of the layout used in this application. c. This app lication has a shortcut button to p erform routing and make calls from store details page. d. Pinch-to-zoom feature which are pop ular amon g smartp hone users were imp lemented well in this application to zoom in or out floorp lan map s. e. Ease to obtain the most current news and p romotions using internet connection. f. This app lication can still be used when the Internet connection is not available, because the database is stored on a local database store. g. The process of route searchin g is calculated directly by the application, without using an internet connection to the server. h. The user interface is attractive, intuitive and in line with the corporate identity of Central Park Mall..
It is inevitable that the app lication of M obile Directory still has some weaknesses that can be corrected in the next develop ment, these weaknesses are: a. This app lication does not store a cache of downloaded inform ation. b. Events and Promotions has not been equipped with a rep resentative picture. c. Does not reach all areas within the Mall, such as: toilet, pray er room, and p arking lot. d. The data management process is still using a direct access to the database, there's still no user friendly UI in backend.
7. Conclusion Based on observation and learnin g of this thesis, the author can take sev eral conclusions as follows: a. Trials which carried out by the internal managem ent of Central Park M all showed that this system can serve as an alternative media in add ition to kiosk and website directory , and the A * algorithm which used to find the best route within the Directions module p roved can be used to disp lay the best route to allow visitors in search a location in the Central Park M all. b. Although without any p ositioning sy stem, navigation program in this room works well lik e a common nav igation programs which runs outside the room usin g GPS. c. The program can be integrated with current running system in Central Park M all, additional d evelop ment that needs to be held was only a Web Service to link between databases with mobile ap p lications..
Lookin g at the results of implementation and the possibility to further research of this app lication, below are some su ggestions that may be useful to the next develop ment: a. Coordinates collection Method that are use today still use the conventional way, for the next development, floorp lan and node map ping can be using shapefile. Shap efile is a spatial data typ e which has additional geo gr aphical information in it. By using this data typ e, it's expected to accelerate the develop ment and the update p rocess.. b. Provide better data collection, so all regions can be covered in this app lication. Region that has not been covered such as: parkin g lot, p ublic facilities, and p arks.. c. QR Code Scan and NFC Tag features as the input location, so that future users do not need to manually input the initial location.. d. Add features to search a route between floors, so that all areas can be visited by both visitors. e. Move access of route search features to the Dashboard, so that user can know about the existence of such features.
References [1] Dharwiy anti, S., & Wahono, R. S. (2006). Pengantar unified modeling languag e (UML). Retrieved from http ://ilmukomputer.org/2006 /08/25/pen gantar-uml/ [2] Fulcher, R. N., Chris and Palm er, J., & Robertson, C. (2010). Android UI design patterns. Retrieved 01-06-2012 from http ://www.google. com/events/io/2010/sessions/andro id-ui-designp atterns.html [3] Google Android. Platform versions. (2012). Retrieved 01-02-2012 from
http ://developer.android.com/resources/d ashboard/platform-versions.html [4] Google Android. S creen sizes and densities. (2012). Retrieved 01-02-2012 from http ://developer.android.com/resources/d ashboard/screens.html [5] Jackson, Wallace. (2011). Android apps for absolute beg inner. New York: Apress. [6] Krishnaswamy , Nikhil. (2009). Comparison of efficiency in pathfinding algorithms in game development. Chicago: DePau l University. [7] Krug, Steve. (2006). Don’t make me think! A common sense approach to web usability. (2
nd
Edition). California: New Riders.
[8] Kusrini. (2007). Strategi perancangan dan pengelolaan basis data. Yogy akarta: ANDI [9] Le, M. H. V., Saragas, D., & W ebb, N. (2009). Indoor navigation system for handheld devices. Massachusetts: Worcester Polytechnic Institute. [10] Lester, Patrick. A* pathfinding for beginn ers. (2005). Retrieved 29-01-2012 from http ://www.policy almanac.or g/games/aStarTutorial.htm [11] Munir, Rinaldi. (2005). Matematika diskrit. (Edisi Ketiga). Bandun g: Informatika. [12] Munir, Rinaldi. (2009). Diktat strategi algoritma. Bandung: ITB. [13] Patel, Amit. Amit’s A* pages. (2011). Retrieved 18-01-2012 from http ://theory .stanford.edu/~am itp/GameProgrammin g/ [14]Prastowo, B. N. SQLite DBMS. (2010). Retrieved 22-01-2012 from http ://p loworks.wg.ugm.ac.id/p ublic.p hp ?filein=news&artikel=F9C3ACF02E 20689E [15] Putra, D. A. R. Sistem operasi mobile. (2010). Retrieved 22-01-2012 from http ://iy ozdamnation.wordp ress.com/2010/11/14/sistem-operasi-mobile/
[16] Russel, S., & Norvig, Peter. (2010). Artificial in telligen ce. A modern approach. New Jersey : Pearson Education. [17] Sulianta, Feri. (2010). IT ergonomics. Jakarta: Elex Media. [18] Suryani, Erma. (2006). Pemodelan & simulasi. Yogyakarta: Graha Ilmu. [19] Weisstein, E. W. Algorithm. n.d. Retrieved 24-01-2012 fro m: http ://mathworld.wolfram.com/Algor ithm.html
