Designing distributed controllers for self-reconfiguring modular robots has been consistently challenging. We have developed a reinforcement learning approach which can be used both to automate controller design and to adapt robot behavior on-line. In this paper, we report on our study of reinforcement learning in the domain of self-reconfigurable modular robots: the underlying assumptions, the applicable algorithms and the issues of partial observability, large search spaces and local optima. We propose and validate experimentally in simulation a number of techniques designed to address these and other scalability issues that arise in applying machine learning to distributed systems such as modular robots. We discuss ways to make learning faster, more robust and amenable to on-line application by giving scaffolding to the learning agents in the form of policy representation, structured experience and additional information. With enough structure modular robots can run learning algorithms to both automate the generation of distributed controllers, and adapt to the changing environment and deliver on the self-organization promise with less interference from human designers, programmers and operators.
Andre, D. and Russell, S. (2000). Programmable reinforcement learning agents. Advances in Neural Information Processing SystemsLeen, T. K., Dietterich, T. G. and Tresp, V. (eds). Cambridge, MA, MIT Press.
2.
Bagnell, J.A. et al. (2004). Policy search by dynamic programming. Advances in Neural Information Processing Systems, Vol. 16, Thrun, S., Saul, L. K. and Scholkopf, B. (eds). Cambridge, MA, MIT Press.
3.
Baxter, J. and Bartlett, P.L. (2001). Infinite-horizon gradient-based policy search . Journal of Artificial Intelligence Research, 15: 319—350.
Butler, Z. et al. (2001). Cellular automata for decentralized control of self-reconfigurable robots. Proceedings of the International Conference on Intelligent Robots and Systems, Wailea, HI.
6.
Butler, Z. et al. (2004). Generic distributed control for locomotion with self-reconfiguring robots. International Journal of Robotics Research, 23(9): 919—938.
7.
Chang, Y.-H., Ho, T. and Kaelbling, L.P. (2004). All learning is local: multi-agent learning in global reward games. Advances in Neural Information Processing Systems, Vol. 16, Thrun, S., Saul, L. K. and Scholkopf, B. (eds). Cambridge, MA, MIT Press.
8.
Fernandez, F. and Parker, L.E. (2001). Learning in large cooperative multi-robot domains . International Journal of Robotics and Automation, 16(4): 217—226.
9.
Fitch, R. and Butler, Z. (2006). A million-module march. Digital Proceedings of the RSS Workshop on Self-Reconfigurable Modular Robotics , Philadelphia, PA.
10.
Grudic, G., Kumar, V. and Ungar, L.H. (2003). Using policy gradient reinforcement learning on autonomous robot controllers. Proceedings of the International Conference on Intelligent Robots and Systems, Las Vegas, NV.
11.
Guestrin, C., Koller, D. and Parr, R. (2002). Multiagent planning with factored MDPs. Advances in Neural Information Processing Systems, Vol. 14 Dietterich, T. G., Becker, S. and Ghahramani, Z. (eds). Cambridge, MA, MIT Press.
12.
Kamimura, A. et al. (2004). Distributed adaptive locomotion by a modular robotic system, M-TRAN II—from local adaptation to global coordinated motion using cpg controllers. Proceedings of the International Conference on Intelligent Robots and Systems, Sendai, Japan.
13.
Kitano, H. et al. (1997). RoboCup: The robot world cup initiative . Proceedings of the 1st International Conference on Autonomous Agents (Agents'97), Johnson, W. L. and Hayes-Roth, B. (eds). New York, ACM Press, pp. 340— 347.
14.
Kok, J.R. and Vlassis, N. (2006). Collaborative multiagent reinforcement learning by payoff propagation. Journal of Machine Learning Research , 7: 1789—1828.
15.
Kotay, K. and Rus, D. (2005). Efficient locomotion for a self-reconfiguring robot. Proceedings of the International Conference on Robotics and Automation, Barcelona, Spain.
16.
Kubica, J. and Rieffel, E. (2002). Collaborating with a genetic programming system to generate modular robotic code. GECCO 2002: Proceedings of the Genetic and Evolutionary Computation Conference, W. et al. (ed). New York, Morgan Kaufmann, pp. 804—811.
17.
Lagoudakis, M.G. and Parr, R. (2003). Least-squares policy iteration. Journal of Machine Learning Research,4: 1107— 1149.
18.
Martin, M. (2004). The essential dynamics algorithm: fast policy search in continuous worlds. Vision and Modeling Technical Report 582, Cambridge, MA, MIT Media Laboratory.
19.
Mataric, M.J. (1997). Reinforcement learning in the multi-robot domain . Autonomous Robots, 4(1): 73—83.
20.
Mytilinaios, E. et al. (2004). Designed and evolved blueprints for physical self-replicating machines. Proceedings of the 9th International Conference on Artificial Life (ALIFE IX), Boston, MA.
21.
Nagpal, R. (2002). Programmable self-assembly using biologically-inspired multiagent control. Proceedings of the 1st International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), Bologna, Italy.
22.
Ng, A.Y. et al. (2004). Autonomous inverted helicopter flight via reinforcement learning. Proceedings of the International Symposium on Experimental Robotics (ISER), Singapore.
23.
Ng, A.Y. and Jordan, M. (2000). PEGASUS: a policy search method for large MDPs and POMDPs. Proceedings of the International Conference on Uncertainty in AI (UAI), Stanford, CA.
24.
Peshkin, L. (2001). Reinforcement learning by policy search. Ph.D. Thesis, Brown University, Department of Computer Science .
25.
Schaal, S. et al. (2003). Learning movement primitives. Proceedings of the International Symposium on Robotics Research (ISRR), Siena, Italy.
26.
Schneider, J. et al. (1999). Distributed value functions. Proceedings of the International Conference on Machine Learning , Bled, Slovenia.
27.
Shoham, Y., Powers, R. and Grenager, T. (2003). Multi-agent reinforcement learning: a critical survey. Technical Report, Palo Alto, CA, Stanford University.
28.
Stone, P. and Veloso, M.M. (2000). Multiagent systems: a survey from a machine learning perspective, Autonomous Robots8(3): 345—383.
29.
Sutton, R.S. (1995). Generatlization in reinforcement learning: successful examples using sparse coarse coding. Advances in Neural Information Processing Systems, Touretzky, D. S., Mozer, M. C. and Hasselmo, M. E. (eds). Cambridge, MA, MIT Press, pp. 1038—1044.
30.
Sutton, R.S. and Barto, A.G. (1998). Reinforcement Learning. Cambridge, MA, MIT Press.
31.
Sutton, R.S. et al. (2000). Policy gradient methods for reinforcement learning with function approximation. Advances in Neural Information Processing Systems, Leen, T. K., Dietterich, T. G. and Tresp, V. (eds), Vol. 12. Cambridge, MA, MIT Press.
32.
Tedrake, R., Zhang, T.W. and Seung, H.S. (2005). Learning to walk in 20 minutes. Proceedings of the 14th Yale Workshop on Adaptive and Learning Systems, New Haven, CT.
33.
Varshavskaya, P., Kaelbling, L.P. and Rus, D. (2004). Distributed learning for modular robots. Proceedings of the International Conference on Intelligent Robots and Systems, Sendai, Japan.
34.
Varshavskaya, P., Kaelbling, L.P. and Rus, D. (2006). On scalability issues in reinforcement learning for self-reconfiguring modular robots. Digital Proceedings of RSS Workshop on Self-Reconfigurable Modular Robotics, Philadelphia, PA.
35.
Watkins, C.J.C.H. and Dayan, P. (1992). Q-learning. Machine Learning, 8(3—4): 279—292.
36.
Yu, W. et al. (2002). Using interaction-based learning to construct an adaptive and fault-tolerant multi-link floating robot. Proceedings of the International Workshop on Distributed Autonomous Robotic Systems (DARS), Vol. 5, Asama, H., Arai, T., Fukuda, T. and Hasegawa, T. (eds). Berlin, Springer, pp. 455—464.
37.
Zykov, V. et al. (2005). Self-reproducing machines. Nature, 435(7038): 163—164.
