School of Science and Technology 科技學院
Computing Programmes 電腦學系
| Programme | Bachelor of Science with Honours in Web Technologies |
| Supervisor | Dr. YC Zhao |
| Areas | Mobile Applications |
| Year of Completion | 2015 |
The aims of this project are to improve the availability and efficiency on book finding. This can be done by adding additional function onto the original system and developing multi-platform version of the searching system. In addition, the system can generate a map with the shortest path for user to reach the books they are searching for.
The main objective to achieve the aim is developing a path generating function. This function should provide a path for user to reach all the books they are looking for on a 2D library map. There are also some sub-objectives improving the availability and efficiency of the searching process.
The expected result after applied the new Path finding method is we can find a shortest path that passes every books we want, then we can pick all the books up along this path, without wasting time on the shelves that do not contain the books we want. Also our project needs to mix in some basic library functions, which help people manage books (checking status, renewing books, and so on), such as the principal functions of Hong Kong Library system. Our project is going to build up an app that can find the locations of books and show a suggested path on the floor plan. The app will let users create a wishlist of books, and then it will calculate the shelves' locations and generate a path.
User can use the book searching function or login when they first come to the website. Different from book searching, they are required to login for using the book storage and path generating function. Path will be generated and shown on the library floor plan with books in the storage list. The overview on path generating website structure is shown below:
If the library consists of several districts, we will first divide the problem into subproblems on each district. For each district we construct a MST as Christofides Algorithm. We calculate the distance between each target and the ending point and sort them in descending order, following which we can generate the path along MST. In this algorithm, we consider the number of books that a user has to carry along the path. Therefore it is more comfortable for users to follow such a path.
This algorithm also considers the factor of ‘Area’. As shown below, bookshelves are separated into two sides. Although some books from two sides may share the same distance to the ending point, they are considered separately in different district. There are 3 types of points for path calculation (Blue, Red and Green):
By combining Html5 and jQuery coding, path can be generated by given starting point and ending point. In the below example, both cornered point are the starting point and ending point, while the points between are animation points moving from the starting point to the ending point.
In our circumstance, the floor plan has two main areas that contain a lot of bookshelves. We can partition the floor plan into multiple districts so that it is easy to organize and calculate the path in a reasonable time.
We adopt Revised MST based Approximation Algorithm to our application. There are the steps that apply this algorithm into the application:
As the result of above path finding, we suggest user go to the farthest first and the nearest last. The Priority are:
Because we concern both path length and user experience of the carrying ability. Therefore, we recommend that go to the farthest point to pick up the first book. At last, the user will carry all the books at the nearest library counter position. We think this design may feel more comfort for the user experience. Below is a detail flow testing in the development system:
Using book's code to locate where the book is works well. It can accurately tell that the book is on which side of a bookshelf. Here is an completed example:
The path above is calculated base on RMST. The path is overlapping but we have 2 methods to presenting the path's sequence clear: the colors of points and the books list. The color is default from red to blue in ascending order and so as the books list.
In this section we will evaluate our application's components, target user’s opinions and performance differences between the 3 path calculation methods we had mentioned.
Over 90% of users found the path on the floor path is simple for them to follow the path. They liked the colored points with books list beside the floor plan so that they can know which book they are going for. Besides, they found understanding the sequence is easy and some of them suggested that we should apply rainbow color on the colored points.
Over 75% users believe our path is accurate on locating books. However, some of them found that colored points between bookshelves are not accurate enough as it is not pointing out which side the book is. We have tried to do that by presenting the colored points onto bookshelves but they are too small on the floor plan which makes the outcome much more confusing.
Almost all users like the path calculated by RMST. They like it as it is more user friendly although the length is longer. They found the path is similar between Christofides Algorithm and RMST but RMST is more comfortable as well. A few of them believe brute force is the best for them as the path is the shortest.
Nearly half of users found comfortable at most of their concern. They did not want to carry lots of books walking around the library and that makes distances the second concern of them. Response time for RMST and Christofides Algorithm is reasonable but brute force take much longer time to calculate.
In this project we discuss how to develop an application for the multi-destination path finding problem. We use CIHE library as an example and design an approximation algorithm, which considers the efficiency, performance and user experience.
Multi-destination path finding problem can model many other problems such as supermarkets, schools, and governments, we also introduce the design of showing paths and floor plan in the mobile application. The display and calculation of path still have a huge room to improve such as the overlapping path, supporting and displaying the path for multi-floor building and cross-builds calculation.
Since it is NP-complete to find the optimal, it is very difficult to find the optimal path in polynomial time. Hence there is a trade-off between performance and the efficiency. There is still room to improve this app such as the display of path on multi-floor. For example if we want to apply this app onto supermarket, there are shopping carts so that customer's carry ability around the market might not be the first consideration. We believe our work is a good start for a kind of applications' development, which will benefit the users who are not familiar with the environment. Besides the normal functions, there is one possible direction. If some sensors are installed in the environment, we may use these sensors to point out the correct direction that leads the user to the targets along the path. How to utilize the sensors in the app will be the future work.
Copyright Lau On Ki, Lee Sung Hei, Cheong Chi Yin and YC Zhao 2015
Jonathan handles all external affairs include business development, patents write up and public relations. He is frequently interviewed by media and is considered a pioneer in 3D printing products.
After graduating from OUHK, Krutz obtained an M.Sc. in Engineering Management from CityU. He is now completing his second master degree, M.Sc. in Biomedical Engineering, at CUHK. Krutz has a wide range of working experience. He has been with Siemens, VTech, and PCCW.
Hugo Leung Wai-yin, who graduated from his four-year programme in 2015, won the Best Paper Award for his ‘intelligent pill-dispenser’ design at the Institute of Electrical and Electronics Engineering’s International Conference on Consumer Electronics – China 2015.
The pill-dispenser alerts patients via sound and LED flashes to pre-set dosage and time intervals. Unlike units currently on the market, Hugo’s design connects to any mobile phone globally. In explaining how it works, he said: ‘There are three layers in the portable pillbox. The lowest level is a controller with various devices which can be connected to mobile phones in remote locations. Patients are alerted by a sound alarm and flashes. Should they fail to follow their prescribed regime, data can be sent via SMS to relatives and friends for follow up.’ The pill-dispenser has four medicine slots, plus a back-up with a LED alert, topped by a 500ml water bottle. It took Hugo three months of research and coding to complete his design, but he feels it was worth all his time and effort.
Hugo’s public examination results were disappointing and he was at a loss about his future before enrolling at the OUHK, which he now realizes was a major turning point in his life. He is grateful for the OUHK’s learning environment, its industry links and the positive guidance and encouragement from his teachers. The University is now exploring the commercial potential of his design with a pharmaceutical company. He hopes that this will benefit the elderly and chronically ill, as well as the society at large.
Soon after completing his studies, Hugo joined an automation technology company as an assistant engineer. He is responsible for the design and development of automation devices. The target is to minimize human labor and increase the quality of products. He is developing products which are used in various sections, including healthcare, manufacturing and consumer electronics.
| Course Code | Title | Credits | |
|---|---|---|---|
| COMP S321F | Advanced Database and Data Warehousing | 5 | |
| COMP S333F | Advanced Programming and AI Algorithms | 5 | |
| COMP S351F | Software Project Management | 5 | |
| COMP S362F | Concurrent and Network Programming | 5 | |
| COMP S363F | Distributed Systems and Parallel Computing | 5 | |
| COMP S382F | Data Mining and Analytics | 5 | |
| COMP S390F | Creative Programming for Games | 5 | |
| COMP S492F | Machine Learning | 5 | |
| ELEC S305F | Computer Networking | 5 | |
| ELEC S348F | IOT Security | 5 | |
| ELEC S371F | Digital Forensics | 5 | |
| ELEC S431F | Blockchain Technologies | 5 | |
| ELEC S425F | Computer and Network Security | 5 |
| Course Code | Title | Credits | |
|---|---|---|---|
| ELEC S201F | Basic Electronics | 5 | |
| IT S290F | Human Computer Interaction & User Experience Design | 5 | |
| STAT S251F | Statistical Data Analysis | 5 |
| Course Code | Title | Credits | |
|---|---|---|---|
| COMPS333F | Advanced Programming and AI Algorithms | 5 | |
| COMPS362F | Concurrent and Network Programming | 5 | |
| COMPS363F | Distributed Systems and Parallel Computing | 5 | |
| COMPS380F | Web Applications: Design and Development | 5 | |
| COMPS381F | Server-side Technologies and Cloud Computing | 5 | |
| COMPS382F | Data Mining and Analytics | 5 | |
| COMPS390F | Creative Programming for Games | 5 | |
| COMPS413F | Application Design and Development for Mobile Devices | 5 | |
| COMPS492F | Machine Learning | 5 | |
| ELECS305F | Computer Networking | 5 | |
| ELECS363F | Advanced Computer Design | 5 | |
| ELECS425F | Computer and Network Security | 5 |
