Reply to Shawn Lockery

[Jose del R. MILLAN]

Regarding Shawn Lockery's question about connectionist approaches to navigation,
we have developed a reinforcement learning system that tackles the robot 
path-finding problem.

In order to study the feasibility of our approach, a first version (Millan &
Torras 1990a, 1990b) was required to generate a ``quasi-optimal path'' between
two fixed configurations in a given workspace with obstacles. The fact that the
robot is a point, allows us to concentrate on the capabilities of reinforcement
learning for the problem at hand. 

The third reference describes a review of existing connectionist approaches to
the problem. The abstracts of the first two papers can be found at the end of
this message. 

A forthcoming paper will describe the second version of the system. The new 
system combines reinforcement with supervised and unsupervised learning 
techniques to solve a more complex instance of the problem, namely, to generate 
quasi-optimal paths from any initial configuration to a fixed goal in a given 
workspace with obstacles.

Currently, we are extending the system to deal with dimensional mobile robots.

References

Millan, J. del R. & Torras, C. (1990a). Reinforcement connectionist learning 
for robot path finding: a comparative study. Proc. COGNITIVA-90, 123--131.

Millan, J. del R. & Torras, C. (1990b). Reinforcement learning: discovering
stable solutions in the robot path finding domain. Proc. 9th European
Conference on Artificial Intelligence, 219--221.

Millan, J. del R. & Torras, C. (To appear). Connectionist approaches to robot
path finding. In O.M. Omidvar (ed.) Progress in Neural Networks Series, Vol. 3.
Ablex Publishing Corporation.

-------------------------------------------------------------------------------
	Reinforcement Connectionist Learning for Robot
		Path Finding: A Comparative Study

ABSTRACT. A connectionist approach to robot path finding has been devised so as
to avoid some of the bottlenecks of algebraic and heuristic approaches, namely
construction of configuration space, discretization and step
predetermination. The approach relies on reinforcement learning. In order to
identify the learning rule within this paradigm that best suits the problem at
hand, an experimental comparison of 13 different such rules has been carried
out. The most promising rule has been shown to be that using predicted
comparison as reinforcement baseline, and the Hebbian formula as eligibility
factor.

-------------------------------------------------------------------------------
	Reinforcement Learning: Discovering Stable Solutions
		in the Robot Path Finding Domain

ABSTRACT. After outlining the drawbacks of classical approaches to robot
path finding, a prototypical system overcoming some of them and demonstrating
the feasibility of reinforcement connectionist learning approaches to the
problem is presented. The way in which the information is codified and the
computational model used allow to avoid both the explicit construction of
configuration space required by algebraic approaches as well as the
discretization and step homogeneity demands of heuristic search algorithms. In
addition, the simulations show that finding feasible paths is not as
computational expensive as it is usually assumed for a reinforcement learning
system. Finally, a mechanism is incorporated into the system to ``stabilise''
learning once an acceptable path has been found. 

-------------------------------------------------------------------------------

	Jose del R. MILLAN
	Institute for System Engineering and Informatics
	Commission of the European Communities. Joint Research Centre
	Building A36. 21020 ISPRA (VA). ITALY

	e-mail:	 j_millan at cen.jrc.it (try this one first, please), or
		 millan at lsi.upc.es