Project Proposition for IFT702

July 2004

Eric Beaudry and Xu Yi

Task planner and scheduler for MARIE / EMIB

Introduction

This project can be viewed as a subproject of my research project for my Master.

My master project consist to integrate a planning feature for a robot (U2S) developed at LABORIUS, a laboratory at Computer and Electric Engineering faculty of University of Sherbrooke. One of goals of this robot is to participate to the AAAI Challenge, an informal competition at the AAAI conferences. Originally, LABORIUS projected to participate this year (July 2004), but it was not possible for some reasons. Next participation will be summer 2005. Recently, another event was added to U2D agenda : participate at a scientific exposition in Sherbrooke (september 2004). For both events, and probably more others events, a requirement is to have a planner at high-level task.

AAAI Challenge

This challenge is to produce a robot that can participate to a scientific conference. The robot have to be autonomous and no teleoperation is permitted. The basic tasks that the robot have to do are :

to register himself as a participant

find the appropriate place
exchange information

to give a small technical presentation

find the room where to present
arrive on time at room
do the presentation

to accomplish some volunteer tasks

ex : bring an object to a room
ex : keeping a room

"Schmoozing"

navigate randomly and talk with others attendees

Scientific Exposition at Sherbrooke

This event is more simple that AAAI challenge and can be done without planning. But, we can imagine some scenarios for the robot in a typic scientific exposition...

Tasks profile

Time dependent

Ex : presentation must be done at 14:00
Ex : battery has some max lifetime

Many modalities (or strategies) to achieve tasks

Ex: navigation task can be done by

metric map
topologic graph
follow someone by vision tracking
driving instruction (turn left 90deg, go ahead 20m, turn right, ...)

Uncertainty

Navigation failed
AAAI registration : nobody at registration office, we must try later
Dynamic environment change

Ideas

An idea that we can explore is combining temporal consideration with a some limited uncertainty.

The part "temporal consideration" can be achieved by running a partial order planner (plan space search, GraphPlan) and in second pass, applying the result to a scheduler with time constrains... (see Chapter 13 to 14 in the book)

The part "uncertainty" can be achieved by using a non-deterministic planner like SimPlan (see chapter 16). Non-deterministic planning for robotics does not seem to be mature. Sample of applications that is see are very limited.

I have never seem project that try to combine non-deterministic and time scheduling. I think that there are some interesting thing to try. For example, in the AAAI challenge, we want that the robot can do registration by himself. To the registration, robot can follow some guidelines like : "find line-up of persons waiting for registration, follow the last person by vision tracking, when arrive a first place goto registration desk". But, we can expect failure. If the time permits, we want that the robot try another registration strategy by himself... but the planner must evaluate the worst case. For example, if we anticipate that a failure may compromise future task with time constraints, we may want that the robot try the safer method even if it's not 100% autonomous (ask for help)...

So the policy of the robot can be :

try by yourself at first
at failure, retry with minimal help
in worst cases, when time schedule can be broken, ask for help to obtain max chance of success

It's seems to be a big project. We have to talk with Pr. Kabanza... We have to expect to find some limitation to reduce the project complexity...

References

EMIB : Computational architecture for robotics with artificial emotion developed by F. Michaud, UdeS/Computer Engineering (PDF)

MARIE : Mobile and Autonomous Robotic Integration environment (web site)

Book : Automated Planning