人工智能原理-北京大学-8--PartIVPlanningChapter8Classicand-(8

SchoolofElectronicandComputerEngineeringPekingUniversityWangWenminArtificialIntelligenceReal-WorldPlanningArtificialIntelligence2Contents8.4.1.HierarchicalPlanning8.4.2.Multi-agentPlanningArtificialIntelligence::Planning::ClassicandReal-worldPlanning3Classicalplanning经典规划feature:afixedsetofactions.特征：一组固定的动作problem:astate-of-the-artalgorithmscangeneratesolutionscontainingthousandsofactions.问题：最新式的算法可以生成包含数千个动作的解。Hierarchicalplanning分层规划feature:decomposehigh-level,abstracttasksintolow-level,concretetasks.特征：将高层、抽象的任务分解为低层、具象的任务benefit:ateachlevelofthehierarchy,acomputationaltaskisreducedtoasmallnumberofactivities,sothecomputationalcostissmall.益处：在层次结构的每一级，计算任务被缩减为少量活动，因此计算成本也减少。Classicalplanningvs.Hierarchicalplanning经典规划和分层规划8.4.1.HierarchicalPlanningArtificialIntelligence::Planning::ClassicandReal-worldPlanning4Primitiveaction基本动作Meanstheactionsinclassicalplanning,withstandardprecondition-effectschemas.指的是经典规划中的动作，具有经典的前提-效用模式。Hasnorefinements.没有提炼过程。High-levelaction(HLA)高级动作(HLA)Keyadditionalconceptforhierarchicaltasknetworks(HTN)planning.层次任务网络(HTN)规划中的重要概念。EachHLAhasoneormorepossiblerefinements,eachofwhichmaybeanHLA,oraprimitiveaction.每个HLA有一个或多个可能的提炼，每个动作可以是一个HLA、或一个基本动作。PrimitiveactionandHigh-levelaction基本动作和高层动作8.4.1.HierarchicalPlanningArtificialIntelligence::Planning::ClassicandReal-worldPlanning5Theactionis“GotoSanFranciscoairport”,representedformallyas:该动作是“去旧金山机场”，形式化表示为：Example:Refinement提炼8.4.1.HierarchicalPlanningRefinement(Go(Home,SFO),STEPS:[Drive(Home,SFOLongTermParking),Shuttle(SFOLongTermParking,SFO)])Refinement(Go(Home,SFO),STEPS:[Taxi(Home,SFO)])Mayhavetwopossiblerefinements:1)driveacartogettotheairport,or2)takeataxitogettotheairport.可以有两种可能的提炼：1)开车去机场，或2)打车去机场。Go(Home,SFO).ArtificialIntelligence::Planning::ClassicandReal-worldPlanning6Sofar,wehaveassumedthatonlyoneagentisdoingtheplanning.迄今为止，我们假设仅有一个智能体在做计划。Whentherearemultipleagentsintheenvironment,eachagentfacesamulti-agentplanningprobleminwhichittriestoachieveitsowngoalswiththehelporhindranceofothers.当环境中有多个智能体时，每个面临多智能体规划问题，试图通过其他智能体的帮助或阻碍达到自己的目标。Thisplanninginvolvescoordinatingresourcesandactivitiesofmultipleagents.这种多智能体规划涉及多个智能体之间协调资源和活动。Thetopicalsoinvolveshowagentscandothisinrealtimewhileexecutingplans(distributedcontinualplanning).该主题也涉及到多个智能体在执行计划（分布式连续规划）时如何能够实时动作。Whatismulti-agentplanning什么是多智能体规划8.4.2.Multi-agentPlanningArtificialIntelligence::Planning::ClassicandReal-worldPlanning7Single-agentproblem单智能体问题Multi-effector多效用器anagentwithmultipleeffectorsthatcanoperateconcurrently,e.g.,ahumanwhocantypeandspeakatthesametime.一个智能体有多个可以并发运行的效用器。例如，一个人可以同时一边打字一边说话。Multi-body多躯体effectorsarephysicallydecoupledintodetachedunits,butactasasinglebody,e.g.,afleetofdeliveryrobotsinafactory.效应器物理分解为独立的单元，但是作为一个躯体动作。例如，工厂里的传送机器人机群。Multi-agentproblem多智能体问题multipleagentscoordinatetheresourcesandactions.多智能体之间协调资源与动作。Single-agentvs.Multi-agentproblem单智能体与多智能体问题8.4.2.Multi-agentPlanningArtificialIntelligence::Planning::ClassicandReal-worldPlanning8Autonomy:自主性theagentsareatleastpartiallyindependent,self-aware,autonomous.这些智能体至少是部分独立、自我意识的、自主的。Localviews:局部视野noagenthasafullglobalviewofthesystem,orthesystemistoocomplexforanagenttomakepracticaluseofsuchknowledge.没有智能体对系统具有全局视野，或者系统太复杂，一个智能体无法实际使用这些知识。Decentralization:分散化nodesignatedcontrollingagent,foreachagentmayneedtoincludecommunicativeactionswithotherbodies.不指定控制智能体，每个智能体可能需要包含与其它躯体进行沟通的动作。e.g.,multiplereconnaissancerobots.例如：多机器人侦查。Characteristicsofmulti-agent多智能体的特性8.4.2.Multi-agentPlanningArtificialIntelligence::Planning::ClassicandReal-worldPlanning9Theclearestcaseofamulti-agentproblemiswhentheagentshavedifferentgoals.多智能体问题最明显的案例是这些智能体具有不同目标时。Theissuesinmulti-agentplanningcanbedividedroughlyintotwosets:多智能体规划中的问题可以大致分为两类：1)involvingissuesofrepresentingandplanningformultiplesimultaneousactions.多同步动作的表示与规划所涉及的问题。theseoccurinallsettingsfrommulti-effectortomulti-agentplanning.这些问题从多效应器到多智能体规划的所有状况下都会发生。2)involvingissuesofcooperation,coordination,andcompetitionarisingintruemulti-agentsettings.真正的多智能体环境中所发生的合作、协调和竞争的问题。IssuesinMulti-agentPlanning多机器人规划中的问题8.4.2.Multi-agentPlanningArtificialIntelligence::Planning::ClassicandReal-worldPlanning10Actor行动者agenerictermtocovereffectors,bodies,andagents.一个涵盖效用器、躯体和智能体的通用术语。Multi-actor多行动者agenerictermtotreatmulti-effector,multi-body,andmulti-agent.一个涉猎多效用器、多躯体、以及多智能体的通用术语。Multiplesimultaneousactions多同步动作formulti-actor,toworkouthowtodefine:对于多行动者，要解决如何定义：transitionmodels,correctplans,andefficientplanningalgorithms.迁移模型、正确的规划、以及有效的规划算法。1)Planningwithmultiplesimultaneousactions具有多同步动作的规划8.4.2.Multi-agentPlanningArtificialIntelligence::Planning::ClassicandReal-worldPlanning11Example:Doublestennisproblem双打网球问题8.4.2.Multi-agentPlanningTwoactorsAandBareplayingtogether.两个行动者A和B一起打球。Theycanbeinoneoffourlocations:他们可以位于四个位置中的一个：LeftBaseline,RightBaseline,LeftNet,andRightNet.Theballcanbereturnedonlyifaplayerisintherightplace.只有当球手位于正确的地方时才可以回球。Eachactionmustincludetheactorasanargument.每个动作必须包含该行动者作为参数。Actors(A,B)Init(A