TITLE: Exploiting subgraph structure in multiagent path planning

PRESENTER: Malcolm Ryan, http://malcolmr.web.cse.unsw.edu.au, malcolmr@cse.unsw.edu.au

AFFILIATION:http://www.cse.unsw.edu.au, Centre for Autonomous Systems, School of Computer Science & Engineering, University of New South Wales

DATE: Friday 22th September 2006

TIME: 12:00:00

PLACE: CSE Seminar Room, Level 1, K17

ABSTRACT:

Planning paths for multiple agents moving around a shared map is
computationally expensive. As each new agent is added the size of
the search space grows combinatorially and planning soon becomes
infeasible. Prioritisation is a common solution but it is not
complete - there are problems which it cannot solve.

In this talk I present a new approach which takes advantage of the
structure of the world to do planning more efficient. A map of the
planning domain is decomposed into subgraphs with particular
structures: stacks, halls, rings and cliques. These structures
dictate certain conditions on when agents can enter and leave the
subgraphs. Armed with this information, we can do planning at
the abstract level, moving robots from subgraph to subgraph rather
than from vertex to vertex, thus reducing the size of the search
space significantly, allowing us to solve much larger problems.

BIOGRAPHY OF SPEAKER:

Malcolm Ryan is a post-doctoral research associate with the Centre
for Autonomous Systems (CAS) at the University of New South Wales.
His past research has involved the amalgamation of reinforcement
learning and symbolic planning, and he's still trying to live it
down. His favorite colour is red and his favorite number is 3. He
is currently looking for a new place to live in the inner-west area.
Any offers?

Seminar information is also available at
http://www.cse.unsw.edu.au/db/ai/seminars/list/index.html

Host:

Seminar Convenor:

Van Hai Ho