School of Science and Technology 科技學院
Computing Programmes 電腦學系

A Book Finding App for the Library

Lau On Ki, Lee Sung Hei and Cheong Chi Yin

ProgrammeBachelor of Science with Honours in Web Technologies
SupervisorDr. YC Zhao
AreasMobile Applications
Year of Completion2015

Objectives

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.

Background and Methodology

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):

  • Blue points are the intersection points of walking paths;
  • Red and Green points represent bookshelves. The paths can continue in x-coordinate for Red points and in y- coordinate for Green points.

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:

  • Construct MST
  • Generate Path from the farthest to the nearest

As the result of above path finding, we suggest user go to the farthest first and the nearest last. The Priority are:

  • Red point: Accounting and finance
  • Dark red point: Theories of personality
  • Purple point: Biological psychology
  • Blue point: The relational database dictionary & Java 2: the complete reference

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.

Evaluation

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.

Conclusion and Future Development

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 Chiu
Marketing Director
3DP Technology Limited

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.

Krutz Cheuk
Biomedical Engineer
Hong Kong Sanatorium & Hospital

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
Software and Hardware Engineer
Innovation Team Company Limited

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 CodeTitleCredits
 COMP S321FAdvanced Database and Data Warehousing5
 COMP S333FAdvanced Programming and AI Algorithms5
 COMP S351FSoftware Project Management5
 COMP S362FConcurrent and Network Programming5
 COMP S363FDistributed Systems and Parallel Computing5
 COMP S382FData Mining and Analytics5
 COMP S390FCreative Programming for Games5
 COMP S492FMachine Learning5
 ELEC S305FComputer Networking5
 ELEC S348FIOT Security5
 ELEC S371FDigital Forensics5
 ELEC S431FBlockchain Technologies5
 ELEC S425FComputer and Network Security5
 Course CodeTitleCredits
 ELEC S201FBasic Electronics5
 IT S290FHuman Computer Interaction & User Experience Design5
 STAT S251FStatistical Data Analysis5
 Course CodeTitleCredits
 COMPS333FAdvanced Programming and AI Algorithms5
 COMPS362FConcurrent and Network Programming5
 COMPS363FDistributed Systems and Parallel Computing5
 COMPS380FWeb Applications: Design and Development5
 COMPS381FServer-side Technologies and Cloud Computing5
 COMPS382FData Mining and Analytics5
 COMPS390FCreative Programming for Games5
 COMPS413FApplication Design and Development for Mobile Devices5
 COMPS492FMachine Learning5
 ELECS305FComputer Networking5
 ELECS363FAdvanced Computer Design5
 ELECS425FComputer and Network Security5