[Caml-list] Playing Soccer with OCaml

[Caml-list] Playing Soccer with OCaml

[Kai Kaminski]

Hi,

I'm currently taking part in a university project, which is about
teaching robots to play soccer. My task is the path-finding module. It
is responsible for finding short paths, while considering moving
obstacles (team mates, enemy robots and the ball). I will probably use
Dijkstra or Markov Decision Processes to accomplish this. Not because
I'm a great friend of these algos (in fact I don't know nothing about
them yet) but my lecturer told me that these were suitable. Since I
fell in love with OCaml some weeks ago, I am considering implementing
the module in OCaml. First, to improve my OCaml skills, and second to
show my colleagues the power of OCaml.

(* They are all JAVA people. When I tell them about functional
   languages they think I want to go back to Turbo Pascal :(
*)

Now there are several questions for me:
- I'm new to OCaml and functional programming. I have some experience
  with C/C++, Pascal and Asm. But I don't think that this will help
  me. Do you think it is possible for a newbie to implement such
  algorithms within five or six month in reasonably quality?

- We use CORBA for communication (omniORB). How difficult is it to
  communicate with C++ modules via CORBA. As I understand it, CamlIDL
  could help me here, but I'm not sure.

- Is OCaml fast enough? We need to do all the work for 4-6 robots on
  one linux machine (Intel at ~400MHz).

- Is OCaml a good choice to implement these algorithms? A better
  choice than C++ at least? (Ok, I know: OCaml is *always* the better
  choice ;-)

- What about SunOS? This port is not a requirement, but it would be
  nice.

- Any pointers on how to implement these algos in a functional
  language?

- Are there any other algos you would recommend?

Thanks in advance,
Kai Kaminski

PS: I'm not really a cs guy, I'm more involved with mathematics.
    Therefore abstraction doesn't make me cry. On the other hand, I've
    just started my second year at university...

PPS: If you are a native speaker please correct at least a few of my
     mistakes. But please remember the 5 MB limit on my mail server ;-)
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Playing Soccer with OCaml

[Alan Schmitt]

* Kai Kaminski (kok@wtal.de) wrote:
> Now there are several questions for me:
> - I'm new to OCaml and functional programming. I have some experience
>   with C/C++, Pascal and Asm. But I don't think that this will help
>   me. Do you think it is possible for a newbie to implement such
>   algorithms within five or six month in reasonably quality?
> 

Yes, definitely. And I think that any experience in programming will
help you.

> - We use CORBA for communication (omniORB). How difficult is it to
>   communicate with C++ modules via CORBA. As I understand it, CamlIDL
>   could help me here, but I'm not sure.
>

I'm not sure about using camlidl for that, I'll let Xavier answer it.
There was a project for writing bindings for Orbit in caml (the page is
at http://www.sf.net/projects/camlorb ), but we haven't done much on it
for quite a while ... (I was supposed to work on it, but other projects
beckoned ... you know how it goes ;-) If there is some goal to push us
forward with this project, it would be a good thing.

> - Is OCaml fast enough? We need to do all the work for 4-6 robots on
>   one linux machine (Intel at ~400MHz).
> 

Yes definitely, as caml can be compiled to native code on many
architectures.

> - Is OCaml a good choice to implement these algorithms? A better
>   choice than C++ at least? (Ok, I know: OCaml is *always* the better
>   choice ;-)
> 

You answered this one yourself ;-) More seriously, OCaml is great for
fast development (type inference helps a lot) and for complex data
structures.

> - What about SunOS? This port is not a requirement, but it would be
>   nice.
> 

From the Readme:
The other compiler generates high-performance native code for a number
of processors. Compilation takes longer and generates bigger code, but
the generated programs deliver excellent performance, while retaining
the moderate memory requirements of the bytecode compiler. The
native-code compiler currently runs on the following platforms:

    Intel Pentium processors: PCs under Linux, FreeBSD, NetBSD, OpenBSD,
      Windows, NextStep, Solaris 2, BeOS.
    Alpha processors: Digital/Compaq Alpha machines under
      Digital Unix/Compaq Tru64, Linux, NetBSD and OpenBSD.
    Sparc processors: Sun Sparc under SunOS 4.1, Solaris 2, NetBSD, Linux
    Mips processors: SGI workstations and mainframes under IRIX 6
    HP PA-RISC processors: HP 9000/700 under HPUX 10
    PowerPC processors: IBM RS6000 and PowerPC workstations under AIX 4.3,
                        PowerMacintosh under MkLinux, LinuxPPC, MacOS X
    Strong ARM processors: Corel Netwinder under Linux
    Intel IA64 processors: prototypes under Linux

Alan

--
The hacker: someone who figured things out and made something cool happen.
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Playing Soccer with OCaml

[Xavier Leroy]

> - We use CORBA for communication (omniORB). How difficult is it to
>   communicate with C++ modules via CORBA. As I understand it, CamlIDL
>   could help me here, but I'm not sure.

That might be the show-stopper.  There is currently no CORBA binding
for OCaml (although this has been on our to-do list for quite a while).

CamlIDL is a COM binding, and while COM and CORBA have several points
in common, they are sufficiently different that CamlIDL won't help you
much here.

There is always the possibility of generating C++ communication stubs
using omniORB, then connect the Caml code to these stubs by hand.
This is feasible for a small number of CORBA interfaces and methods,
but doesn't scale up.

> - What about SunOS? This port is not a requirement, but it would be
>   nice.

SunOS 5 (a.k.a. Solaris 2) is well supported and regularly tested.
OCaml used to run under SunOS 4 but hasn't been tested under this
environment in a while.

- Xavier Leroy
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Playing Soccer with OCaml

[Rafael 'Dido' Sevilla]

On Mon, Oct 29, 2001 at 06:39:00PM +0100, Kai Kaminski wrote:
> Hi,
> 
> I'm currently taking part in a university project, which is about
> teaching robots to play soccer. My task is the path-finding module. It
> is responsible for finding short paths, while considering moving
> obstacles (team mates, enemy robots and the ball). I will probably use
> Dijkstra or Markov Decision Processes to accomplish this. Not because
> I'm a great friend of these algos (in fact I don't know nothing about
> them yet) but my lecturer told me that these were suitable.

I have an idea for you if you're making such a system that should be an
approximation to an autonomous mobile robot (looks like it).  Maybe, as
opposed to doing the classical sense-model-plan-act (SMPA) paradigm of
robotics (as it looks like you're doing, as you're looking for
pathfinding algorithms) you can try doing research on the behavior-based
subsumption approach to robotic control, pioneered by Prof. Rod Brooks
at MIT.  The basic idea is that your robotic beings are controlled by
behaviors which run in parallel, which are activated by various sensory
inputs, and are prioritized in control of their actuators.  The seminal
paper that describes this approach is Rodney A. Brooks, "A Robust
Layered Control System for a Mobile Robot", MIT AI Lab Memo 864,
September 1985.  You can find an electronic version of this paper and
many more on the behavior-based approach at Brooks' home page 
at http://www.ai.mit.edu/people/brooks/.

In order to implement a subsumption architecture in OCaml you would
probably need to use the threads library to make one thread for each
behavior you wanted to make the robot perform, and two more threads to
get inputs from the robots sensors and arbitrate the access of behaviors
to the robot's actuators.

Which brings me to a somewhat related question: just how real-time is
OCaml's runtime environment?  Is the garbage collection algorithm
real-time, i.e. it uses its own thread to perform GC in parallel to
processing or uses some other technique which guarantees that every cons
performed has an upper bound on the amount of time it will take,
regardless of GC?  Most garbage collection algorithms I've seen are not
real-time, in that they can potentially take an unbounded amount of time
that depends on the number of allocated cells.  For robotics and other
real-time control and processing problems this is an important question.

-- 
Rafael R. Sevilla <sevillar@team.ph.inter.net>   +63(2)   8177746 ext. 8311
Programmer, Inter.Net Philippines                +63(917) 4458925
http://dido.engr.internet.org.ph/                OpenPGP Key ID: 0x5CDA17D8
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Playing Soccer with OCaml

[Axel Poigné]

Dear Rafael

> In order to implement a subsumption architecture in OCaml you would
> probably need to use the threads library to make one thread for each
> behavior you wanted to make the robot perform, and two more threads to
> get inputs from the robots sensors and arbitrate the access of behaviors
> to the robot's actuators.

Programming robots using threads is notoriously bad idea. More or less all
the robots I know of, and, in fact, the hard real time part of most embedded
systems are implemented using one execution loop only, "synchronously" to
use a more technical term. The loop works as follows: read the input
(sensor) data, compute the "state change" (decoupled from the environment),
write the output (actuator) data. The rationale is to obtain deterministic
behaviour of course depending on the input. Since input is somewhat "fuzzy",
in particular for autonomous robots with all kinds of sensors involved, one
at least wants to understand what the software does. In particular one wants
control behaviour to be reproducible. I believe that complex threading does
not necessarily contribute to these goals. To be explicit: I have seen a
couple of robocup robots just doing nothing because of a deadlock with
regard to threading.

Without wanting to raise a flame, I believe that ocaml is not particular
well suited to generate code of the characteristics described above.
Further, much of the power of ocaml is in the sophisticated structuring
mechanisms for data - that are quite useless in robotics where most data are
elementary, and must be: anything with a touch of recursion is devasting for
real-time applications, deadlines then depend on size of data.


Axel Poigne

PS. Though subsumption was an advancement more recent approaches try to fuse
behaviours in a more sophisticated way.

PPS This may considered as a reaction to the recent mail of A Joseph Koshy
as well

------------------------------------------------------------------------
Dipl.Ing. Dr.rer.nat. Axel Poigné       http://www.ais.fraunhofer.de/~ap
                                        mailto:poigne@ais.fraunhofer.de
Fraunhofer AiS                          Tel: (+) 2241 142440
Schloss Birlinghoven                    Fax: (+) 2241 142324
D-53754 Sankt Augustin
Germany 

------------------------------------------------------------------------
Have a look at our new language for designing Embedded Software

sE = Java + synchronous Languages  (http://www.ais.fraunhofer.de/~ap/sE)





-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Playing Soccer with OCaml

[Damien Doligez]

>From: "Rafael 'Dido' Sevilla" <sevillar@team.ph.inter.net>

>Which brings me to a somewhat related question: just how real-time is
>OCaml's runtime environment?

In short: it has pretty good latency characteristics, but no real-time
guarantees.


>  Is the garbage collection algorithm
>real-time, i.e. it uses its own thread to perform GC in parallel to
>processing or uses some other technique which guarantees that every cons
>performed has an upper bound on the amount of time it will take,
>regardless of GC?

Note that using a separate thread to perform GC in parallel does not
by itself guarantee real-time behaviour.


>  Most garbage collection algorithms I've seen are not
>real-time, in that they can potentially take an unbounded amount of time
>that depends on the number of allocated cells.

In a real-time GC system, the programmer gives a guarantee that the
program will never have more than a fixed amount (declared in advance)
of live data, and the system gives a bound on the time needed to
perform each allocation.  Note that this bound has to be quite low in
order to make the real-time guarantees meaningful.  The memory
management of Objective Caml has low latency almost all the time,
thanks to the incremental GC, but we do not give a guaranteed bound.
Going all the way to real-time behaviour would be doable (with a lot
of work), but it would incur a large overhead, which we are not ready
to impose on "normal" users (compilers and proof assistants).

That said, I have to add that the normal behaviour of Objective Caml
on modern machines should be good enough for interactive games.  But
if you try to run rocket control algorithms with O'Caml, don't blame
us if it fails.


>  For robotics and other
>real-time control and processing problems this is an important question.

That's right, but Objective Caml is mainly targetted at Unix systems,
which generally do not support real-time anyway.

-- Damien
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr