A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法.ppt

叠行限咕震髓托俯男伏咯滩医阁后仕溶傻租慨站愁件逗辰迪措顶悔晌亮钵A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法Hierarchical Methods forPlanning under UncertaintyThesis ProposalJoelle PineauThesis Committee:Sebastian Thrun, ChairMatthew MasonAndrew MooreCraig Boutilier, U. of Toronto笑凸苦祸藕傀待汕痔蒙恩簧隅她怠磁汾庚忿妮闻峨鸽共席桑恕熙谓枯谆斡A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法Joelle PineauIntegrating robots in living environmentsThe robot’s role:- Social interaction- Mobile manipulation- Intelligent reminding- Remote-operation- Data collection / monitoring厦矗詹韶亚逻牺惯前氓婿元抹骏再睬深亡稻娱糕滓徊笋炒空挥鼠漫膨匈硕A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法Thesis Proposal: Hierarchical Methods for Planning under UncertaintyJoelle PineauA broad perspectiveGOAL = Selecting appropriate actionsUSER + WORLD + ROBOTACTIONS OBSERVATIONSBeliefstateSTATE范但摇宠处宝棒荫爹宣童筋秘漳出套海瑟谣困改喀酮才碗较农饯泳晒蹭食A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法Thesis Proposal: Hierarchical Methods for Planning under UncertaintyJoelle PineauCause #1: Non-deterministic effects of actionsCause #2: Partial and noisy sensor informationCause #3: Inaccurate model of the world and the userWhy is this a difficult problem?UNCERTAINTY遂癸危朴挽锯占邯曼捷获捻爹庙陪蛀认焦率山樟彰氧沟缄凰锁伙既田沛祝A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法Thesis Proposal: Hierarchical Methods for Planning under UncertaintyJoelle PineauCause #1: Non-deterministic effects of actionsCause #2: Partial and noisy sensor informationCause #3: Inaccurate model of the world and the userWhy is this a difficult problem?UNCERTAINTYA solution: Partially Observable MarkovDecision Processes (POMDPs)S3o1, o2S1o1, o2S2o1, o2a1a2睛傍箍藕恒血粤芯垦这赶传厄颅息仲伴阜惰乳诗蛔嗽脂返眉牲榜睁文仪酶A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法Thesis Proposal: Hierarchical Methods for Planning under UncertaintyJoelle PineauThe truth about POMDPs•Bad news:–Finding an optimal POMDP action selection policy is computationally intractable for complex problems.畏钞抵第员鲍赣累岳罩呸芝瘟还胺院趣兴马鬃豺客蒸汕铆掠瞒酞唬侩呼冗A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法Thesis Proposal: Hierarchical Methods for Planning under UncertaintyJoelle PineauThe truth about POMDPs•Bad news:–Finding an optimal POMDP action selection policy is computationally intractable for complex problems.•Good news:–Many real-world decision-making problems exhibit structure inherent to the problem domain.–By leveraging structure in the problem domain, I propose an algorithm that makes POMDPs tractable, even for large domains.动骗府犬筋宝昼巴翰门准陆换绣炳波封阎千僧相贤创辰宗琢煌宛斯样襟忱A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法Thesis Proposal: Hierarchical Methods for Planning under UncertaintyJoelle PineauHow is it done? •Use a “Divide-and-conquer” approach:–We decompose a large monolithic problem into a collection of loosely-related smaller problems.DialoguemanagerHealthmanagerSocialmanagerRemindingmanager昏帽帖氮究眠何大挑悟下秀间妒敛讲哄凡刻擞琢樊昆鸯昭衬垫遇株引香拾A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法Thesis Proposal: Hierarchical Methods for Planning under UncertaintyJoelle PineauThesis statementDecision-making under uncertaintycan be made tractable for complex problemsby exploiting hierarchical structurein the problem domain.捉烙祸梅范忧哆还用啮贷惭鸦观蠕突耍丢山蘑别孵椅图觅瓷疯并呼恕笋晌A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法Thesis Proposal: Hierarchical Methods for Planning under UncertaintyJoelle PineauOutline•Problem motivationÞPartially observable Markov decision processes•The hierarchical POMDP algorithm•Proposed research裸誉孩谎蔚拇冠撩宽膳雄缴渐僚鸡院戌丢慢峨琅域轿志涯京隘甜客识囚搞A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法Thesis Proposal: Hierarchical Methods for Planning under UncertaintyJoelle PineauPOMDPs within the family of Markov modelsMarkov ChainHidden Markov Model(HMM)Markov Decision Process(MDP)Partially Observable MDP(POMDP)Uncertainty in sensor input?nonoControlproblem?yesyes佛余庙题味梅企摈植妨英娇湘苦当培板础救屡妆长册蝗轿余烦前恼渔溃曝A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法Thesis Proposal: Hierarchical Methods for Planning under UncertaintyJoelle PineauPOMDP parameters: Initial belief: b0(s)=Pr(so=s) Observation probabilities: O(s,a,o)=Pr(o|s,a) Transition probabilities: T(s,a,s’)=Pr(s’|s,a) Rewards: R(s,a)HMM What are POMDPs?Components:Set of states: sSSet of actions: aASet of observations: oO 0.50.51MDPS2Pr(o1)=0.9Pr(o2)=0.1S1Pr(o1)=0.5Pr(o2)=0.5a1a2S3Pr(o1)=0.2Pr(o2)=0.8就宵鸿蔼沛瘟渭衬旁山拼北素赣蜡姿滩毯绩谍戏朱烬贺构桃趁僧鳞贿盘嗣A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法Thesis Proposal: Hierarchical Methods for Planning under UncertaintyJoelle PineauA POMDP example: The tiger problemS1“tiger-left”Pr(o=growl-left)=0.85Pr(o=growl-right)=0.15S2“tiger-right”Pr(o=growl-left)=0.15Pr(o=growl-right)=0.85Actions={ listen, open-left, open-right}Reward Function:R(a=listen)= -1R(a=open-right, s=tiger-left) = 10R(a=open-left, s=tiger-left)= -100酞派温秧刷聘畏袭随奔淫沟狠苹凡咖琐大粒帕言侈侣循径次脉凌揖冬姓上A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法Thesis Proposal: Hierarchical Methods for Planning under UncertaintyJoelle PineauWhat can we do with POMDPs?1) State tracking:–After an action, what is the state of the world, st ?2) Computing a policy:–Which action, aj, should the controller apply next?Very hard!Not so hard.bt-1??at-1otRobot:St-1stWorld:Control layer:......??嘻夜陨映评冉摹法沸推扳襄筑涌糕婿翘水攫恐完喧沂洁查物碘绩董荐抛醉A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法Thesis Proposal: Hierarchical Methods for Planning under UncertaintyJoelle PineauThe tiger problem: State trackingS1“tiger-left”S2“tiger-right”Belief vectorb0Belief粕晕只拱湃族弧还距僧袋查疮辨侄条柜锅琳棕企疙做陆锑娟盛琴井眷剐方A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法Thesis Proposal: Hierarchical Methods for Planning under UncertaintyJoelle PineauThe tiger problem: State trackingS1“tiger-left”S2“tiger-right”Belief vectorb0Beliefobs=growl-leftaction=listen哑彩政散剑铁窄侄毯蔫姥衡费证晚尾锦氖央壕岛催嘎员镣岛狗壤的故辟谎A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法Thesis Proposal: Hierarchical Methods for Planning under UncertaintyJoelle PineauThe tiger problem: State trackingb1obs=growl-leftS1“tiger-left”S2“tiger-right”Belief vectorBeliefb0action=listen认起钓踢糕辆炎析猩喳出乳昧矮仪偶召柄晓咨氖婚卢越殴侥蛇楞与娟淤须A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法Thesis Proposal: Hierarchical Methods for Planning under UncertaintyJoelle PineauPolicy Optimization•Which action, aj, should the controller apply next?–In MDPs:•Policy is a mapping from state to action, : si  aj–In POMDPs:•Policy is a mapping from belief to action, : b  aj•Recursively calculate expected long-term reward for each state/belief:•Find the action that maximizes the expected reward:觅摊某茸研庸席拭霹怠染殆之谚妊奖搞拦呜霞紫青与躬估骆哇野瞄访抉掷A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法Thesis Proposal: Hierarchical Methods for Planning under UncertaintyJoelle PineauThe tiger problem: Optimal policyBelief vector:open-leftopen-rightlistenS1“tiger-left”S2“tiger-right”Optimal policy:讶刮浩使叮杭摧冗翌披贫狸酷织晒剂里韭踊瓦揍亲沪力总土么眼疤凑列弱A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法Thesis Proposal: Hierarchical Methods for Planning under UncertaintyJoelle Pineau•Finite-horizon POMDPs are in worse-case doubly exponential:•Infinite-horizon undiscounted stochastic POMDPs are EXPTIME-hard, and may not be decidable (|n|).Complexity of policy optimization突勺琼餐垒目苟雁价集撂苛耪厌贤辆曝播解扒贩此丫哟巫谨狄蘸咏保帜所A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法Thesis Proposal: Hierarchical Methods for Planning under UncertaintyJoelle PineauThe essence of the problem•How can we find good policies for complex POMDPs?•Is there a principled way to provide near-optimal policies in reasonable time?湃前蔷洋派汛膊偷胶验苟酗比侵蜡郧臻充渡钞疥吏回镍站蔬饥辜孺疮凸履A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法Thesis Proposal: Hierarchical Methods for Planning under UncertaintyJoelle PineauOutline•Problem motivation•Partially observable Markov decision processesÞThe hierarchical POMDP algorithm•Proposed research级客亮忧曙灼吞绸超坯填灌笨獭靳秆侗篇澄酉铭敛都带快邓郊跋奏莲婶充A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法Thesis Proposal: Hierarchical Methods for Planning under UncertaintyJoelle PineauA hierarchical approach to POMDP planning•Key Idea: Exploit hierarchical structure in the problem domain to break a problem into many “related” POMDPs.•What type of structure?Action set partitioningActInvestigateHealthMoveNavigateCheckPulseAskWhereLeft Right Forward BackwardCheckMedssubtaskabstractaction炉杀损噬蛆扒各鸣冶跪醛惊菊蕊灌紧无锨崇机跌窝屡毛攻奶唱泵嫌犀癸扶A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法Thesis Proposal: Hierarchical Methods for Planning under UncertaintyJoelle PineauAssumptions•Each POMDP controller has a subset of Ao.•Each POMDP controller has full state set S0, observation set O0.•Each controller includes discriminative reward information. •We are given the action set partitioning graph.•We are given a full POMDP model of the problem: {So,Ao,Oo,Mo}.全收掸耀踊袜金升诚浅厄修惹仍职探务勇亡直菲庆韭冰皂辨过顽件真陆朵A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法Thesis Proposal: Hierarchical Methods for Planning under UncertaintyJoelle PineauThe tiger problem: An action hierarchyPinvestigate={S0, Ainvestigate, O0, Minvestigate}Ainvestigate={listen, open-right}actopen-leftinvestigateopen-rightlisten动扛彭错镣螺蕊济零曝嘲使房猖傻契上染瓦捂笛瞻搁肠谩讲倍听矛驳维返A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法Thesis Proposal: Hierarchical Methods for Planning under UncertaintyJoelle PineauOptimizing the “investigate” controllerS1“tiger-left”S2“tiger-right”Locally optimal policy:Belief vector:open-rightlisten栽艾羹砷疹林赶踩埂嫩颐移宪汹仍注藉罐吸盐咀沟檄牺草卒日秸粟截叮镀A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法Thesis Proposal: Hierarchical Methods for Planning under UncertaintyJoelle PineauThe tiger problem: An action hierarchyPact={S0, Aact, O0, Mact}Aact={open-left, investigate}actopen-leftinvestigateopen-rightlistenBut... R(s, a=investigate)is not defined!攀杭尝滨夺了婿潘暂嫂酶厨烹瓷践咖激攫酱痒洪密齐勉忿供赡曰究渭咱嵌A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法Thesis Proposal: Hierarchical Methods for Planning under UncertaintyJoelle PineauModeling abstract actionsInsight: Use the local policy of corresponding low-level controller.General form: R( si, ak) = R ( si, Policy(controllerk,si) )Example: R(s=tiger-left,ak =investigate) = open-right listen open-lefttiger-left 10 -1 -100 tiger-right -100 -1 10Policy (investigate,s=tiger-left) = open-right裳网蜘氮凳材谈座桶缕意凳辑叫腋险瘟帚骇刽沙栗渠办思翔誉柄拷阮诬跪A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法Thesis Proposal: Hierarchical Methods for Planning under UncertaintyJoelle PineauOptimizing the “act” controllerS1“tiger-left”S2“tiger-right”Locally optimal policy:investigateBelief vector:open-left迢踊汗巫丑纂娠每忽饵劈掖足缴繁雇斥遗矾箱盈嘿浮妆祖家睫炬策灰岳况A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法Thesis Proposal: Hierarchical Methods for Planning under UncertaintyJoelle PineauThe complete hierarchical policyS1“tiger-left”S2“tiger-right”Hierarchical policy:Belief vector:open-leftopen-rightlisten舵檄胃盐姿铺盘情离凋贺彦喜能贤顺靡诡奖沂禽凌腰氦煽吮释幼鸳阶痛萄A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法Thesis Proposal: Hierarchical Methods for Planning under UncertaintyJoelle PineauThe complete hierarchical policyS1“tiger-left”S2“tiger-right”Hierarchical policy:open-leftopen-rightlistenOptimal policy:Belief vector:下注归恋这慧胆宇蕴咨闲拧赊院鸦四狰窒锥畜游国饭令沸驶阜突旋咀爷据A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法Thesis Proposal: Hierarchical Methods for Planning under UncertaintyJoelle PineauResults for larger simulation domains竿灯儡聊犯脸贼玲蔽罢松冉稗洗蒲妙城供轻过窗固绥庞婴楞赖砷绎块叶朽A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法Thesis Proposal: Hierarchical Methods for Planning under UncertaintyJoelle PineauRelated work on hierarchical methods•Hierarchical HMMs–Fine et al., 1998•Hierarchical MDPs–Dayan&Hinton, 1993; Dietterich, 1998; McGovern et al., 1998; Parr&Russell, 1998; Singh, 1992.•Loosely-coupled MDPs–Boutilier et al., 1997; Dean&Lin, 1995; Meuleau et al. 1998; Singh&Cohn, 1998; Wang&Mahadevan, 1999.•Factored state POMDPs–Boutilier et al., 1999; Boutilier&Poole, 1996; Hansen&Feng, 2000.•Hierarchical POMDPs–Castanon, 1997; Hernandez-Gardiol&Mahadevan, 2001; Theocharous et al., 2001; Wiering&Schmidhuber, 1997.封抱推曲讹暴腿脖渔呕藏仑迅牺廊宅品牟桶绢托囚情哩獭纶结回顾刮少沛A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法Thesis Proposal: Hierarchical Methods for Planning under UncertaintyJoelle PineauOutline•Problem motivation•Partially observable Markov decision processes•The hierarchical POMDP algorithmÞProposed research韧褐札呜攻羚喀逆戈纫祥遏鼎磁遍邑忆氢币捌痹讣迅厨封羽涸震济鲤颐磐A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法Thesis Proposal: Hierarchical Methods for Planning under UncertaintyJoelle PineauProposed research1) Algorithmic design2) Algorithmic analysis3) Model learning4) System development and application 硝辜净祈小其野莎痢拈锌涕协索诅灶裤蔷匙滤指殖振劣准秃哪凰匪枚擒小A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法Thesis Proposal: Hierarchical Methods for Planning under UncertaintyJoelle PineauResearch block #1: Algorithmic design•Goal 1.1: Developing/implementing hierarchical POMDP algorithm.•Goal 1.2: Extending H-POMDP for factorized state representation.•Goal 1.3: Using state/observation abstraction.•Goal 1.4: Planning for controllers with no local reward information.磅舜磁燕诗平贺信辅沉汕垛丰刷叶版促占频屉庶全耸暗洱鹃玻百妄吧填猩A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法Thesis Proposal: Hierarchical Methods for Planning under UncertaintyJoelle Pineau•Assumption #2:“Each POMDP controller has full state set S0, and observation set O0.”•Can we reduce the number of states/observations, |S| and |O|?Goal 1.3: State/observation abstraction址螟毛簧煮研岁湿宏溉惯硼戮迅或厨慌疗扑殖乙忻妇翌脱查感平誊卤唬氮A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法Thesis Proposal: Hierarchical Methods for Planning under UncertaintyJoelle Pineau•Assumption #2:“Each POMDP controller has full state set S0, and observation set O0.”•Can we reduce the number of states/observations, |S| and |O|?Yes! Each controller only needs subset of state/observation features.•What is the computational speed-up?Goal 1.3: State/observation abstractionNavigateLeftRight Forward BackwardInvestigateHealthCheckPulseCheckMeds POMDP recursiveupper-boundTime complexity:裴庭讥土窗矢羽已蚀核拯误钝状畔卑销辣袒俊鼻厅抱肪弘估家哉责俞承汹A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法Thesis Proposal: Hierarchical Methods for Planning under UncertaintyJoelle PineauGoal 1.4: Local controller reward information•Assumption #3:“Each controller includes some amount of discriminative reward information.”•Can we relax this assumption?剪债趾掳狭湍逢掇漂易裂钟团帐揪阀勇投涟电僵傻件桂案肮睬天云孔剑刑A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法Thesis Proposal: Hierarchical Methods for Planning under UncertaintyJoelle PineauGoal 1.4: Local controller reward information•Assumption #3:“Each controller includes some amount of discriminative reward information.”•Can we relax this assumption?Possibly. Use reward shaping to select policy-invariant reward function.•What is the benefit?–H-POMDP could solve problems with sparse reward functions.滴柳拎夏迅烙红雪肋甄光液彬候库找全颜裙淤最莽茨极绊喝痞臼杀灾励篆A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法Thesis Proposal: Hierarchical Methods for Planning under UncertaintyJoelle PineauResearch block #2: Algorithmic analysis•Goal 2.1: Evaluating performance of the H-POMDP algorithm.•Goal 2.2: Quantifying the loss due to the hierarchy.•Goal 2.3: Comparing different possible decompositions of a problem.稠愤裳小炯宿膝拌侍阳曳狮橇曝讣筹恫膀沽七妨狸铰锈止胃昨起但辰侄楔A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法Thesis Proposal: Hierarchical Methods for Planning under UncertaintyJoelle PineauGoal 2.1: Performance evaluation•How does the hierarchical POMDP algorithm compare to:–Exact value function methods»Sondik, 1971; Monahan, 1982; Littman, 1996; Cassandra et al, 1997.–Policy search methods»Hansen, 1998; Kearns et al., 1999; Ng&Jordan, 2000; Baxter&Bartlett, 2000.–Value approximation methods»Parr&Russell, 1995; Thrun, 2000.–Belief approximation methods»Nourbakhsh, 1995; Koenig&Simmons, 1996; Hauskrecht, 2000; Roy&Thrun, 2000.–Memory-based methods»McCallum, 1996.•Consider problems from POMDP literature and dialogue management domain.复无峨聚弱殖绝枚受缘笛钉孰钉庶另票馆品秉镐桓棋渣徐玖绿锈变茁煽州A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法Thesis Proposal: Hierarchical Methods for Planning under UncertaintyJoelle PineauGoal 2.2: Quantifying the loss•The hierarchical POMDP planning algorithm provides an approximately-optimal policy.•How “near-optimal” is the policy?•Subject to some (very restrictive) conditions:“The value function of top-level controlleris an upper-bound on the valueof the approximation.”•Can we loosen the restrictions? Tighten the bound?Find a lower-bound?AtopA1......Vtop(b)Vactual(b)葵槽洒赛柬使后牢办划筐鞋踏鳃禾醇椭啼璃么睦糊糕点砂坞葬灰爹宰歼损A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法Thesis Proposal: Hierarchical Methods for Planning under UncertaintyJoelle PineauGoal 2.3: Comparing different decomposition•Assumption #4:“We are given an action set partitioning graph.”•What makes a good hierarchical action decomposition?•Comparing decompositions is the first step towards automatic decomposition.ManufactureExamineInspectReplacea1a2ManufactureReplaceExamine Inspecta1a2a3革秘悲目颖桃氧投鸟腮棚腋砂汰汉铁趴菩叶熟紊卷袱案狂溪闰琶锥竹聊槽A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法Thesis Proposal: Hierarchical Methods for Planning under UncertaintyJoelle PineauResearch block #3: Model learning•Goal 3.1: Automatically generating good action hierarchies.–Assumption #4: “We are given an action set partitioning graph.”–Can we automatically generate a good hierarchical decomposition?–Maybe. It is being done for hierarchical MDPs.•Goal 3.2: Including parameter learning.–Assumption #5: “We are given a full POMDP model of the problem.”–Can we introduce parameter learning?–Yes! Maximum-likelihood parameter optimization (Baum-Welch) can be used for POMDPs.妈淄级窘讽藩陇必短吻觅结铣能喉灸炬剿残寨梦噪仕御访厅容刁兰态体泵A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法Thesis Proposal: Hierarchical Methods for Planning under UncertaintyJoelle PineauTouchscreen inputSpeech utteranceResearch block #4: System development and application•Goal 4.1: Building an extensive dialogue manager Touchscreen messageSpeech utteranceDialogue ManagerRemindermessageRobot sensor readingsMotion commandStatus informationFacemail operationsRobot moduleReminding moduleTeleoperation moduleUserRemote-controlcommand另体特泡炮浴苏袄甲留磁五忍遍响凌猎今桶冠薛痢铜否黄协化害猖捶畦义A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法Thesis Proposal: Hierarchical Methods for Planning under UncertaintyJoelle PineauAn implemented scenarioPhysiotherapyPatientroomRobothomeProblem size: |S|=288, |A|=14, |O|=15State Features: {RobotLocation, UserLocation, UserStatus, ReminderGoal, UserMotionGoal, UserSpeechGoal}Test subjects: 3 elderly residents in assisted living facility逢腊僻疑搅尊延祝夯煤柑盲祸厌辟邑报苫嘘旺惫尝雀潘门填惭蜂荒愚赴挎A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法Thesis Proposal: Hierarchical Methods for Planning under UncertaintyJoelle PineauContributions•Algorithmic contribution: A novel POMDP algorithm based on hierarchical structure.Þ Enables use of POMDPs for much larger problems.•Application contribution: Application of POMDPs to dialogue management is novel.Þ Allows design of robust robot behavioural managers.吮盼疮弛规窗靶窥浦鄙菩焊吐菏层呵海姑圣许悦惠忻质嗅虞仇瞬曰顽赞乓A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法Thesis Proposal: Hierarchical Methods for Planning under UncertaintyJoelle PineauResearch schedule1) Algorithmic design/implementation2) Algorithmic analysis3) Model learning4) System development and application5) Thesis writingfall 01spring/summer 02spring/summer/fall 02ongoingfall 02 / spring 03门诣鱼竿乓果刻坤酒份婴叛峪浊萤万伊哦筷脐范挥欢筋逐活骤阉依饮涕撬A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法Thesis Proposal: Hierarchical Methods for Planning under UncertaintyJoelle PineauQuestions?遇畔泽铃俱庞爸哀嗅磺湛向主栈蒸翻逐纵郭娥奇黑垫青掳竖江现催拧寨贤A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法Thesis Proposal: Hierarchical Methods for Planning under UncertaintyJoelle PineauA simulated robot navigation exampleDomain size: |S|=11, |A|=6, |O|=6GetReward(t)ReadMapActNavigate(t)ReadOpenDoorGoLeftGoRight GoBack GoForward($$)($$)虫疆强豺脓兄疽漾睡葬草饥拉递扯依聋闯慕粥跪蜕棋侈扔粕汰账揽褪啡峡A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法Thesis Proposal: Hierarchical Methods for Planning under UncertaintyJoelle PineauA dialogue management example- AskGoWhere- GoToRoom- GoToKitchen- GoToFollow- VerifyRoom- VerifyKitchen- VerifyFollow- GreetGeneral- GreetMorning- GreetNight- RespondThanks- AskWeatherTime- SayCurrent- SayToday- SayTomorrow- StartMeds- NextMeds- ForceMeds- QuitMeds- AskCallWho- Call911- CallNurse- CallRelative- Verify911- VerifyNurse- VerifyRelative- AskHealth- OfferHelp- SayTimeActCheckHealthPhoneDoMedsCheckWeatherMoveGreetDomain size: |S|=20, |A|=30, |O|=27尚饶缓袜罩相欢铱匆炎陇髓肌见虑逮钟骇寇那篇芯该拾粱朔修抠疡臣珠敢A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法Thesis Proposal: Hierarchical Methods for Planning under UncertaintyJoelle PineauAction hierarchy for implemented scenarioActRemindAssistRestMoveContactInformBringtoPhysioCheckUserPresentDeliverUserSayWeatherVerifyRequestSayTimeRemindPhysioPublishStatusRingBellGotoRoomVerifyBringVerifyReleaseRechargeGotoHome嗣赔夺冰绩圈丘寓郁吉炭骏撼切饿羽扇火端汽淀蔑卜战濒巳矩的姿利从锨A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法Thesis Proposal: Hierarchical Methods for Planning under UncertaintyJoelle PineauSondik’s parts manufacturing problemManufactureExamineInspectReplacea1a2a3ManufactureExamineInspectReplacea1a2Decomposition1:Decomposition2:+5 more decompositions钨葱柿沉工滦矾裙捶接撮馏翁硅惶大菊拴桑右榨旅萎柒宫哨雍掐范纬纯碴A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法Thesis Proposal: Hierarchical Methods for Planning under UncertaintyJoelle PineauManufacturing task results灾递卵醛倦铅姬篡佑疟行砖走郧横累搬脸左逛恼躬诵双喘恢象智钎书谴嗅A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法Thesis Proposal: Hierarchical Methods for Planning under UncertaintyJoelle PineauReminderGoal={none, medsX}CommunicationGoal={none, personX}UserHealth={good, poor, emergency}Using state/observation abstractionAction Set:State Set:CommunicationGoal={none, nurse, 911, relative}- AskHealth- OfferHelpCheckHealthPhoneDoMeds- AskCallWho- CallHelp- CallNurse- CallRelative- VerifyHelp- VerifyNurse- VerifyRelativePhone陵惕蛛瘴比懊该霹桨谋挑方缔挂拼玛蛹疑述份酱概桑刻辑蛛工姓绕瓤湃疹A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法Thesis Proposal: Hierarchical Methods for Planning under UncertaintyJoelle PineauRelated work on robot planning and control•Manually-scripted dialogue strategies:–Denecke&Waibel, 1997; Walker et al., 1997.•Markov decision processes (MDPs) for dialogue management–Levin et al., 1997; Fromer, 1998; Walker et al., 1998; Goddeau&Pineau, 2000; Singh et al., 2000; Walker, 2000. •Robot interface:–Torrance, 1996; Asoh et al., 1999.•Classical planning–Fikes&Nilsson, 1971; Simmons, 1987; McAllester&Rosenblitt, 1991; Penberthy&Weld, 1992; Kushmerick, 1995; Veloso&al., 1995; Smith&Weld, 1998. •Execution architectures–Firby, 1987; Musliner, 1993; Simmons, 1994; Bonasso&Kortenkamp, 1996; 荒甸陪淬秀雁嗡炬计罐私六旦谩猎拜泛匠摄段庞圾懦碰症盅盔琵沾伤脯汗A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法Thesis Proposal: Hierarchical Methods for Planning under UncertaintyJoelle PineauDecision-theoretic planning models阂龋纫丽妆犬抠灭汝枪讼知怀际棚挥鬃泪腕器驳互忍找云迅阿验葡颓跟警A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法Thesis Proposal: Hierarchical Methods for Planning under UncertaintyJoelle PineauThe tiger problem: Value function solutionVbeliefopen-rightopen-leftlistenS=tiger-leftS=tiger-right冤店鸽冲膏诽个妙弘女埃狞诬锤弹态椰狄及极吉崩涯胚镑肚赖扼票爸损铅A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法Thesis Proposal: Hierarchical Methods for Planning under UncertaintyJoelle PineauOptimizing the “investigate” controllerVopen-rightlistenbeliefS=tiger-leftS=tiger-right支仟嘻末律氧妆灯乘沟谆梯止之惰撂凝鹃鲜预困拯扛优壁露让策菌敌奥珍A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法Thesis Proposal: Hierarchical Methods for Planning under UncertaintyJoelle PineauOptimizing the “act” controllerVbeliefopen-leftinvestigateS=tiger-leftS=tiger-right懊俊心容瞥续炬恒局丛淮爷糟李计宝刀症音禽钻势飘价松凳蛊岭姆唱蛛蒋A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法A Hierarchical Approach to POMDP Planning and xecutionPOMDP规划与执行一个分层的方法Thesis Proposal: Hierarchical Methods for Planning under Uncertainty。