School of Computer Science PGR Seminar Zipei Li and Ben Claydon

Zipei Li will present Combining LLM-Generated Pseudo-Landmarks and Symbolic Guidance for Difficult Planning Problems

Abstract: Classical planning faces a fundamental trade-off between computational efficiency and plan quality, particularly on difficult problems. While optimal planners may require excessive computational resources, satisficing planners can efficiently find solutions but often produce unnecessarily long plans. Large Language Models (LLMs) offer an alternative source of planning guidance, their ability to generate reliable guidance towards high-quality plans remains limited.
In this work, we combine LLM-generated intermediate states, which we call pseudo-landmarks, with classical planning to improve plan quality on difficult problems. Rather than relying on LLMs to generate complete action sequences, our approach uses them to identify promising intermediate states that guide classical planners through smaller subproblems. We further introduce symbolic mechanisms to validate, evaluate, and iteratively refine these intermediate states, to reduce unnecessary search effort and planning detours.
Our initial experiments on difficult Blocks World instances demonstrate that this approach can substantially improve plan quality compared to satisficing planning, while requiring significantly less computation than optimal planning.

Ben Claydon will present Improving Locality-Sensitivity Based Similarity Search

Abstract: Our context of interest is the approximate k-nearest neighbours problem posed over a large collection of high-dimensional Euclidean vectors, in particular those derived as embeddings from deep learning networks. It is important that algorithms which solve this problem are both fast and accurate. One classical approach to this problem is the use of locality-sensitive hashing (LSH) functions. In recent years, LSH-based algorithms have fallen out of fashion in favour of other classes of algorithm, particularly graph-based approaches, due to the observation that they achieve high-quality results in very little time.

In this talk, I will discuss how LSH-based approaches may be improved using some novel geometric insights. I will also present the results of the SISAP Challenge, to which we submitted an algorithm which incorporates these ideas. The SISAP Challenge sees international teams attempt to engineer algorithms which search standardised datasets as quickly as possible. We found our LSH-based solution to be competitive with some graph-based approaches submitted by other teams, a surprising and encouraging result.