Floor 
`Initial  stack s 
`
`Floo r 
`Goa l stac k 
`
`Fig .  13. 1  A   simpl e  bloc k  stackin g  task . 
`
`INITIAL STATE : ON(C,A) , O N (A , Floor) , ON(B , Floor) , 
`CLEAR (C) , CLEA R (B) , CLEA R (Floor ) 
`The goa l stat e i s on e i n whic h th e followin g tw o assertion s ar e true . 
`GOAL ASSERTIONS :  ON(A,B) , ON(B,C ) 
`With  onl y thes e rules , th e formalizatio n  o f th e bloc k  stackin g worl d  yield s a  ver y 
`"loose"  semantics .  (Th e  tas k  easil y  translate s  t o  sortin g  integer s  wit h  som e  re ­
`strictions o n operations , o r t o th e "sedation " tas k o f arrangin g block s horizontall y 
`in orde r o f size , o r a  hos t o f others. ) 
`Actions transfor m  th e se t o f assertion s describin g th e world . Fo r problem s o f 
`realistic scale , th e representatio n  o f th e tre e o f worl d state s i s a  practica l  problem . 
`The issu e i s on e o f maintainin g severa l coexistin g  "hypothetica l  worlds " an d rea ­
`soning abou t them . Thi s i s anothe r versio n o f th e fram e  proble m discusse d i n sec . 
`12.1.6. On e wa y t o solv e thi s proble m i s t o giv e eac h assertio n a n extr a  argument , 
`naming th e hypothetica l worl d  (usuall y calle d a  situatio n  [Nilsso n  1980 ; McCarth y 
`and Haye s 1969] ) i n whic h th e assertio n holds . The n action s ma p situation s t o situ ­
`ations a s wel l a s introducin g an d changin g assertions . 
`An equivalen t wa y t o think  abou t  (an d implement )  multiple , dependent , hy ­
`pothetical world s i s wit h a  tree­structure d  context­oriented  data  base.  Thi s ide a i s a 
`general on e tha t i s usefu l  i n man y artificia l  intelligenc e applications , no t jus t sym ­
`bolic  planning .  Suc h  dat a  base s  ar e  include d  i n  man y  artificia l  intelligenc e 
`languages an d  appea r  i n othe r  mor e  traditiona l  environment s  a s well . A  context ­
`oriented  dat a bas e acts  lik e a  tre e  o f dat a  bases ; a t an y nod e o f th e tre e i s a  se t o f 
`assertions tha t make s u p th e dat a base . A  ne w dat a bas e (context )  ma y b e spawne d 
`from  an y contex t  (dat a base )  i n th e tree . Al l assertion s tha t ar e tru e i n th e spawn ­
`ing  (ancestor )  contex t  ar e  initiall y  tru e  i n  th e  spawne d  (descendant )  context . 
`However,  ne w assertion s adde d  i n an y contex t  o r delete d  fro m  i t d o no t affec t  it s 
`ancestor. Thu s  b y goin g  bac k t o  th e ancestor ,  al l dat a  bas e change s performe d  i n 
`the descenden t contex t disappear . 
`Implementing  suc h  a  dat a bas e i s a n interestin g exercise .  Copyin g al l asser ­
`tions  t o eac h ne w contex t  i s possible , bu t  ver y wastefu l  i f onl y a  fe w change s ar e 
`made i n eac h context . Th e followin g  mechanis m  i s muc h  mor e efficient .  Th e roo t 
`or initia l  contex t  ha s som e  se t  o f assertion s  i n it , an d  eac h descendan t  contex t  i s 
`merely a n add  list  o f assertion s t o ad d t o th e dat a bas e an d a  delete  list  o f assertion s 
`to delete . The n t o se e i f a n assertio n i s tru e i n a  context , d o th e following . 
`
`1.  I f th e contex t i s th e roo t context , loo k u p "a s usual. " 
`2.  Otherwise ,  i f th e assertio n  i s o n th e add  list  o f thi s context ,  retur n  true.   I f th e 
`assertion i s o n th e delete  list  o f thi s context , retur n false. 
`
`4 4 0 
`
`Ch.  13   Goal   Achievement 
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 452
`
`

`

`3.  Otherwise , recursivel y appl y thi s procedur e t o th e ancesto r o f thi s context . 
`In  a  genera l  programmin g  environment ,  context s  hav e  names , an d  ther e  i s 
`the facilit y  o f executin g  procedure s  "in "  particula r  contexts ,  movin g aroun d  th e 
`context  tree , an d  s o forth .  However ,  i n wha t follows ,  onl y  th e  abilit y  t o  loo k  u p 
`assertions i n context s i s relevant . 
`
`13.1.2  Representin g  Action s 
`
`Represent a n actio n a s a  triple . 
`ACTION :: =  [PATTERN , PRECONDITIONS , POSTCONDITIONS] . 
`Here th e patter n give s th e nam e o f th e actio n an d name s fo r th e object s wit h whic h 
`it deals—it s  "forma l  parameters. "  Preconditions  an d postcondition s  ma y us e  th e 
`formal  variable s o f  th e pattern .  I n  a  sense ,  th e  precondition s  an d  postcondition s 
`are  th e  "body "  o f  th e  action ,  wit h  subroutine­lik e  "variabl e  bindings "  takin g 
`place whe n th e actio n  i s t o b e performed .  Th e precondition s giv e th e worl d state s 
`in whic h th e actio n  ma y b e applied . Her e th e precondition s ar e assume d simpl y t o 
`be a  lis t  o f assertion s  al l o f whic h  mus t  b e true . Th e  postcondition s  describ e  th e 
`world  stat e  tha t  result s  fro m  performin g  th e  action .  Th e  context­oriente d  dat a 
`base o f hypothetica l world s ca n b e use d t o implemen t th e postconditions . 
`
`POSTCONDITIONS :: =  [ADD­LIST , DELETE­LIST] . 
`An actio n i s the n performe d  a s follows . 
`
`2. 
`
`1.  Bin d th e patter n variable s t o entitie s i n th e world , thu s bindin g th e associate d 
`variables i n th e precondition s an d postconditions . 
`I f th e precondition s ar e me t  (th e boun d assertion s exis t  i n th e dat a  base) , d o 
`the nex t step , els e exi t reportin g failure . 
`3.  Delet e  th e assertion s  i n  th e delet e  list ,  ad d thos e  i n  th e ad d list , an d exi t re ­
`porting success . 
`Here i s th e Move  actio n fo r ou r block­stackin g example . 
`
`PATTERN 
`
`Move Object  Xfrom   YtoZ 
`PRECONDITIONS   DELETE­LIST  
`
`ADD­LIST 
`
`Move(X,Y,Z)  CLEA R (X ) 
`CLEAR (Z ) 
`ON(X,Y) 
`
`ON(X,Y ) 
`CLEAR(Z ) 
`
`ON(X,Z ) 
`CLEA R (Y ) 
`
`Here X ,  Y,  an d Z  ar e al l variable s boun d t o worl d entities .  I n th e initia l stat e 
`of Fig . 13.1 , Mov e (C,A,  Floor )  bind s Zt o  C ,  Yto   A,   Zt o  Floor , an d th e precondi ­
`tions ar e satisfied ; th e actio n ma y proceed . 
`However, notic e tw o things . 
`
`Sec. 13.1   Symbolic   Planning  
`
`44 1 
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 453
`
`

`

`1.  Th e  actio n  give n  abov e  delete s  th e  CLEA R (Floor )  assertio n  tha t  alway s 
`should  b e  true .  On e  mus t  fix   thi s  somehow ;  puttin g  CLEA R (Floor )  i n  th e 
`add­lis t doe s th e job , bu t i s a  littl e inelegant . 
`2.  Wha t  abou t  a n  actio n  lik e  Move(C,^(,C) ?  I t  meet s  th e  preconditions ,  bu t 
`causes troubl e whe n th e ad d an d delet e list s ar e applied . On e fix  her e i s t o kee p 
`in th e dat a bas e  ("worl d  model" )  a  se t o f assertion s suc h a s Differen t  (A,B), 
`Different (A,  Floor) ,  .  . .
` ,  an d t o ad d assertion s suc h a s Differen t  {X,Z)   t o th e 
`preconditions o f Move . 
`Such housekeepin g  chore s  an d detail s o f axiomatizatio n  ar e inheren t  i n ap ­
`plying  basicall y  syntactic , forma l  solutio n  method s  t o  proble m  solving .  Fo r  now , 
`let u s assum e  tha t CLEA R (Floor )  i s neve r  deleted ,  an d tha t Move(A' , Y,Z)  i s ap ­
`plied onl y i f Z  i s differen t  fro m Xan d  Y. 
`
`13.1.3  Stackin g  Block s 
`
`In th e block­stackin g example , th e goa l i s tw o simultaneou s assertions ,  ON(A,B) 
`and ON(i?,C) . On e solutio n  metho d  proceed s b y repeatedl y pickin g a  goa l t o wor k 
`on, finding  a n operato r tha t move s close r t o th e goal , an d applyin g it . I n thi s cas e o f 
`only  on e  actio n  th e  questio n  i s  ho w  t o  appl y  it—wha t  t o  mov e  where .  Thi s  i s 
`answered b y lookin g a t th e postcondition s o f th e actio n i n th e ligh t o f th e goal . Th e 
`reasoning migh t g o lik e this : ON(Z?,C ) ca n b e mad e tru e i f X is  B  an d Zi s C.  Tha t i s 
`possible i n thi s stat e i f  Yis  A;  al l precondition s ar e satisfied ,  an d th e goa l O N (i?,C ) 
`can b e achieve d wit h on e action . 
`Part o f th e worl d stat e  (o r context )  tre e th e planne r  mus t searc h i s show n i n 
`Fig. 13.2 , wher e state s ar e show n diagrammaticall y instea d o f throug h set s o f asser ­
`tions. Notic e th e followin g thing s i n Fig . 13.2 . 
`
`1.  Tryin g t o achiev e O N (B,  C)  first  i s a  mistak e  (Branc h 1) . 
`2.  Tryin g  t o  achiev e  ON(A,B)   first   i s  als o  a   mistak e  fo r  les s  obviou s  reason s 
`(Branch 2) . 
`3.  Branche s  1  an d  2  sho w  "subgoa l  interaction. "  Th e goal s a s state d ar e no t  in ­
`dependent.  Branc h  3  mus t  b e generate d  somehow , eithe r  throug h  backtrack ­
`ing o r som e intelligen t wa y o f copin g wit h interaction . I t wil l neve r b e foun d b y 
`the  single­minde d  approac h  o f  (1 )  an d  (2) .  However ,  i f ON(C,Floor )  wer e 
`one o f th e goa l assertions , Branc h 3  coul d b e found . 
`
`Clearly, representin g worl d an d action s i s no t th e whol e stor y i n planning . In ­
`telligent searc h o f th e contex t i s als o necessary . Thi s searc h involve s subgoa l selec ­
`tion,  actio n  selection ,  an d  actio n  argumen t  selection .  Ba d  choice s anywher e  ca n 
`mean  inefficien t  o r  loopin g  actio n  sequences ,  o r  th e  generatio n  o f  impossibl e 
`subgoals. "Intelligent "  searc h  implie s a  meta­leve l  capability : th e abilit y o f a  pro ­
`gram t o reaso n abou t it s ow n plans . "Pla n critics " ar e ofte n  a  par t o f sophisticate d 
`planners; on e o f thei r mai n job s i s t o isolat e an d rectif y  unwante d  subgoa l interac ­
`tion  [Sussma n 1975] . 
`
`442 
`
`Ch.  13   Goal   Achievement 
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 454
`
`

`

`c
`A 
`
`B 
`
`(jWove KB,  C,  f T ) 
`
`c
`
`A 
`
`B 
`
`Branch 1 
`
`E  0   0 
`
`Bran  : h 2 
`
`A 
`A 
`A 
`
`B 
`B 
`B 
`
`C 
`C 
`C 
`
`Branch 3 
`
`Fig.  13. 2  A  stat e tre e generate d  i n  plannin g  ho w  l o slac k  thre e  blocks . 
`
`Intelligent choic e o f action s i s th e cru x o f planning , an d i s a  majo r researc h is ­
`sue. Severa l avenue s  hav e bee n  an d ar e bein g tried . Perhap s subgoal s ma y b e or ­
`dered b y difficult y  an d achieve d  i n tha t order . Perhap s plannin g shoul d procee d a t 
`various level s o f detai l  (lik e multiresolutio n imag e understanding) , wher e th e stra ­
`tegic skeleto n  o f a  pla n  i s derive d  withou t  details ,  the n  th e detail s ar e filled  i n b y 
`applying th e planne r i n mor e detai l t o th e subgoal s i n th e low­resolutio n plan . 
`
`Sec.  73. 7  Symbolic   Planning 
`
`443 
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 455
`
`

`

`13.1.4  Th e Fram e Proble m 
`
`All  plannin g  i s  plague d  b y  aspect s  o f  th e frame   problem  (introduce d  i n  Sectio n 
`12.1.6). 
`
`1. 
`
`I t i s impractica l  (an d boring )  t o writ e dow n i n a n actio n al l th e thing s tha t sta y 
`the sam e whe n a n actio n i s applied . 
`2.  Similarly , i t i s impractica l t o reasser t i n th e dat a bas e al l th e thing s tha t remai n 
`true whe n a n actio n i s implied . 
`3.  Ofte n  a n  actio n  ha s  effect s  tha t  canno t  b e  represente d  wit h  simpl e  ad d  an d 
`delete lists . 
`
`The  ad d  an d  delet e  lis t  mechanis m  an d  th e  context­oriente d  dat a  bas e 
`mechanism  addresse d  th e first  tw o problems .  Th e  las t  proble m  i s mor e  trouble ­
`some. 
`Add an d delet e list s ar e simpl e ideas , wherea s th e worl d i s a  comple x place . I n 
`many interestin g cases , th e ad d an d delet e list s depen d o n th e curren t stat e o f th e 
`world whe n th e actio n i s applied . Thin k o f action s TURNBYU )  an d MOVEBY(Z ) 
`in a  worl d wher e orientatio n  an d locatio n ar e important . Th e orientatio n  an d loca ­
`tion afte r  a n actio n depen d no t jus t o n th e actio n bu t o n th e stat e o f th e worl d jus t 
`before th e action . 
`Again, th e actio n ma y hav e ver y comple x effect s  i f ther e ar e comple x depen ­
`dencies  betwee n  worl d  objects .  Conside r  th e proble m  o f th e  "monke y  an d  bana ­
`nas," wher e th e monke y plan s t o pus h th e bo x unde r  th e banana s an d clim b o n i t 
`to reac h the m  (Fig . 13.3) .  Implementatio n  o f realisticall y powerfu l  ad d an d delet e 
`lists ma y i n fac t requir e arbitrar y amount s o f deductio n an d computation . 
`
`/ A
`
`V 
`
`V V 
`
`K
`
`4 \>
`
`/
`
`\ 
`
`/
`
`/
`
`444 
`
`Fig.  13. 3  Action s  ma y  hav e comple x 
`effects. 
`
`Ch.  7 3  Coal   Achievement 
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 456
`
`

`

`This  quic k  preci s  o f  symboli c  plannin g  doe s  no t  addres s  man y  "classical " 
`topics, suc h a s learnin g o r rememberin g usefu l plans .  Als o no t discusse d are : plan ­
`ning  a t  varyin g  level s  o f  abstraction ,  plan s  wit h  uncertai n  information ,  o r  plan s 
`with costs . Th e intereste d reade r shoul d consul t th e Reference s  fo r  mor e  informa ­
`tion.  Th e  nex t  sectio n  addresse s  plan s  wit h  cost s  sinc e  the y  ar e  particularl y 
`relevant t o vision ; som e o f th e othe r issue s appea r i n th e Exercises . 
`
`13.2  PLANNIN G WIT H  COST S 
`
`Decision makin g unde r uncertaint y  i s a n importan t  topi c i n it s ow n right ,  bein g o f 
`interest  t o policymaker s an d manager s  [Raiff a  1968] . Analyti c technique s tha t ca n 
`derive th e strateg y  wit h  th e  "optima l  expecte d  outcome "  o r "maxima l  expecte d 
`utility" ca n b e base d o n Bayesia n model s o f probability . 
`In  [Feldma n an d Sproul l  1977 ] thes e technique s ar e explore d  i n th e contex t 
`of actio n  plannin g  fo r  real­worl d  action s an d  vision .  A s  a n  exampl e  o f  th e  tech ­
`niques, the y ar e use d t o mode l a n extende d versio n o f th e "monke y an d bananas " 
`problem o f th e las t section , wit h multipl e boxe s bu t withou t th e maddenin g pulle y 
`arrangement. I n th e extende d problem , ther e ar e boxe s o f differen t  weight s whic h 
`may o r ma y no t suppor t th e monkey , an d h e ca n appl y test s  (e.g. , vision )  a t som e 
`cost  t o  determin e  whethe r  the y  ar e  usable .  Pushin g  weighte d  boxe s  cost s  som e 
`effort,  an d  th e  gratificatio n  o f  eatin g  th e  banana s  i s  "worth "  onl y  som e  finite 
`amount  o f effort .  Thi s extende d  se t o f consideration s  i s mor e  lik e everyda y deci ­
`sion  makin g  i n  th e  numbe r  o f factor s  tha t  nee d  balancing ,  i n th e  uncertaint y  in ­
`herent  i n  th e universe , an d  i n  th e richnes s o f applicabl e  tests . I n fact ,  on e migh t 
`make th e clai m tha t huma n  being s alway s "maximiz e  thei r expecte d  utility, " an d 
`if on e  kne w a  person' s  utilit y  functions ,  hi s behavio r  woul d  becom e  predictable . 
`The  mor e  intuitiv e  clai m  tha t  human s  being s  pla n  onl y  a s fa r  a s  "sufficien t  ex ­
`pected utility " ca n b e cas t a s a  maximizatio n operatio n wit h nonzer o "cos t o f plan ­
`ning." 
`The sequentia l decision­makin g mode l o f plannin g wit h th e goa l o f maximiz ­
`ing  th e goodnes s  o f  th e expecte d  outcom e  wa s use d  i n  a  trave l  planne r  [Sproul l 
`1977]. Knowledg e  o f schedule s  an d cost s o f variou s mode s o f transportatio n  an d 
`the attendan t risk s coul d b e combine d wit h persona l prejudice s an d preference s  t o 
`produce a n itinerar y wit h th e maximu m  expecte d  utility .  I f unexpecte d  situation s 
`(canceled flights , say ) aros e en  route,  replannin g coul d b e initiated ; thi s incremen ­
`tal pla n ramificatio n  i s a  natura l extensio n o f sequentia l decisio n making . 
`This sectio n i s concerne d  wit h measurin g th e expecte d performanc e  o f plan s 
`using a  singl e number .  Althoug h  on e migh t expec t on e numbe r  t o b e inadequate , 
`the centra l  theore m  o f decisio n  theor y  [DeGroo t  1970 ] show s essentiall y tha t on e 
`number  i s enough .  Usin g  a  numerica l  measur e  o f goodnes s  allow s  comparison s 
`between normall y  incomparabl e  concept s t o b e mad e easily . Quit e frequentl y  nu ­
`merical  score s ar e directl y  relevan t  t o  th e issue s a t stak e i n planning ,  s o the y ar e 
`not obnoxiousl y reductionistic . Decisio n theor y ca n als o hel p i n th e proces s o f ap ­
`plying a  plan—th e basi c pla n ma y b e simple , bu t it s applicatio n t o th e worl d ma y b e 
`complex, i n term s o f whe n t o declar e a  resul t establishe d o r a n actio n  unsuccessful . 
`The decision­theoreti c approac h ha s bee n use d i n severa l artificia l  intelligenc e an d 
`
`Sec.  13.2   Planning   with  Costs 
`
`445 
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 457
`
`

`

`vision  program s  [Feldma n  an d  Yakimovsk y  1974 ;  Bolle s  1977 ; Garve y  1976 ; Bal ­
`lard  1978 ; Sproul l  1977] . 
`
`13.2.1  Planning , Scoring , an d Thei r  Interactio n 
`
`For  didacti c  purposes ,  th e  processe s  o f  pla n  generatio n  an d  pla n  scorin g  ar e  con ­
`sidered  separately .  I n  fact ,  thes e  processe s  ma y  cooperat e  mor e  o r les s  intimately . 
`The planne r  produce s  "sequences " o f actions  fo r  evaluatio n  b y th e scorer .  Eac h ac ­
`tion  (computation ,  informatio n  gathering ,  performin g  a   real­worl d  action )  ha s  a 
`cost,  expressin g  expenditur e  o f  resources ,  o r  associate d  unhappiness .  A n  actio n 
`has a  se t  o f possibl e  outcomes,   o f whic h  onl y on e wil l reall y occu r whe n  th e actio n  i s 
`performed.  A  goalis   a  stat e  o f th e  worl d  wit h  a n  associate d  "happiness "  o r  utility. 
`For  th e purpose s  o f uniformit y  an d forma l  manipulation ,  goal s ar e treate d a s  (null ) 
`actions wit h n o outcomes ,  an d  negativ e  utilitie s ar e use d t o expres s costs . The n  th e 
`plan  ha s onl y action s i n it ; the y  ma y b e arrange d  i n a  stric t sequence ,  o r b e i n loops , 
`be conditiona l  o n outcome s o f othe r actions , an d s o  forth . 
`The  scoring  proces s  evalute s  th e  expected   utility  o f  a   plan .  I n  a n  uncertai n 
`world,  a  pla n  prio r  t o executio n  ha s onl y a n  expecte d  goodness—somethin g  migh t 
`go wrong . Suc h a  scorin g proces s typicall y  i s no t  o f interes t  t o thos e  wh o woul d  us e 
`planners  t o  solv e  puzzle s  o r  d o  proofs ;  wha t  i s  interestin g  i s  th e  result ,  no t  th e 
`effort.  Bu t  plan s  tha t ar e  "optimal "  i n som e  sens e  ar e decidedl y  o f interes t  i n  real ­
`world  decisio n  making .  I n  a  visio n  context ,  plan s  ar e  usuall y  usefu l  onl y  i f  the y 
`can b e evaluate d  fo r efficienc y  an d  efficacy . 
`Scoring  ca n  tak e  plac e  o n  "complete "  plans ,  bu t  i t ca n  als o  b e  use d  t o  guid e 
`plan  generation .  Th e  usua l  artificia l  intelligenc e  problem­solvin g  technique s  o f 
`progressive  deepenin g  searc h  an d  branch­and­boun d  prunin g  ma y  b e  applie d  t o 
`planning  i f scorin g  happen s  a s th e  pla n  i s generate d  [Nilsso n  1980] . Scorin g  ca n  b e 
`used  t o  asses s  th e  cos t  o f  plannin g  an d  t o  monito r  plannin g  horizon s  (ho w  fa r 
`ahead  t o  loo k  an d  ho w  detaile d  t o  mak e  th e  plan) . Scorin g  wil l  penaliz e  plan s  tha t 
`loop  withou t  producin g  results .  Pla n  improvements ,  suc h  a s  replannin g  upo n 
`failure,  ca n  b e  assesse d  wit h  scores ,  an d  th e  contributio n  o f  additiona l  step s  (sa y 
`for  extr a  informatio n  gathering )  ca n  b e  assesse d  dynamicall y  b y  scoring .  Scorin g 
`can  b e  arbitraril y  comple x  utilit y  functions ,  thu s  reflectin g  suc h  concept s  a s  "ris k 
`aversion"  an d nonlinea r  valu e o f resource s  [Raiff a  1968] . 
`
`13.2.2  Scorin g Simpl e Plan s 
`
`Scoring and  an   Example 
`A  simple  plan   i s a  tre e  o f node s  (ther e  ar e  n o  loops) . Th e  node s  represen t  ac ­
`tions  (an d goals) . Outcome s  ar e represente d  b y labele d arc s i n th e tree . A  probabil ­
`ity  o f  occurrenc e  i s associate d  wit h  eac h  possibl e  outcome ;  sinc e  exactl y  on e  out ­
`come  actuall y  occur s  pe r  action ,  th e  probabilitie s  fo r  th e  possibl e outcome s  o f  an y 
`action su m  t o  unity . 
`The  score  o f a  pla n  i s it s expected  utility.  Th e expecte d  utilit y  o f an y nod e  i s re ­
`cursively  define d  a s  it s  utilit y  time s  th e  probabilit y  o f  reachin g  tha t  nod e  i n  th e 
`
`446 
`
`Ch.  13   Goal   Achievement 
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 458
`
`

`

`plan, plu s th e expecte d  utilitie s o f th e action s a t it s  (possible ) outcomes .  Th e pro ­
`bability  o f reachin g  an y  "goa l  state "  i n th e pla n i s th e produc t  o f probabilitie s o f 
`outcomes formin g a  pat h fro m th e roo t o f th e pla n t o th e goa l state . 
`As a n example , conside r th e pla n show n i n Fig .  13.4 . I f th e pla n o f Fig . 13. 4 
`
`Table locate d 
`
`Table no t locate d 
`
`Find telephon e 
`shape 
`
`Do no t 
`find telephon e 
`shape 
`
`Telephone 
`there 
`
`No telephon e 
`there 
`
`P13 
`
`PU 
`
`Fig.  13. 4  Thi s  pla n  t o  find  a   telephon e  i n  a n  offic e  scen e  involve s  finding  a   tabl e  first 
`and  lookin g  ther e  i n  mor e  detail .  Th e  action s  an d  outcome s  ar e  shown .  Th e  probabilitie s 
`of  outcome s  ar e  assigne d  symbol s  (P10 ,  etc.) .  Utilitie s  (denote d  b y  U: )  ar e  give n  fo r  th e 
`individual  actions .  Not e  tha t  negativ e  utilitie s  ma y  b e  considere d  costs .  I n  thi s  example , 
`decision­makin g  take s  n o  effort ,  imag e  processin g  cost s  vary ,  an d  ther e  ar e  variou s  penal ­
`ties  an d  reward s  fo r  correc t  an d  incorrec t  finding   o f  th e  telephone . 
`
`Sec. 13.2 Planning with Costs
`
`447 
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 459
`
`

`

`has  probabilitie s  assigne d  t o  it s  outcomes ,  w e  ma y  comput e  it s expecte d  utility . 
`Figure  13. 5 show s  th e  calculation .  Th e  probabilit y  o f  correctl y  findin g  th e  tele ­
`phone i s 0.34 , an d th e expecte d utilit y o f th e pla n i s 433 . 
`Although  th e generatio n  o f a  pla n ma y no t b e easy , scorin g a  pla n i s a  trivia l 
`exercise onc e th e probabilitie s an d utilitie s ar e known . I n practice , th e assignmen t 
`of probabilitie s i s usuall y a  sourc e o f difficulty .  Th e followin g i s a n exampl e  usin g 
`
`Find telephon e 
`shape 
`
`Do no t 
`find  telephon e 
`shape 
`
`Telephone 
`there 
`
`No telephon e 
`there 
`
`0.95 
`
`Fig.  13. 5  A s  fo r  Fig .  13.4 .  U :  give s  th e  utilit y  o f  eac h  action .  E(U) :  give s  th e  expecte d 
`utillity  o f  th e  action ,  whic h  depend s  o n  th e  outcome s  belo w  it .  Value s  fo r  outcom e  proba ­
`bilities  ar e give n  o n  th e  outcom e  arcs . 
`
`448 
`
`Ch.  13   Coal   Achievement 
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 460
`
`

`

`the  telephone­findin g  pla n  an d  som e  assumption s  abou t  th e tests .  Differen t  as ­
`sumptions yiel d differen t  scores . 
`Computing Outcome  Probabilities:  An  Example 
`This exampl e relie s heavil y o n Bayes ' rule : 
`
`P(B\A)P(A)  =  P(AAB)   =  P(A\B)P(B).  
`
`(13.1 ) 
`
`Let  u s assum e a  specifi c  a  prior i  probabilit y  tha t  th e  scen e  contain s a  tele ­
`phone. 
`
`(13.2 ) 
`P\  =  aprior i probabilit y  o f Telephon e 
`Also assum e tha t somethin g i s know n abou t th e behavio r o f th e variou s test s i n th e 
`presence o f wha t  the y  ar e  lookin g  for .  Thi s  knowledg e  ma y  accru e fro m  experi ­
`ments  t o se e  ho w  ofte n  th e tabl e  tes t  foun d  table s  whe n  telephone s  (o r tables ) 
`were an d wer e no t present .  Le t u s assum e tha t th e followin g ar e know n probabili ­
`ties. 
`
`(13.3 ) 
`Pi =  P(tabl e  located|telephon e  i n scene ) 
`(13.4 ) 
`Ps  =  P(tabl e located|n o  telephon e i n scene ) 
`Either ther e i s a  telephon e o r ther e i s not , an d a  tabl e i s locate d o r i t i s not , s o 
`P2 =  a  prior i probabilit y o f n o telephon e =   1  —  P\  
`Pi,  =  P(n o tabl e locate d |telephon e i n scene )  =   1  —  P 3 
`P(, =  P(n o tabl e locate d |n o telephon e i n scene ) =   1  —   P 5 
`Similarly wit h th e "shap e test " fo r telephones : assum e probabilitie s 
`P1 =  P  (telephon e shap e locate d |  telephone ) 
`P9=  P(telephon e shap e locate d |n o telephone ) 
`
`(13.8 ) 
`(13.9 ) 
`
`(13.5 ) 
`(13.6 ) 
`(13.7 ) 
`
`with 
`
`(13.10 ) 
`
`P l0=l­P 9 
`
`Ps=l­P 7, 
`as above . 
`There ar e a  fe w point s t o make : First , i t i s no t necessar y t o kno w exactl y thes e 
`probabilities  i n orde r  t o scor e  th e plan ;  on e  coul d  us e  relate d  probabilitie s  an d 
`Bayes' rule . Othe r usefu l  probabilitie s ar e o f th e for m 
`P (telephon e |  telephon e shap e located) . 
`In  som e  system s  [Garve y  1976 ]  thes e  ar e  assume d  t o b e  availabl e directly . Thi s 
`section  show s  ho w t o deriv e  the m  fro m  know n  conditiona l  probabilitie s  tha t 
`describe th e behavio r o f detector s give n certai n scen e phenomena . 
`Second,  notic e  th e assumptio n  tha t althoug h  bot h  th e outcom e  o f th e  tabl e 
`test an d th e shap e tes t depen d o n th e presenc e o f telephones , the y ar e take n t o b e 
`independent o f eac h other . Tha t is , havin g foun d a  tabl e tell s u s nothin g abou t th e 
`likelihood o f finding  a  telephon e shape . Independenc e assumption s suc h a s thi s ar e 
`
`Sec.  13.2   Planning   with   Costs  
`
`4 4 9 
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 461
`
`

`

`useful  t o limi t computation s an d dat a gathering , bu t ca n b e somewha t  unrealistic . 
`To accoun t fo r th e dependence , on e woul d hav e t o measur e suc h quantitie s a s 
`P(telephone shap e found|tabl e  located) . 
`Now t o comput e som e outcom e probabilities : Conside r th e probabilit y 
`Pu  =  P  (tabl e located ) 
`
`(13.11 ) 
`
`Let u s writ e 
`TL fo r Tabl e Locate d 
`TNL fo r Tabl e No t Located . 
`A  tabl e  ma y  b e  locate d  whethe r  o r  no t  a  telephon e  i s  i n  th e  scene .  I n  term s  o f 
`known probabilities , Bayes ' rul e yield s 
`Pu^PiPi  +  PsPi  
`
`(13­12 ) 
`
`Then 
`
`(13.13 ) 
`
`P12  =   />(TNL )  =   \~P n 
`Calculating P 13 show s a  nea t tric k usin g Bayes ' Rule : 
`(13.14 ) 
`Pu  =  P  (telephon e |TNL ) 
`That  is ,  P1 3 i s  th e  probabilit y  tha t  ther e  i s  a  telephon e  i n  th e  scen e  give n  tha t 
`search fo r a  tabl e wa s unsuccessful . Thi s probabilit y i s no t know n directly , bu t 
`p  _   P  (telephon e an d TNL ) 
`13 
`P(TNL ) 
`P (TN L an d telephone ) 
`Pn 
`=  [P  (TN L |  telephone ) P  (telephone ) ]  
`Pn 
`
`, J 3 15 N 
`
`[P4P\] 
`Pn 
`
`Then, o f cours e 
`
`(13.16 ) 
`P u ­ l ­ P n 
`Reasoning  i n  thi s  wa y  usin g  th e  conditiona l  probabilitie s  an d  assumption s 
`about thei r independenc e allow s th e completio n o f th e calculatio n o f outcom e pro ­
`babilities  (se e th e Exercises) .  On e possibl y confusin g  poin t occur s i n calculatio n o f 
`P ] 5 ,  whic h i s 
`
`P\s=  P  (telephon e shap e foun d |  tabl e located ) 
`(13.17 ) 
`By assumption , thes e event s ar e onl y indirectl y related . B y th e simplifyin g assump ­
`tions o f independence ,  th e shap e operato r  an d th e tabl e operato r  ar e independen t 
`in thei r operation .  (Suc h assumption s  migh t  b e fals e  i f the y use d commo n  imag e 
`processing subroutines , fo r example. )  O f course , th e probabilit y o f succes s o f eac h 
`
`4 5 0 
`
`Ch.   13   Coal   Achievement 
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 462
`
`

`

`depends o n th e presenc e o f a  telephon e i n th e scene .  Therefor e thei r  performanc e 
`is linke d i n th e followin g wa y (se e th e Exercises) . (Writ e TS L fo r Telephon e Shap e 
`Located.) 
`P15 =   P  (TS L |TL ) P  (TS L |  telephone ) P  (telephon e |TL ) 
`+P(TSL|no telephone) Pino  telephone|TL ) 
`
`(13.18 ) 
`
`13.2.3  Scorin g Enhance d Plan s 
`
`The  plan s o f Sectio n  13.2. 2 wer e calle d  "simple "  becaus e  o f thei r  tre e  structure , 
`complete orderin g o f actions , an d th e simpl e action s o f thei r nodes . Wit h a  riche r 
`output  fro m  th e symboli c planner ,  th e plan s ma y hav e differen t  structure . Fo r ex ­
`ample,  ther e  ma y b e  OR  nodes , an y on e o f whos e son s wil l achiev e th e actio n a t 
`the node ; AND  nodes , al l o f whic h mus t b e satisfie d  (i n an y order ) fo r th e actio n t o 
`be satisfactoril y completed ; SEQUENCE  nodes , whic h specif y  a  se t o f action s an d a 
`particular  orde r  i n  whic h  t o  achiev e  them .  Th e  pla n  ma y  hav e  loops ,  share d 
`subgoal structure , o r goal s tha t depen d o n eac h other . Ho w enhance d plan s ar e in ­
`terpreted  an d  execute d  depend s  o n  th e  scorin g  algorithms ,  th e  possibilitie s  o f 
`parallel  execution ,  whethe r  executio n  an d  scorin g  ar e  interleaved ,  an d s o  forth . 
`This  treatmen t  ignore s  parallelis m  an d  limit s  discussio n  t o  expandin g  enhance d 
`plans int o simpl e ones . 
`It shoul d  b e clea r ho w t o g o abou t convertin g man y o f thes e enhance d  plan s 
`to  simpl e  plans . Fo r  instance ,  sequenc e  node s  simpl y  g o  t o a  uniqu e  pat h o f ac ­
`tions.  Alternatively ,  dependin g  o n  assumption s  abou t  outcome s  o f suc h  action s 
`(say  whethe r  the y  ca n  fail) ,  the y  ma y  b e  coalesce d  int o  on e  action ,  a s wa s  th e 
`"threshold, find  blobs , an d comput e shapes " actio n i n th e telephone­findin g  plan . 
`Rather  mor e  interestin g  ar e  th e  O R  an d  AN D  nodes ,  th e  orde r  o f  whos e 
`subgoals  i s unspecified .  Eac h suc h  nod e yield s man y  simpl e plans , dependin g  o n 
`the  orde r  i n  whic h  th e subgoal s ar e attacked .  On e wa y t o  scor e suc h  a  pla n  i s t o 
`generate al l possibl e simpl e plan s an d scor e eac h one , bu t perhap s i t i s possibl e t o 
`do better .  Fo r example , loop s an d mutua l dependencie s i n plan s ca n b e deal t wit h 
`in variou s ways . A  loo p ca n b e analyze d t o mak e sur e tha t i t contain s a n exi t  (suc h 
`as a  branc h o f a n O R nod e  tha t  ca n b e executed) .  On e ca n  mak e a d ho c assump ­
`tions tha t  th e cos t o f executio n  i s alway s mor e tha n  th e cos t o f plannin g  [Garve y 
`1976], an d  scor e th e loo p b y it s executabl e  branch . Anothe r  ide a i s t o pla n incre ­
`mentally  wit h  a   finite   horizon ,  expandin g  th e  pla n  throug h  som e  progressiv e 
`deepening,  heuristi c  search ,  o r  prunin g  strategy .  Th e  accumulate d  cos t o f goin g 
`around a  loo p wil l soo n remov e i t fro m furthe r  consideration . 
`Recall  (Figs . 13. 4 an d  13.5 )  tha t  th e expecte d  utilit y o f a  pla n wa s define d  a s 
`the su m o f th e utilit y o f eac h lea f nod e time s th e probabilit y o f reachin g tha t node . 
`However,  th e utilitie s nee d  no t combin e  linearl y  i n scoring . Differen t  monotoni c 
`functions  o f  utilit y  expres s  suc h  differen t  conception s  a s  "aversio n  t o  risk "  o r 
`"gambling addiction. "  Thes e  consideration s ar e rea l ones , an d  nonlinea r  utilitie s 
`are th e rul e rathe r tha n  th e exception .  Fo r instance , th e valu e o f mone y i s notori ­
`ously nonlinear . Man y peopl e woul d pa y $ 5 fo r  a n eve n chanc e t o wi n $15 ; no t s o 
`many peopl e woul d pa y $5,00 0 fo r a n eve n chanc e t o wi n $15,000 . 
`
`Sec.  13.2   Planning   with   Costs  
`
`45 1 
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 463
`
`

`

`One commo n wa y t o comput e score s base d o n utilitie s i s th e  "cost/benefit " 
`ratio. This , i n th e for m  "cost/confidence "  ratio , i s use d b y Garve y i n hi s plannin g 
`vision  system .  Thi s  measur e  i s examine d  i n  Sectio n  13.2.5 ; roughly ,  hi s  "cost " 
`was th e effor t  i n machin e  cycle s t o achiev e goals , an d  hi s "confidence "  approxi ­
`mated th e probabilit y o f a  goa l achievin g th e correc t outcome . Th e utilit y o f correc t 
`outcomes wa s no t explicitl y encode d i n hi s planner . 
`Sequential pla n elaboratio n o r partia l pla n elaboratio n ca n b e interleave d wit h 
`execution  an d  scoring .  Mos t  practica l  plannin g  i s  don e  i n  interactio n  wit h  th e 
`world,  an d  th e  pla n  scorin g  approac h  lend s  itsel f  wel l  t o  assessin g  suc h  interac ­
`tions.  I n  Sectio n  13.2. 5  consider s  a   plannin g  visio n  syste m  tha t  use s  enhance d 
`plans an d a  limite d replannin g capability . 
`A thorn y proble m  fo r decisio n makin g i s t o asses s th e cos t o f plannin g itself . 
`The plannin g proces s i s give n it s ow n utilit y  (cost) , an d i s carrie d onl y ou t a s fa r a s 
`is indicated .  O f course , th e proble m i s i n genera l infinitel y  recursive , sinc e ther e i s 
`also th e cos t o f assessin g  th e cos t