Special Topics CAP 6938
University of Central Florida
Popular in Course
Popular in System Engineering
This 26 page Class Notes was uploaded by Khalil Conroy on Thursday October 22, 2015. The Class Notes belongs to CAP 6938 at University of Central Florida taught by Gita Sukthankar in Fall. Since its upload, it has received 52 views. For similar materials see /class/227213/cap-6938-university-of-central-florida in System Engineering at University of Central Florida.
Reviews for Special Topics
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 10/22/15
K CAP693802 Plan Activity and Intent Recognition Review of Material Instructor Dr Gita Sukthankar Email gitarseecsucfedu Schedule T amp Th 130245pm Location CL1 212 Office Hours HEC 232 T 3430pm Th 101130am Exam Format Exam Oct 4th closedbook can bring 1 page of notes Oct 11th 2 page writeup of your project results informal inclass presentation Oct 18th Project Phase 2 Chance to start a new project or refine your old one 1 page writeup and informal class presentation describing changes you want to make in your project CAP6938 Dr Gita Sukthankar Definitely on Exam Specific questions on Bayes networks Hidden Markov Models Representation Forward algorithm General research questions on the 5 papers Kautz Tambe Pynadath Kaminka Starner CAP6938 Dr Gita Sukthankar Not on Exam Logic proofs or egraphs SOAR Inference using stochastic grammars Variable elimination for loopy graphs Details of BaumWelch algorithm Vision based tracking CAP6938 Dr Gita Sukthankar What makes PAIR hard High computational cost Plan library requirements Libraries can be incomplete or inaccurate Difficult to author making learning attractive Individual differences Mistakesirrational behavior Domainspecific characteristics make generalization across domains difficult Specific to activity recognition Identifying transitions between behavior Data association Obtaining reliable tracking data vision CAP6938 Dr Gita Sukthankar Application Areas Robocup not on the exam Quality of Life not on the exam Adversarial reasoning for games and battlefield analysis Tambe Gesture recognition Starner CAP6938 Dr Gita Sukthankar Symbolic Consistencybased Based on the idea that plan recognition is a consistencychecking process A model matches the set of observations if the observed actions don t violate any of the constraints specified in the plan library Example techniques first 2 weeks of reading Event hierarchy circumscription Kautz Event trackingmodel tracing Tambe Fastcomplete symbolic plan recognition Kaminka Output return complete set of models that pass consistency checking CAP6938 Dr Gita Sukthankar Probabilistic Likelihoodbased Based on the idea of selecting the plan that has a high probability based on the observed evidence Belief is usually calculated using some variant on Bayesian belief update but DempsterShafer evidential reasoning has also been used Includes both directedundirected graphical model based procedures Examples dynamic Bayes networks DBNs hidden MarkovsemiMarkov models HMMs Output model with the maximum likelihood at the current time step given the set of previous observations CAP6938 Dr Gita Sukthankar Decisiontheoretic Utilitybased Based on the idea that the agent is rational and acts to maximize a known utility function Plan recognition process occurs by calculating utility of all plans in current situation Gametheory is applicable for adversarial reasoning when the agent is simultaneously trying to maximize their utility while minimizing their opponents Output a rankordering of models by utility Note this method is wellsuited for prioritizing or pruning the search process and is often used in combination with one of the previous methods CAP6938 Dr Gita Sukthankar 9 Event Hierarchy Circumscription Event hierarchy General axioms My Evenl V d apg mcilihih D Enu Event Entrapment Prepare MES Was immin Disnss anzzmm Temporal i a 6 05 EDII Fas a Make Dish 2 Meal sq Dish Put15mm Make Noooles 15quot Make Make Make Fenucini Spaghetti Spaghem Make Anreda Pesto Marmara auae MEKE Cthken Mannm s2 55 Make mm Marmara Y I Sau e as a Make Spaghelll H Kautz A Formal Theory of Plan Recognition and its Implementation in Reasoning about Plans CAP6938 Dr Gita Sukthankar 10 Kautz s Model First order predicate calculus Event hierarchy logical encoding of a semantic network Event predicates Abstaction axioms Decomposition axioms General axioms hardest to use for inference Includes temporal constraints between the steps Equality constraints between the agents executing steps or objects involved in steps Preconditions Special event predicates Eng AnyEIent top level abstraction CAP6938 Dr Gita Sukthankar Kautz s Assumptions Exhaustiveness Known ways of specializing an event type are the only ways of specializing it Disjointedness Types are disjoint unless one abstracts the other or they abstract a common type ComponentUse Seeing an event implies the disjunction of the plans which include it as a component Minimum Cardinality Assumption Assume parsimony the minimum number of plans to explain the observations CAP6938 Dr Gita Sukthankar RESC Algorithm Tambe Simple insight model what you would do if you were in the opponent s position What are problems with this High overhead must program an agent capable of solving the problem Modeling the opponent s world state can be difficult what is the opponent s sensor model Maintaining multiple hypotheses is even more expensive What are the strengths Allows designer to leverage extra domain knowledge Does not require enumerating chains of possible events CAP6938 Dr Gita Sukthankar 13 Ambiguity in Event Tracking Ambiguity the bane of plan recognition Potential solutions Maintain multiple operator hierarchies continue considering all valid hypotheses Delay until more evidence presents itself Tambe solution attempt to resolve ambiguity and commit to a single interpretation Passive ambiguity resolution gametheoretic Active resolution modify agent s actions to resolve ambiguity Detect incorrect interpretation through match failure Recovery mechanisms assumption injection backtracking CAP6938 Dr Gita Sukthankar 14 Stochastic Grammars Refer to the shorter version of the Pynadath paper Understand how to represent plan recognition as a grammar parsing problem Difference between plan recognition using contextfree and contextsensitive grammars Understand Pynadath s representation of the driving domain CAP6938 Dr Gita Sukthankar Speedups for Plan Recognition Smart data structures Kaminka Use of dynamic programming forwards backwards algorithm variable elimination Be able to suggest new speedups Understand the purpose of the ones proposed in the Kaminka paper Speeding observation matching tagged feature tree Improving efficiency of current state query Hypotheses graph data structure CAP6938 Dr Gita Sukthankar 16 RHIBS Omebal aility 39 Pmdum R1116 F HI I WG5 My WI va Ial ginalizatimi P if it P F J 1 39 Xbinmy 2 Pa P can 199 Jack mesemosm CorporatixmamlDaphm Eo m39 Starrmummy Alln39gdsreimred 11 Bayes Rule FJHE39PiH IEJHTEEPEE IHJNH PLH lg J 4 PiE m h39i39P39 2131 PtjeJi39jHPCe f Pae hi3P139QF1f HIE h39EJPUIT Pee 1 uPt j a can 199 Jack eeseh u oso CorporatimiamlDaphm Holler Starrmummy Alln39gdsreimred 12 What is a Bayes belief net Compact representation of joint probability distributions via conditional independence Family of Alarm Qualitative part 7 E 3 PM EB Directed acyclic graph DAG e b 09 01 Nodes random vars f 75 02 08 Edges direct influence lt1 f b 9 1 6 3 001 099 Together Define a unique distribution in a factored form ntitative part Set of conditional probability distributions dgg eg gggm rglt r7EPA BEPR EPC A 19 Figure from N Friedman Conditional probability distributions CPDs Burglary Earthquake Each node specifies a distribution over its values given its parents values PXi Xpai Full table needs 25131 parameters BN needs 10 Radio 39DCDITI DI DI U7 397 7 39 31 PC31PCEIBPCAIBJEPRABEPWIEARE 1 2 4 8 16 H3 ME PltAIB E PRlE PClA WWW Pead1988 Iimzls Def inference f l DBMS filtering PM 1W 1 T p tedicticu gtH PEXEHHZI l ir39 i i39 t r 7 E xedlag PEEKLl fan131 ammthmg t T f e39 IntEmmi l PIECE 1amp1 lej mn mg T uf mej CAP6938 Dr Gita Sukthankar 21 CPDs for HMMS W a11 CL12 CL13 0 G22 G23 u 0 O Q33 lt 9 quota Astate transition matrix meter tyeing Para I T pX1T7Y1T PX1PY1X1 H PXtiXt1PY3iXt 152 Transition matrix let1 Observation matrix mgp atardgm on PX1 239 77239 22 Nuisance variablehidden node that we don t care about but that we don t know the value for Inference tasks Posterior probabilities of Query given Evidence Marginalize out Nuisance variables Sumproduct z x 255 1 6 x W n Lajq Lmnrkahpajnawe Most Probable Explanation MPE Viterbi maxproduct 13 arg axPmqm arg axPxqwe Marginal Maximum A Posteriori MAP maxsumproduct 3 arg mxaxPccqlxe arg mangqu can me 5371 Variable bucket eliminationm Push sums inside products generalized distributive law Carry out summations right to left storing intermediate results factors to avoid recomputation dynamic programming CAP6938 Dr Gita Sukthankar Forwards algorithm filtering 04757 CAP6938 Dr CL D quoth R Gita Sukthal at Git 1 Use the Markov assumptions PK 15 h I39vr h 1739 luiytix gt lyiztff ub gr Jiylzt l PCQthf J ZPXfX 1 PX 1lyl 1 i etJV 4 L 0 30g17 1 7J b J 25 at X at gtilt ATat Gesture Recognition Starner Be able to describe how the recognition aspect of the system works Don t have to understand the visual tracking Don t have to understand the use of Gaussian probability densities CAP6938 Dr Gita Sukthankar 26
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'