Sunday, September 16, 2012

Lanka Trip Planner White Paper

DOWNLOAD as PDF

1.     ABSTRACT


Finding a solution for a problem using Artificial Intelligence (AI) can be viewed as a systematic search through a range of possible actions in order to reach the predefined goal or solution. Problem solving by using various searching algorithms is a common technique in AI. In this research paper, an approach taken to implement a trip planner using search algorithms of AI is discussed. Travel planning is a very complex & important task in day today life. Paper discusses why trip planning is hard? In addition, how planning process can be improved using AI technologies. Implementation detail of the application, Challenges faced in the implantation process and how researchers overcame those are also discussed. Future works that are planned to done in this field and the benefits of that constraint based travel planner are also highlighted in the paper.   
Categories and Subject Descriptors
I.2.5 [Artificial Intelligence]:  Programming Languages and Software - Expert system tools and techniques.
General Terms
Algorithms, Performance, Design
Keywords
Artificial intelligence, Travel planning


2.     INTRODUCTION


Sri Lanka is a beautiful country with many places that attract tourists. Planning a trip manually to visit some of these places is a harder job than it seems, because it requires detailed knowledge in several areas like distances between places, road conditions, food supply, accommodation etc. Planning process become more complicated as the factors like mode of transportation, number of participants, preferences of participants etc. begin to vary.
To ease the process of trip planning to some extent, automated software is created using AI technologies where users can input their preferences like starting town, trip duration, preferred sites and the software will plan the best route for the user based on preferences. To carry out this process efficiently application’s agent has to know the correct distances between places on the map, level of tourist attraction to a particular place, places to get accommodation facilities and food and an efficient algorithm to compute the best path for the user. 
In the next section of the paper describes background of this problem explaining problem description, current solutions, and existing resources.  The implementation details are described next explaining user Interfaces, algorithm used and data Stores. After that, problem and challenges faces in the process are described along with the ways used to tackle those. Before the conclusion, future works that are expected to do and ways to improve the software are described.

3.     BACKGROUND


3.1     Problem Definition


Trip planning is a hard job because it requires detailed knowledge about distances between places, road conditions, alternate routes, time to be spent at a particular site, food supply, accommodation, amount of money to be expended on tickets and booking services. Process of planning becomes even complicated when varying factors like mode of transportation, possible delays in travelling due to traffic or natural reasons, weather conditions, number of participants, preferences of participants are taken in to consideration. If we look at this problem in a more generic mathematical perspective, it is observed that this problem easily maps to the generic Travelling Salesmen Problem (TSP). Since TSP is a NP-Complete problem, we cannot find the optimal solution for this problem. Therefore, the planning has to be done with a sub optimal solution that will take us to the optimal solution as close as possible.

3.2     Current Solutions


Currently only available solution to tackle the problem of trip planning is to plan the trip manually. For the manual planning information can be taken from road maps, other people’s experiences, weather reports, timetables of transportation services etc. For example, Google maps can be pointed as a valuable resource for manual trip planning. As other valuable resources web sites like “lakdasun” (1) where people can share their experiences with others about trips they went, Sri Lanka Railways’ online train timetable and ticket booking service can be pointed out. Information gathered from these resources play a vital role when creating the knowledge base of the new software as it helps application to come up with best route possible with data that are more accurate.

3.3     Available Resources


As this new software is implemented using java programming language several existing data structures, file reading APIs and inbuilt UI components are used. For example as the application uses xml files to store core data for processing java xml libraries were used to access data in xml files. Using java xml libraries for this operation is much easier than implementing a way to read data from generic file reading methods. In the implementation, section of the paper it will be explained more about how existing resources are utilized to successfully implement the software and the advantages gained by using those resources.
It is observed that there are some software solutions created to address this problem in other countries both on line and off line.  (2) (3)Main problematic design decisions to take when developing a trip planner application are
·         Selecting a method to store persistence data
·         Selecting a suitable algorithm to compute path
·         How to manage data inside the program for computation. 
Details about how these problems are tackled are described in the later sections “Implementation” and “Problems & Challenges”

4.     IMPLEMENTATION


4.1     Functionality


Our system is not only giving the route of cities which traveler need to travel but also our system is capable of giving rough schedule of the journey. User can enter the preferred locations which traveler needs to travel through his journey. Afterwards user ask to enter the departure time, journey days, arrival time and meal preferences whether traveler likes to get regular meals in a visiting place or a well-known meal taking place. Possible route is giving by considering user-preferred locations. After getting route, our system is capable of generating possible rough plan for the journey. Our AI is planning travel by day by day. For a day, traveler visits several places and travel between cities. Our AI is considering the travelling times between cities, time for taking meals and time for visiting locations to plan the day schedule. This is an also hard task for AI. This becomes harder because we take several traveler preferences to schedule the day plan. Planning for day includes arranging the order of visiting location along with providing suggestions for breakfast, lunch and evening tea whiles considering the traveler preferences. If travel takes more than one day, our AI is providing suggestions for staying for the day which traveler needs to stay. When planning the day schedule, it is not possible to meet all the traveler preferences. As an example, consider the situation where algorithm is indicate  traveler travelling between cities when user specify that he wants to get meal at a visiting location at that time. It’s not possible because traveler travel between the cities but user specify that he need to have a meal at around that time at a visiting  location. Therefore, our AI is dealing it by indicating user that it is not possible to meet with that requirement while providing a suggestions for location for taking meals. Generating rough schedule is helpful for traveler in order to get understand about the travel order, which is more beneficial for a traveler. Our algorithm is capable of suggesting visiting locations, which can be visit through the journey, but traveler not specified it. This option is also more helpful for a traveler to know the places, which are passing through the travel. Then traveler can be adjusting the travel route by considering the locations, which are suggested by our algorithm. There are many constraints to planning the schedule, for an AI its need to be gradually developed. In our AI, we address many issues but it is not the prefect. Further, anyone can improve the efficiency of the planning algorithm.

4.2     Implementation Detail


In our trip planner algorithm, we mainly use a variation of the (4) (5). Here mainly algorithm runs using a list of places, a finished list, and an open list, as used in a normal BFS search. Here the difference happens, in how we used BFS.
 Let us start with the methods used here one by one. The main method we use here is the ‘get route’ method what this do is, given a set of preferred places and the starting place id it returns the route, that the user should follow in a integer array.  This ‘get route’ method uses other supporting methods to find the route. As an example, this ‘get route’ method uses ‘get neighbors’ method to get all neighbors to a node.  It uses ‘get all neighbors’ to get neighbors of the nodes in the open list. I am not going to explain where and why those methods are used, in this research paper (please refer to the code in order to get a perfect idea of how it is working). If I simply go through the main algorithm, it takes the neighbors of the starting node and then neighbors of newfound nodes until it find a preferred place (a place where user wants to visit). When it find a preferred place algorithm will generate a sub-route to that place form the starting place. Algorithm will continue taking the found preferred place as a starting point. Found preferred place will be removed from the preferred place list. This will happen in a greedy manner until all the preferred places are finished.
It is clear that this is not the optimal way of doing this. After all this is a NP-complete problem, so it is not a good idea to try to find an optimal solution for this problem. Therefore, our target is clear we have to find a sub-optimal solution that will take us to the optimal solution as close as possible. I looked at the existing algorithms that can solve this kind of problems. Two problems that was similar (not similar enough though) to our problem are, ‘Traveling Salesman Problem’ (6) (7) (8) and ‘Traveling Purchases Problem’ (9). While this gave us lot of thinking around our problem, those had lot of limitations that made it hard to use the existing solutions for our purpose. As an example, we can find that in ‘travelling salesman problem’ salesperson cannot travel via same city twice, which is not a problem in our scenario. In addition, if we look into ‘travelling Purchases problem’ we cannot find enough details on the web so that we can relate it to our problem. Considering those limitations in the existing problem, we thought of going towards a solution that will search for a travel route in a greedy manner.

4.3     User Interface

User will navigate through 3 main UI panels before coming into the final result of his journey. In the first panel, he will be asked to provide his preferences to the system. After selecting the preferred places user is asked to define time constrains, and meal taking constrains. After user provides all those details, we give him a full look of all the details he provided. With one click, he will be navigated to the result page.

User interface is one of major critical part in our system. User interaction is achieved through the User interface. We are providing several user interfaces, which are easy to understand, and highly user friendly. First user is providing an interface to select preferred locations. In this user interface, traveler needs to indicate the starting location of the journey. User can view locations, which are in a particular city and select preferred locations in that city. Until traveler adds all preferred locations in the city, traveler will not be able to see the visiting locations of another city.  Traveler need to add all the visiting locations in a city, which are preferred to visit during the travel. Through user interface user can see currently added visiting places. After finishing the selecting visiting locations, user will directed to another user interface, which need to be filled by the user. All interfaces are design in a way that reducing user typing by having combo boxes. This user interface user need to enter the journey days, departure time of the journey and the arrival time. Then user asks to selecting meal preferences during the travel. User can give an approximate time, which he prefers to take each regular meal. Along with time, user can specify he likes to take meal during the journey (visiting place) or a well-known meal-taking place (E.g.-restaurant) for taking meals. All these inputs are getting through user interface components such as combo boxes and check boxes, which are more user friendly for the user.
                                                                                                                                                                                After providing the inputs by user, next window shows entire user preferences list. This user interface generated in order to user to recall all the preferences, which are made during the user, interface interactions. Then user can view the final journey plan. According to given user constraints, if journey cannot be planned because of time limitation, then system will indicate that the journey cannot be planned. If our AI can successfully planned the journey according to user preferences, then user will receive a window which contains the route, order of visiting places which need to be visit during the journey, suggestions which contains the locations to take meals during the journey, suggestions about the visiting places other than the user specified and if journey is more than one day, suggestions for places which can be stay for each day. These user interfaces are design in a way that improving a user-friendliness in order to provide a more usability for user.

4.4     Data Handling


Here our main data storing technology is through xml. We had to do a decision here either we have to go with a database which requires internet connection to use our product or going with the xml structure that will store information that allows the offline access. However, use of xml definitely limits our extendibility and modifiability. We had to go with the xml solution as we are in the Sri Lanka where not a lot of users have internet connections.
When working with xml we use java xml libraries that made our life so much easy. Without that, we are still writing the code for reading xml. XmlReader class mainly reads the data from the database and loads that into a set of objects that we will use in the main program. Talking about the objects where data resides in, it is built in a hierarchy. At top, we have a city; each city has its own id and name. ‘id’ is mainly used for identification of the object. These cities are composed of visiting places, meal taking places, places where you can stay in the night, places where you can have a visit. We have made sure that we stick in to the object oriented structure while we are storing data. We went with this design mainly because of three things. OOP methods make code more maintainable. Identifying the source of errors becomes easier because objects are self-contained the principles of good OOP design contribute to an application’s maintainability. Next one is re usability, objects contain both data and functions that act on data, objects can be thought of as self-contained “boxes”. This feature makes it easy to reuse code in new systems. Thirdly, it is Scalability, OO applications are more scalable then their structured programming roots. As an object’s interface provides a roadmap for reusing the object in new software, it also provides you with all the information you need to replace the object without affecting other code. This makes it easy to replace old and aging code with faster algorithms and newer technology.

5.     PROBLEMS AND CHALLENGES


How to store graph so that it easy to change and retrieve? This was the main problem that we had in our mind, we thought of a database at the first step. However, in order to use a database, user should always be connected to the internet to use that app. Therefore, we started thinking about a local data storing method. As our data, normally do not go through a rapid change we are always allowed to go to a local data storing method. Our solution was XML, which is a semi-structured way to store data. With XML, we had to face several problems. First, will it be hard to manipulate XML data with java? As a solution to that, we found a java library to work with XML. Other problem is the scalability of XML files. Still we are finding ways to overcome scalability problems.
Another problem that we came across was how the graph is represented in the program (An array list, adjacency matrix, etc.)? We went with the adjacency matrix because of its simplicity and the fast access. With adjacency matrix, we can have a constant time access to the journey details between two cities.
Next problem was how deep we have to go into the problem? Do we have to show the route within a city? Do we have to show the route to meal taking places? We concluded with that we do not have to do that far. So we thought of not considering the path within a city and path to a meal place.

6.     FUTURE WORK


 In the development process, it is observed that performance of a selected algorithm depends on the context of the given problem’s parameters.  For the future development of the software, it is planned to implement the systems algorithm to be changed dynamically depending on the problem at hand using the strategy design pattern.
Most of the better sub optimal solutions for travelling salesmen problem are implemented using the genetic algorithms (GA). Since the trip-planning problem is also closely related to the TSP, it is inevitable that a solution based on genetic algorithms would perform better than the current algorithm, which is a variation of BFS. When a set of different sub optimal algorithms are created they can be switched accordingly to get the necessary performance with the strategy design pattern.
According the existing architecture of the application user has to download the java application from the internet and run it locally to get the output. Moreover, user has to periodically update the data used by the application for the operation via internet. Other than this architecture, we have planned to implement the application as web services, which can be accessed using a web browser, which support client side scripting. Therefore, that user can access the application from any computer with an internet connection and a web browser. With this web application, it is planned to give an opportunity to the users of the system to enter data of their trip experiences. Therefore, the Application can learn from those feedbacks and learn and update existing data to give performance that is more robust to users.

7.     CONCLUSION


In this research paper, an approach to create a trip planner application based on AI theories is discussed. Trip planning is closely related to travelling sales men problem, therefore we have to go with a sub optimal solution for the trip plan because it is not possible to come up with an algorithm to get the optimal solution for all the preferences.
Created application is implemented as an off line java application in which the data should be updated periodically via internet. XML files are selected as the medium to store persistence data for the application. A variation of BFS is used in the application to compute the required trip path according the preferences input by user.
As future developments of the application, existing algorithm to compute path will be replaced with a set of algorithms, which will be switched according to the user preferences. In addition, the application will provided as a web services, which can be accessed and used via a modern web browser.  It is planned to implement a way to take feed backs from the users about the trips they went, and implement learning part to the AI so that the data will be automatically changed based on the users feed backs to create more accurate plans in the future.

8.     Works Cited


1. Gallage, Malinga. Lakdasun. [Online] 2011. [Cited: 01 13, 2012.] http://www.lakdasun.org/.
2. NSW transport info. [Online] [Cited: 01 12, 2012.] http://www.131500.com.au/plan-your-trip/trip-planner.
3. Trans Link. [Online] [Cited: 01 13, 2012.] http://tripplanning.translink.ca/.
4. Breadth-first search. Wikipedia. [Online] Wikipedia. [Cited: 02 22, 2012.] http://en.wikipedia.org/wiki/Breadth-first_search.
5. Breadth-First Search Traversal Algorithm. [Online] [Cited: 02 10, 2012.] http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/breadthSearch.htm.
6. Weisstein, Eric W. Traveling Salesman Problem. Wolfram MathWorld. [Online] [Cited: 02 13, 2012.] http://mathworld.wolfram.com/TravelingSalesmanProblem.html.
7. The Traveling Salesman Problem. [Online] [Cited: 01 30, 2012.] http://www.tsp.gatech.edu/.
8. Karla Hoffman, Manfred Padberg. Traveling Salesman Problem-2. [Online] [Cited: 02 11, 2012.] http://iris.gmu.edu/~khoffman/papers/trav_salesman.html.
9. Clelland, Ian. Traveling purchaser problem. Wikipedia. [Online] [Cited: 02 21, 2012.] http://en.wikipedia.org/wiki/Traveling_purchaser_problem.


Content

Email:

Syndicators/Readers:

FaceBook: