BARNARD@IU.AI.SRI.COM (Stephen Barnard) (04/13/87)
Everyone is familiar with Maxwell's demon, the tiny sprite that reverses the increase of entropy dictated by the 2nd Law of Thermodynamics. He sits at a trapdoor between two chambers containing a gas in equilibrium (i.e., with maximum entropy) and segregates the molecules into low- and high-energy populations, thereby moving the system away from equilibrium and *decreasing* its entropy. If Maxwell's demon could exist (and be tamed), we could build perpetual motion machines. The thermal gradient between the chambers could drive a heat engine. Brillouin killed the demon by considering the connection between thermodynamics and information theory. The demon would have to acquire information about the position and velocity of the molecules (for example, by bouncing photons off them), but this information would be gained only at a cost that would balance the decrease in entropy due to its actions. Demons of another kind are still alive and well in physics, however. Creutz described a Monte Carlo algorithm that simulates a system in thermal equilibrium, much like the Metropolis algorithm used in simulated annealing. The difference is that Creutz samples from the *microcanonical ensemble*, in which the system is considered to be thermally insulated (constant energy). When the state of the system changes randomly, its potential energy usually changes, and this difference is absorbed or emitted by a demon, which carries kinetic energy. What does this have to do with AI? Simulated annealing is an effective optimization technique. It's been used for several vision problems. Creutz's algorithm can be used in a new variant of simulated annealing that is simpler, more efficient, and more easily controlled than the standard Metropolis version. references: Brillouin, L., Science and Information Theory, Academic Press, New York, 1962. Creutz,M., Microcanonical Monte Carlo simulation, Physical Review Letters, vol. 50, no. 19, May 9, 1983, pp. 363-373. Barnard, S., Stereo matching by hierarchical, microcanonical annealing, SRI technical note 414 (to appear in Proc. IJCAI87). -------