Transcript Total Order Planning and Partial Order Planning

Online Collaborative Time
Management System using
Artificial Intelligence - Planning
Project Advisor: Dr. Chris Pollett
Committee Members:
1) Dr. Robert Chun
2) Dr. Teng Moh
Anand Sivaramakrishnan
Agenda
•
•
•
•
•
•
Why Planner?
Building a Planner
Project
Algorithm
Usability Test
Conclusion
Why Planner?
• Existing Online Planners save paper (because
users do not buy notepads) and also have an
elegant UI. Eg, Grademate, Playware, Google
• Sequence of actions displayed as inputted
(organized). They lack intelligence (logic)
• My project is about creating a planner that
offers advise as to what sequence to be
followed, like a consultant
• The planner should have a brain (to think) of
its’ own instead of just recording user inputs
and displaying them as reminders
Planning
Definition: Generation of a sequence of
actions to achieve a goal is called planning.
This is exactly what the backend of the
product does when it is fed with user inputs
such as actions and goals.
Building a Planner
• Situation Space Planner – World State
• There are two types of planners:
Progression Planner: It searches forward from
the initial situation to the goal situation.
Regression Planner: It searches backward
from the goal situation to the initial situation.
State Space Planning
Project
• Name – MasterPlanner
• Purpose – Planning using Artificial Intelligence,
Regression Planning
• The Website is collaborative in nature. It’s basic
purpose is to achieve collaborative planning
among groups
• The UI has been tried to be made as user friendly
and easy as possible
• A complex back end used to make the front end
as simple as possible
Algorithm – Regression Planning
• Traversal from Goal State to Initial State
(Backward Heuristic Search).
• This project makes use of Regression Planning
because:
(a) Relevant Actions
(b) Lower Branching Factor
Algorithm - Unification
• Actions are chosen based on Unification
between Preconditions of actions(goal in the
first iteration) we are going to satisfy and the
actions whose effect unifies with the above
precondition.
• The action is chosen only if all the effects of an
action unifies with all the predicates in the
World State.
Unification
• Unification – Pass
fruit(apple,pie)
vs fruit(apple, X)
• Unification – Fail
1) fruit(apple,pie) vs
2) team(andy, Captain)
vs
team(Captain, jim)
fruit(pie, apple)
Algorithm - Objects
Classes and Objects - Predicates
• General AI - Classes / Common Nouns
home( b, x) AND car (a)
• Website – Objects / Proper Nouns
john_home( Clean, Lights) AND
andy_car( Engine, Fuel)
Algorithm - Backtracking
• Ensures no conflicts – Logical sequence of
actions based on Unification
• If limited actions then will implement
backtracking
• If it is still not able to satisfy a precondition,
then it will report failure, prompting the group
members to add more actions
World State (Table-DB)
Item
Property
Value
Action
Home
Lights
on
78
Home
Cleanliness
in-complete
43
Home
Food
ready
22
Collaboration
• Actions and Goals are group specific
• Groups can add any objects as items, again
items are group specific
• Flexible Group Involvement
• Accountability
• No Sub Groups
• Scope – Non Corporate Networks
Test Cases - Demo
Usability Test Feedback
• Cryptic terms like Preconditions and Effects are
confusing and uneasy to understand
• Un-join Groups is again difficult to understand, a
term like ‘Leave Groups’ is easier to understand
• Empty Database for new Groups, therefore for
starters (groups new members) this could be very
frustrating
• Lack of subsections within a Group such as
finance-team, accounts-team
• No dates or deadlines
Response to User Feedback
• The caption ‘Un-Join Groups’ has been
changed to ‘Leave Groups’
• Also terms like ‘Preconditions’ and ‘Effects’
will be changed to ‘Before’ and ‘After’
• We could pre add a few items and
corresponding properties by default to every
new group in the system
Conclusion
• User – Freedom and Flexibility
• Learnt how a system in planning is built. Was
very keen to do it
• Implementing the algorithm and designing the
database for the system were the most
challenging tasks
• Keen on getting the site on production
References
• [1995] Artificial Intelligence: A Modern Approach.
Peter Norvig, Stuart Russell. Prentice Hall Series.
1995.
• [1999] Recent Advances in AI Planning. Sussanne
Biundo, Maria Fox. ECP, Springer. 1999.
• [1997]Craig Knoblock, Qiang Yang Relating the
Performance of Partial Order Planning Algorithms
to Domain Features . SIGART Bulletin, Vol. 6, No.
1, 8-15
Thank You
Q&A