Okay, well it looks like you've done the obvious first thing: you've more-or-less broken out every if clause as a subroutine call. So your structure of logical tests may be a mess, but all they do is decide which sub to call.

A minor readability hint: drop the leading "&" on sub calls. It's gone out of style, unless you want the old-fashion calling semantics that automatically passes through @_.

As for cleaning up the logical tests, I don't know what to suggest except that you should write an extensive series of automated tests (e.g. using Test::More and friends) so then you can try experimental refactoring and know immediately if you've broken something.

(By the way, there is a AI::Prolog module, so you can do Prolog type stuff from within perl. Could be fun to play with, though I'm not sure it's ready for "production use".)