From: bryan@ad.cise.nsf.gov (Bryan Thompson)
Subject: Re: Heuristic Dynamic Programming
Reply-To: bryan@ad.cise.nsf.gov
Organization: National Science Foundation
Date: Thu, 13 Aug 1992 14:43:48 GMT

In article <691@trwacs.fp.trw.com> erwin@trwacs.fp.trw.com (Harry  
Erwin) writes:
> Just a short note concerning Paul Werbos' heuristic dynamic  
programming
> (HDP). HDP is actually a link between two disparent areas of  
artificial
> intelligence: neural networks and AI planners. This is because a  
heuristic
> dynamic program is actually a plan consisting of a set of local  
goals and
> linkages that if followed will lead to a long-term strategic goal.  
I am
> willing to speculate that the function of the cerebellar cortex is  
to
> store these plans, indexed by strategic goal, and replay them on  
command.
> I'm also willing to speculate that there is a chaotic process that  
runs in
> the cerebral cortex that is used to generate candidate plans for
> optimization and later storage in the cerebellar cortex.
> 
> Cheers,
> -- 
> Harry Erwin
> Internet: erwin@trwacs.fp.trw.com

A prefix to what has grown into a larger reply -- you are right.  HDP  
does provide the bridge between AI and connectionist systems.  Now,  
on to my quibbles.

Yes, the internal state in HDP is used to index another network, the  
action network, that reflexively generates sequences of actions (and  
is adapted by the critic network which is computing a heuristic  
version of dynamic programming).  However, I would not claim that the  
cerebellar cortex was the action network.  (I think that the action  
network can be located in a subset of the centrifugal connections in  
the cerebral cortex; i.e. those carrying information towards the  
sensory / motor periphery). Neither would I claim that the internal  
state corresponds directly to the AI concept of a goal / subgoal.

My understanding of the cerebellar cortex is much more in line with  
motion smoothing than storing the plans resulting from the long-range  
optimizations provided by HDP.  I see that differentiated intentions  
(i.e. plans or action sequences) enter the cerebellar cortex at one  
temporal grain and are piecewise smoothed into expressed motions.   
You can look at HDP in terms of goals, but I find the analogy  
misleading.  Certainly the cerebrum is developing the internal state  
representation against which the measure of value or utility for HDP  
are assessed.  However, I don't see a role for *goals* in the AI  
sense in biological systems.  In order to have a clear goals in HDP  
you need to be informed when you have reached states where the sum of  
expected future value / utility is exactly known.  I would argue that  
biological systems do not have such terminal states.

I have done some work, in natural language processing, where an HDP  
architecture is used to control internal actions that shift the  
"focus" by pushing and popping "goals".  This is implemented using  
deictic markers that control which sections of a parse tree (which  
you would map onto recurrent connections in a NN) are visible as part  
of the internal state.  It turns out that by looking at two  
structurally defined points on a parse tree and 2-3 buffered  
constituents that have not been attached to the parse tree, that you  
have a complete *decision space* for syntactic processing of natural  
language (English in this case).  Please notice that the decision  
space is much smaller than the internal state of the network  
representations involved, but is complete for assessing the potential  
value of actions.  The parser is an extension of Mitch Marcus's  
PARSIFAL.  Some recent related work on NN implementations of stacks,  
"Learning Context-fre Grammers:..." by Das, Giles, and Sun, is in the  
neuroprose archive.

--
Bryan Thompson
Computer Scientist
National Science Foundation

bryan@ad.cise.nsf.gov



-- NewsGrazer, a NeXTstep(tm) news reader, posting --
M>UQR=&8P7&%N<VE[7&9O;G1T8FQ<9C!<9FUO9&5R;B!#;W5R:65R.WT*7&UA
M<F=L,3(P"EQM87)G<C$R,`I[7&-O;&]R=&)L7')E9#!<9W)E96XP7&)L=64P
M.WT*7'!A<F1<='@Y-C!<='@Q.3(P7'1X,C@X,%QT>#,X-#!<='@T.#`P7'1X
M-3<V,%QT>#8W,C!<='@W-C@P7'1X.#8T,%QT>#DV,#!<9C!<8C!<:3!<=6PP
M7&9S,C0@26X@87)T:6-L92`\-CDQ0'1R=V%C<RYF<"YT<G<N8V]M/B!E<G=I
M;D!T<G=A8W,N9G`N=')W+F-O;2`H2&%R<GD@17)W:6XI('=R:71E<SI<"CX@
M2G5S="!A('-H;W)T(&YO=&4@8V]N8V5R;FEN9R!0875L(%=E<F)O<R<@:&5U
M<FES=&EC(&1Y;F%M:6,@<')O9W)A;6UI;F=<"CX@*$A$4"DN($A$4"!I<R!A
M8W1U86QL>2!A(&QI;FL@8F5T=V5E;B!T=V\@9&ES<&%R96YT(&%R96%S(&]F
M(&%R=&EF:6-I86Q<"CX@:6YT96QL:6=E;F-E.B!N975R86P@;F5T=V]R:W,@
M86YD($%)('!L86YN97)S+B!4:&ES(&ES(&)E8V%U<V4@82!H975R:7-T:6-<
M"CX@9'EN86UI8R!P<F]G<F%M(&ES(&%C='5A;&QY(&$@<&QA;B!C;VYS:7-T
M:6YG(&]F(&$@<V5T(&]F(&QO8V%L(&=O86QS(&%N9%P*/B!L:6YK86=E<R!T
M:&%T(&EF(&9O;&QO=V5D('=I;&P@;&5A9"!T;R!A(&QO;F<M=&5R;2!S=')A
M=&5G:6,@9V]A;"X@22!A;5P*/B!W:6QL:6YG('1O('-P96-U;&%T92!T:&%T
M('1H92!F=6YC=&EO;B!O9B!T:&4@8V5R96)E;&QA<B!C;W)T97@@:7,@=&]<
M"CX@<W1O<F4@=&AE<V4@<&QA;G,L(&EN9&5X960@8GD@<W1R871E9VEC(&=O
M86PL(&%N9"!R97!L87D@=&AE;2!O;B!C;VUM86YD+EP*/B!))VT@86QS;R!W
M:6QL:6YG('1O('-P96-U;&%T92!T:&%T('1H97)E(&ES(&$@8VAA;W1I8R!P
M<F]C97-S('1H870@<G5N<R!I;EP*/B!T:&4@8V5R96)R86P@8V]R=&5X('1H
M870@:7,@=7-E9"!T;R!G96YE<F%T92!C86YD:61A=&4@<&QA;G,@9F]R7`H^
M(&]P=&EM:7IA=&EO;B!A;F0@;&%T97(@<W1O<F%G92!I;B!T:&4@8V5R96)E
M;&QA<B!C;W)T97@N7`H^(%P*/B!#:&5E<G,L7`H^("TM(%P*/B!(87)R>2!%
M<G=I;EP*/B!);G1E<FYE=#H@97)W:6Y`=')W86-S+F9P+G1R=RYC;VU<"EP*
M02!P<F5F:7@@=&\@=VAA="!H87,@9W)O=VX@:6YT;R!A(&QA<F=E<B!R97!L
M>2`M+2!Y;W4@87)E(')I9VAT+B`@2$10(&1O97,@<')O=FED92!T:&4@8G)I
M9&=E(&)E='=E96X@04D@86YD(&-O;FYE8W1I;VYI<W0@<WES=&5M<RX@($YO
M=RP@;VX@=&\@;7D@<75I8F)L97,N7`I<"EEE<RP@=&AE(&EN=&5R;F%L('-T
M871E(&EN($A$4"!I<R!U<V5D('1O(&EN9&5X(&%N;W1H97(@;F5T=V]R:RP@
M=&AE(&%C=&EO;B!N971W;W)K+"!T:&%T(')E9FQE>&EV96QY(&=E;F5R871E
M<R!S97%U96YC97,@;V8@86-T:6]N<R`H86YD(&ES(&%D87!T960@8GD@=&AE
M(&-R:71I8R!N971W;W)K('=H:6-H(&ES(&-O;7!U=&EN9R!A(&AE=7)I<W1I
M8R!V97)S:6]N(&]F(&1Y;F%M:6,@<')O9W)A;6UI;F<I+B`@2&]W979E<BP@
M22!W;W5L9"!N;W0@8VQA:6T@=&AA="!T:&4@8V5R96)E;&QA<B!C;W)T97@@
M=V%S('1H92!A8W1I;VX@;F5T=V]R:RX@("A)('1H:6YK('1H870@=&AE(&%C
M=&EO;B!N971W;W)K(&-A;B!B92!L;V-A=&5D(&EN(&$@<W5B<V5T(&]F('1H
M92!C96YT<FEF=6=A;"!C;VYN96-T:6]N<R!I;B!T:&4@8V5R96)R86P@8V]R
M=&5X.R!I+F4N('1H;W-E(&-A<G)Y:6YG(&EN9F]R;6%T:6]N('1O=V%R9',@
M=&AE('-E;G-O<GD@+R!M;W1O<B!P97)I<&AE<GDI+B!.96ET:&5R('=O=6QD
M($D@8VQA:6T@=&AA="!T:&4@:6YT97)N86P@<W1A=&4@8V]R<F5S<&]N9',@
M9&ER96-T;'D@=&\@=&AE($%)(&-O;F-E<'0@;V8@82!G;V%L("\@<W5B9V]A
M;"Y<"EP*37D@=6YD97)S=&%N9&EN9R!O9B!T:&4@8V5R96)E;&QA<B!C;W)T
M97@@:7,@;75C:"!M;W)E(&EN(&QI;F4@=VET:"!M;W1I;VX@<VUO;W1H:6YG
M('1H86X@<W1O<FEN9R!T:&4@<&QA;G,@<F5S=6QT:6YG(&9R;VT@=&AE(&QO
M;F<M<F%N9V4@;W!T:6UI>F%T:6]N<R!P<F]V:61E9"!B>2!(1%`N("!)('-E
M92!T:&%T(&1I9F9E<F5N=&EA=&5D(&EN=&5N=&EO;G,@*&DN92X@<&QA;G,@
M;W(@86-T:6]N('-E<75E;F-E<RD@96YT97(@=&AE(&-E<F5B96QL87(@8V]R
M=&5X(&%T(&]N92!T96UP;W)A;"!G<F%I;B!A;F0@87)E('!I96-E=VES92!S
M;6]O=&AE9"!I;G1O(&5X<')E<W-E9"!M;W1I;VYS+B`@66]U(&-A;B!L;V]K
M(&%T($A$4"!I;B!T97)M<R!O9B!G;V%L<RP@8G5T($D@9FEN9"!T:&4@"EQP
M87)D7'1X,3$U,EQT>#(S,#1<='@S-#4V7'1X-#8P.%QT>#4W-C!<='@V.3$R
M7'1X.#`V-%QT>#DR,39<='@Q,#,V.%QT>#$Q-3(P7&9C,"!A;F%L;V=Y"EQP
M87)D7'1X.38P7'1X,3DR,%QT>#(X.#!<='@S.#0P7'1X-#@P,%QT>#4W-C!<
M='@V-S(P7'1X-S8X,%QT>#@V-#!<='@Y-C`P("!M:7-L96%D:6YG+B`@0V5R
M=&%I;FQY('1H92!C97)E8G)U;2!I<R!D979E;&]P:6YG('1H92!I;G1E<FYA
M;"!S=&%T92!R97!R97-E;G1A=&EO;B!A9V%I;G-T('=H:6-H('1H92!M96%S
M=7)E(&]F('9A;'5E(&]R('5T:6QI='D@9F]R($A$4"!A<F4@87-S97-S960N
M("!(;W=E=F5R+"!)(&1O;B=T('-E92!A(')O;&4@9F]R("IG;V%L<RH@:6X@
M=&AE($%)('-E;G-E(&EN(&)I;VQO9VEC86P@<WES=&5M<RX@($EN(&]R9&5R
M('1O(&AA=F4@82!C;&5A<B!G;V%L<R!I;B!(1%`@>6]U(&YE960@=&\@8F4@
M:6YF;W)M960@=VAE;B!Y;W4@:&%V92!R96%C:&5D('-T871E<R!W:&5R92!T
M:&4@<W5M(&]F(&5X<&5C=&5D(&9U='5R92!V86QU92`O('5T:6QI='D@:7,@
M97AA8W1L>2!K;F]W;BX@($D@=V]U;&0@87)G=64@=&AA="!B:6]L;V=I8V%L
M('-Y<W1E;7,@9&\@;F]T(&AA=F4@<W5C:"!T97)M:6YA;"!S=&%T97,N7`I<
M"DD@:&%V92!D;VYE('-O;64@=V]R:RP@:6X@;F%T=7)A;"!L86YG=6%G92!P
M<F]C97-S:6YG+"!W:&5R92!A;B!(1%`@87)C:&ET96-T=7)E(&ES('5S960@
M=&\@8V]N=')O;"!I;G1E<FYA;"!A8W1I;VYS('1H870@<VAI9G0@=&AE(")F
M;V-U<R(@8GD@<'5S:&EN9R!A;F0@<&]P<&EN9R`B9V]A;',B+B`@5&AI<R!I
M<R!I;7!L96UE;G1E9"!U<VEN9R!D96EC=&EC(&UA<FME<G,@=&AA="!C;VYT
M<F]L('=H:6-H('-E8W1I;VYS(&]F(&$@<&%R<V4@=')E92`H=VAI8V@@>6]U
M('=O=6QD(&UA<"!O;G1O(')E8W5R<F5N="!C;VYN96-T:6]N<R!I;B!A($Y.
M*2!A<F4@=FES:6)L92!A<R!P87)T(&]F('1H92!I;G1E<FYA;"!S=&%T92X@
M($ET('1U<FYS(&]U="!T:&%T(&)Y(&QO;VMI;F<@870@='=O('-T<G5C='5R
M86QL>2!D969I;F5D('!O:6YT<R!O;B!A('!A<G-E('1R964@86YD(#(M,R!B
M=69F97)E9"!C;VYS=&ET=65N=',@=&AA="!H879E(&YO="!B965N(&%T=&%C
M:&5D('1O('1H92!P87)S92!T<F5E+"!T:&%T('EO=2!H879E(&$@8V]M<&QE
M=&4@*F1E8VES:6]N('-P86-E*B!F;W(@<WEN=&%C=&EC('!R;V-E<W-I;F<@
M;V8@;F%T=7)A;"!L86YG=6%G92`H16YG;&ES:"!I;B!T:&ES(&-A<V4I+B`@
M4&QE87-E(&YO=&EC92!T:&%T('1H92!D96-I<VEO;B!S<&%C92!I<R!M=6-H
M('-M86QL97(@=&AA;B!T:&4@:6YT97)N86P@<W1A=&4@;V8@=&AE(&YE='=O
M<FL@<F5P<F5S96YT871I;VYS(&EN=F]L=F5D+"!B=70@:7,@8V]M<&QE=&4@
M9F]R(&%S<V5S<VEN9R!T:&4@<&]T96YT:6%L('9A;'5E(&]F(&%C=&EO;G,N
M("!4:&4@<&%R<V5R(&ES(&%N(&5X=&5N<VEO;B!O9B!-:71C:"!-87)C=7,G
M<R!005)3249!3"X@(%-O;64@<F5C96YT(')E;&%T960@=V]R:R!O;B!.3B!I
M;7!L96UE;G1A=&EO;G,@;V8@<W1A8VMS+"`B3&5A<FYI;F<@0V]N=&5X="UF
M<F4@1W)A;6UE<G,Z+BXN(B!B>2!$87,L($=I;&5S+"!A;F0@4W5N+"!I<R!I
M;B!T:&4@;F5U<F]P<F]S92!A<F-H:79E+EP*"EP*+2U<"D)R>6%N(%1H;VUP
M<V]N7`I#;VUP=71E<B!38VEE;G1I<W1<"DYA=&EO;F%L(%-C:65N8V4@1F]U
G;F1A=&EO;EP*7`IB<GEA;D!A9"YC:7-E+FYS9BYG;W9<"EP*"GT*
`