Date and time: 3:00pm-4:30pm, Wednesday 4th October, 2006
Venue: 300.217
Abstract: A new approach to the constrained shortest path problem (CSPP) is applied in the context of submarine path planning through a region of sonar detectors. This uses fast, convergent methods to find the optimal Lagrange multiplier and Dijkstra's algorithm to find initial solutions. On a test set of 120 cases, the resulting paths are almost always within 3% of optimal, with solution times under 1 second on a 2.4 GHz desktop computer. Given the performance of this method on problems with over 6400 nodes, extension to much larger problem sizes appears feasible.
About the speaker: Mark Grigoleit is a PhD candidate in the Department of Mathematics and Statistics, Curtin University of Technology.
Seminars are free and open to all postgraduate students in the Department of Computing and the Department of Mathematics and Statistics. No booking is necessary and biscuits, tea and coffee are provided. Seminars are as informal as the speaker desires. If you are not a postgraduate student and wish to attend a seminar you may only do so with the express permission of the relevant speaker(s).
If you are interested in giving a presentation in this seminar series, or to make suggestions for speakers, please contact Simon Puglisi (Computing): or Christina Burt (Maths):
the seminar co-ordinators. Seminars are normally held at 300.217 (building 300, level 2, room 217) - you can find where this is exactly using the Bentley campus map.
