May 2006
        

AI Expert Newsletter

AI - The art and science of making computers do interesting things that are not in their nature.

May 2006

 

Coding With Dinosaurs

Computer language design is just like a stroll in the park. Jurassic Park, that is.
This quote is by Larry Wall. I took it from Swaine's World, the website of Michael Swaine, columnist and editor for Dr. Dobbs. It reminds me of a poem which I've known for a long time, although I can't remember the author:
He coded in Fortran like hell,
wrote programs with whistle and bell.
Now feels that this tool
has made him a fool
but cannot get rid of its spell.

 

Robotics in Functional Languages

To date, robot programming has been an area rife with innovative approaches to systems and software development but relatively lacking in principled analysis. Yet, it is an area that provides an interesting and challenging basis for programming language research. In particular, the fact that almost all operations are based on time-varying quantities (indeed, time is a critical factor) in most algorithms offers new and interesting challenges to programming languages.

This quote comes from the conclusion to System Presentation — Functional Reactive Robotics: An Exercise in Principled Integration of Domain-Specific Languages, by Izzet Pembeci, Henrik Nilsson, and Gregory Hager. The point is that functional programs are easier to reason about and show correct than those that use "imperative" features such as updateable variables, assignment, and explicit state-changes. But, a language that can't change the state of the world would not be much use to a robot. Because of this, there has been a lot of research on how to extend functional languages so that they can describe state changes of the kind needed in robotics.

(The same is true, incidentally, of operating systems, which researchers recognised early on to be an important challenge to functional languages.)

System Presentation — Functional Reactive Robotics is a nice example of such research.Its authors show how a mobile robot control program can be formulated in a purely functional manner, and then implemented in the functional language Haskell. More specifically, they present a simple but realistic program which enables the robot — a two-wheeled differential-drive ActivMedia Robotics Pioneer 2 with stereo camera, on-board laptop, and the XVision2 real-time vision library — to follow an object while avoiding obstacles. The user can interact with the control program from the laptop, so the user interface had also to be coded functionally.

On the way to this example, the authors show how finite-state automata and subsumption architecture can be expressed functionally. While I haven't yet studied thought about the paper in detail, I think I like how they do subsumption.

Underlying this work is an "ontology": a collection of primitives with which one can talk about the inputs from robot sensors, the outputs to robot actuators, and the transformations between them. This had to be functional; it had to be expressive enough to specify realistic robot-control programs, while being easy to read and write; it had to be implementable efficiently enough to handle the robot; and the implementation had to interface with the XVision2 library.

The ontology used here builds on earlier work on Functional Reactive Programming (FRP), and sees the world in terms of "signals" and "signal functions". Signals are time-varying quantities. For example: the coordinates of the laptop's mouse; the velocity of a drive wheel; the position, colour and shape of a graphic to display on the laptop's screen; or the priority of a task. They are represented as functions from time to an appropriate type (which can be a compound type such as the record describing the graphic).

A program wouldn't be much use if it couldn't compute output signals from inputs. FRP conceptualises this in terms of "signal functions": functions that transform signals to other signals. A fair part of the paper discusses a notation in which signal functions can be conveniently composed from more basic signal functions; simplifies the notation by means of pattern-matching and intermediate names, thus omitting large amounts of "plumbing"; and uses it to describe robot tasks, including as finite-state automata and subsumption architectures. (The notation might be useful to those working on other functional or logic-programming systems, if only because it will suggest how to avoid passing references to actuators and sensors as arguments to every function or predicate.)

Because I am pressed for time, I'm not going to explain further in this feature, but will refer you to the paper. It does require some knowledge of functional programming (for example type definitions and combinators), and of Haskell syntax.

While reading the paper, I wondered about interfacing an FRP implementation to the Tekkotsu open-source robot-programming framework. I have written about Tekkotsu before, when discussing how to program the Sony Aibo robot dog. I mention it here because of the Tekkotsu Cognitive Robotics software. Amongst other interesting things, this implements a "dual coding" system, which represents images both symbolically and as "sketches" (two-dimensional pixel maps). There are operators for translating between the two, so image data can be processed in either form, depending on which is most convenient. Tekkotsu also has a variety of operators, such as flood-filling and skeletonisation, for generating sketches from other sketches; and for maintaining derivation trees showing the history of any particular sketch. All this adds up to a rich repertoire of data structures. It would seem worth investigating how efficiently these (especially the sketches) can be manipulated via FRP, whether new FRP abstractions are needed in order to make the code easy to write and read, and how easy it is to verify.

On the topic of verification, I also suspect that, being purely functional, FRP programs would be amenable to qualitative reasoning for producing high-level symbolic descriptions of their possible behaviours.

Programming is hard. Especially robot programming, where our minds lack the intuitions needed to think about the large numbers of simultaneous transformations being performed between the sensors that describe, and the actuators that affect, a complicated physical environment. We need to look into every technique — of which Functional Reactive Programming is one — that promises to make such programs more reliable.

Links

www.ida.liu.se/~henni/Publications/ppdp2002.pdf — System Presentation — Functional Reactive Robotics: An Exercise in Principled Integration of Domain-Specific Languages, by Izzet Pembeci, Henrik Nilsson, and Gregory Hager, Principles and Practice of Declarative Programming, 2002.

www.haskell.org/frp/index.html — Haskell.org's Functional Reactive Programming page.

people.csail.mit.edu/brooks/papers/how-to-build.pdf — How to Build Complete Creatures Rather than Isolated Cognitive Simulators, by Rodney Brooks. A good explanation of subsumption architecture by its originator.

www.cs.cmu.edu/~tekkotsu/cognitiverobotics.html — The Tekkotsu Cognitive Robotics page.

www.aaai.org/aitopics/html/qual.html — The AAAI Qualitative Reasoning page.

 

The programming musings blog: Haskell, moo-oriented programming, categories, and catamorphisms.

Replying to A Haskell bookshelf, an entry in "Jao" José Ortega-Ruiz's programming musings blog, reader Mark Hanford comments: "Wow, an impressive set of links. It looks like you.ve laid out all the resources anybody would need to dive into the Function/Haskell world".

In A Haskell bookshelf, Jao explains which books and Web pages you need in order to begin learning Haskell. One of these is Jonathan Tang's Write Yourself a Scheme in 48 Hours. Tang says that most Haskell tutorials teach the language by building up knowledge one construct at a time. Interesting and useful programs thus get left to the end, or even omitted altogether. However:

This tutorial takes a different tack. You'll start off with command-line arguments and parsing, and progress to writing a fully-functional Scheme interpreter that implements a good-sized subset of R5RS Scheme. Along the way, you'll learn Haskell's I/O, mutable state, dynamic typing, error handling, and parsing features. By the time you finish, you should be fairly fluent in both Haskell and Scheme.

Indeed, the first program in Tang's tutorial is a combinator-based parser based on Daan Leijen's Parsec library. Parsing with combinators is an elegant and quintessential application of functional programming; it deserves the same prominence in every programmer's toolbox of control-structures as multi-threading, coroutining, and backtracking.

(And, if your language of choice is Java, it shows what can be done when functions as first-class values, not methods, are your executable abstraction.)

Another entry is Moo-oriented programming, about Matt Webb's playsh multi-user text-adventure–like coding environment. This is based in part on the notion that a good user interface should take advantage of our ability to memorise landmarks, places, and stories.

Let me also recommend Programmers go bananas. These "bananas" are the banana-shaped brackets which, in the style of programming referred to here, denote a "catamorphism". Catamorphisms are recursive functions which follow the recursion pattern that I show below for calculating the length of a list: 

  length( [] ) = 0.
  length( cons( Head, Tail ) ) = 1 + length( Tail ).

(I hope this pseudo-code is intelligible. As in Lisp, I write cons to build a list from its head and tail. So cons(1,cons(2,cons(3,[]))) is the list [1,2,3].)

As functional programmers know, many list-processing functions take this form — sum, product, max … . Such functions can be succinctly defined using the higher-order function often named fold or foldr, thus saving the thinking time and chance of typos incurred by coding the recursion explicitly.

The notion of catamorphism was introduced by Erik Meijer, Maarten Fokkinga, and Ross Paterson, in their 1991 paper Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire. As Jao says in Programmers go bananas, to understand this paper, one needs some mathematical sophistication. What's important about it is that it shows why catamorphisms (and various other kinds of function named "anamorphisms", "paramorphisms", and "hylomorphisms") fit list-processing so nicely, and why so many useful functions can be defined using fold. It also shows how these ideas can be extended to other data types; and how, with all such functions, we can formulate some very general laws of program transformation that help us derive and verify our programs.

Catamorphisms work by taking a "picture" of the data and operations used to build a list, and "redrawing" them in a different but closely-related universe. Suppose we want to find the maximum of the list 

  [ x0, x1, …, xn ]
In terms of cons operations, we can rewrite this as 
  cons( x0, cons( x1, …, cons( xn, [] ) … ) )
And to get the maximum, we can "redraw" this description in the universe of max and -∞: 
  max(  x0, max(  x1, …, max(  xn, -∞ ) … ) )

I found a diagram that shows this more clearly, on the Spine Transformers page of Monad Comprehensions: A Versatile Representation for Queries by Torsten Grust. Don't worry about the rest of Grust's paper: it's worth reading, but all I'm referring to here is the diagram. The point is that category theory allows us to reason in a very general way about "redrawing": about moving some entity or activity from one universe to a second, changing it while retaining its essence. This, as Jao shows in the Functors diagram in Programmers go bananas, is one thing categories do. And that is why they are so important.

Links

jaortega.wordpress.com/2006/03/28/a-haskell-bookshelf/ — A Haskell bookshelf.

halogen.note.amherst.edu/%7Ejdtang/scheme_in_48/tutorial/overview.html — Write Yourself a Scheme in 48 Hours: A Haskell Tutorial, by Jonathan Tang.

www.cs.uu.nl/~daan/download/parsec/parsec.html — Parsec, a fast combinator parser, by Daan Leijen.

jaortega.wordpress.com/2006/03/22/moo-oriented-programming/ — Moo-oriented programming.

www.wired.com/news/technology/0%2c70413-0.html?tw=wn_technology_4 — Coding Tool Is a Text Adventure, by Quinn Norton, Wired, March 2006.

interconnected.org/home/2006/03/08/playsh — A summary of what playsh is, the "2006.03.08" entry in Matt Webb's Interconnected blog.

playsh.org/wiki/InspirationalProjects — InspirationalProjects, by Matt Web. The ideas that playsh is based on, amongst them that it should take advantage of our ability to memorise landmarks, paths, and stories.

jaortega.wordpress.com/2006/03/17/programmers-go-bananas/ — Programmers go bananas.

citeseer.ist.psu.edu/meijer91functional.html — Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire, by Erik Meijer, Maarten Fokkinga, and Ross Paterson, Proceedings 5th ACM Conference on Functional Programming Languages and Computer Architecture, 1991.

www.csd.abdn.ac.uk/~pgray/graduate_course2004/monad.pdf — Monad Comprehensions: A Versatile Representation for Queries, by Torsten Grust. I was writing about the diagram on Grust's Spine Transformers page.

hacks-galore.org/jao/ — Jao's home page.

 

How to do Research

I mentioned an older version of the first link below in the The Researchers' Bible section of the February 2006 Newsletter. Now I've found a current version. Here it is, together with other aids to doing research.

Links

homepages.inf.ed.ac.uk/bundy/how-tos/resbible.html — The Researcher's Bible, by Alan Bundy, Ben du Boulay, Jim Howe and Gordon Plotkin; with contributions by Graeme Ritchie and Peter Ross. 9th November 2004. Good advice on various aspects of research. These include: how to avoid over- or under-valuing your work; how to avoid using the wrong research methodology; how to deal with criticism; and how to overcome the psychological problems of Fear of Exposure, Theorem Envy, and Research Impotence, not to mention Solving the World, Yet Another Language, and Ambitious Paralysis.

homepages.inf.ed.ac.uk/bundy/how-tos/writingGuide.html — How to Write an Informatics Paper, by Alan Bundy: "The key to successful paper writing is an explicit statement of both a scientific hypothesis and the evidence to support (or refute) it". Bundy says that in informatics, authors rarely state their hypotheses. This makes papers hard for readers to understand and evaluate; and perhaps confuses authors too.

www2.cs.uregina.ca/~pwlfong/CS499/reading-paper.pdf — How to Read a CS Research Paper?, by Philip Fong. This and the following two overlap in some places, but not all.

www-static.cc.gatech.edu/fac/Spencer.Rugaber/txt/research_paper.txt — How to Read a Research Paper, by Spencer Rugaber.

hampshire.edu/~apmNS/design/RESOURCES/HOW_READ.html — How to Read a Scientific Research Paper-- a four-step guide for students and for faculty, by Ann McNeal.

www.ai.uga.edu/mc/WriteThinkLearn_files/frame.htm and www.ai.uga.edu/mc/WriteThinkLearn.pdf — How to Write More Clearly, Think More Clearly, and Learn Difficult Material More Easily, by Michael Covington.

effectmeasure.blogspot.com/2005/05/big-pharma-right-answers-for-wrong.html — Big Pharma: right answers for wrong questions, Posted by "Revere" in the Effect Measure public-health blog. This posting has a list of "Examples of Methods for Pharmaceutical Companies to Get the Results They Want from Clinical Trial": i.e. and by analogy, how researchers should not compare different medicines, engineering techniques, or programs.

 

Robot Ping-Pong and Other Risks

There is a nice(? find out for yourself) story about a Ping-Pong robot built at MIT. Now the guys who had built that machine were very proud of the device and wanted to show it to Mr. Minsky. First they explained to him how they built it, and made it recognize round objects with a certain amount of reflecting light, for what they had installed some lights, too. Now they turned on the lights, and started the software. One fact is important: mr. minsky is bald. They started the software, and he stand in front of the robot, directly in the lights..

****T H A N G*****, and the robot hit the 'ping pong ball'.

I had intended just to include this story as a bit of humour. Then I decided I ought also to introduce Risks Digest, from where it came. Go to the home page and type "AI" or "artificial intelligence" into the search box. Or just browse amongst the tales of worms, friendly fire, and the Visa fraud-detector that stopped a card because its owner had taken a ferry.

Links

catless.ncl.ac.uk/Risks/8.21.html#subj6.1 — ping-pong robot, Konrad Neuwirth, Risks Digest Volume 8, Issue 21, 1989.

catless.ncl.ac.uk/Risks/21.06.html#subj14.1 — Artificial Intelligence strikes again, Rodger Whitlock, Risks Digest Volume 21, Issue 6, 2000. The Visa-and-ferry story.

catless.ncl.ac.uk/Risks/1.16.html#subj1.1 — Intellectual honesty and the SDI, Bill Anderson, Risks Digest Volume 1, Issue 16, 1985. Over-estimating the capabilities of AI for the Strategic Defense Initiative.

catless.ncl.ac.uk/Risks/9.05.html#subj2.1 — DARPA contract: use AI to select targets during nuclear war, Jonathan Jacky, Risks Digest Volume 9, Issue 5, 1989.

catless.ncl.ac.uk/Risks — Risks home page.

 

Death-Dealing Neural-Net Helicopter

A piece in Defense Review for 28th February this year describes an experimental neural-net controlled helicopter manufactured by Neural Robotics Incorporated. The standard version of the AutoCopter is equipped with a neural-network fly-by-wire controller, so that it can be remotely guided by someone with no flying experience. The experimental version has another feature; one that Defense Review calls "transformational" and a "paradigm shift in lethality and force multiplication". A 12-gauge Auto Assault-12 Full-Auto Shotgun.

The Auto Assault-12 takes many kinds of ammunition. For example, you might load it with Number 4 Hevi-Shot. This is powerful stuff: when I looked it up on the Web, Guns & Ammo's article Hevi Hitter enthused that it will "fold ducks, geese and turkeys with authority at ranges we never before thought possible". Equally potent when employed in AutoCopter, it will deliver 3,500 projectiles on target(s): in 4 seconds, if I correctly understand Defense Review. Should you upgrade to Number 6 shot, you "can accurately unload approx. 5,000 projectiles on the target(s), and kill those targets out to a distance of approx. 67 yards". And should you upgrade even further to high-explosive FRAG-12 rounds, you can punch them "through a standard vehicle's skin, and explode inside the vehicle, releasing 90 ball projectiles at very high velocity in all directions, shredding the occupants".

The FRAG-12 round can be used also, continues Defense Review, "to engage targets inside buildings". To shred people inside buildings.

Links

edgeofvision.com/2006/03/02/flying-robot-armed-with-shotgun/ — The Flying robot armed with shotgun posting in Neil Halelamien's Edge of Vision blog, from which I found AutoCopter.

www.neural-robotics.com/ — Neural Robotics. The first few times I tried my browser on this and on other Neural Robotics links, it asked me for a user name and password. I eventually managed to see the page after happening to turn my computer off for an hour; I don't know why the earlier attempts failed.

www.neural-robotics.com/Product%20Data/AutoCopter%20Briefing%2007.28.05.pdf — AutoCopter Product Briefing. Does not mention the experimental gun-equipped version.

www.defensereview.com/article846.html — Exclusive Video: Unmanned Mini-Helicopter Gets 'Weaponized' with AA-12 Shotgun, by David Crane, Defense Review, 28th February, 2006. It says that a video of the helicopter can be downloaded by FTP as follows:
Do an FTP to www.neural-robotics.com. Give the user name autocopter and the password gunship when asked. Then download the file AutoCopter_Gunship.mpg. When I tried it by calling ftp from my ISP's Linux account, the download aborted each time with no data transferred. I couldn't follow the FTP link from my browser: it told me no anonymous access was allowed.

www.gunsandammomag.com/ammunition/hevi_hitter/ — Hevi Hitter, by Ralph Lermayer, Guns & Ammo.

www.uweb.engr.washington.edu/education/engtoolchest/Ethics2.pdf — Ethics -- Part II, by Buddy Ratner, University of Washington. Following on from Ethics Plain & Simple! at www.uweb.engr.washington.edu/education/engtoolchest/Ethics1.pdf, these slides explain how to view engineering ethics as an optimisation problem.

www.aaai.org/aitopics/html/ethics.html — AAAI page on ethics and social implications of AI.

Past newsletters are available at either www.ddj.com or www.ainewsletter.com. As ever, interesting links and ideas for future issues are very welcome.

Until next month,
Jocelyn <popx@j-paine.org>

For questions about the www.ainewsletter.com site, contact Dennis Merritt

Copyright ©2005 Amzi! inc., CMP, and Jocelyn Paine. All Rights Reserved

Copyright ©2002-04 Amzi! inc. and CMP. All Rights Reserved.