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.
No comments:
Post a Comment