Exploiting structure in AI languages
Just as we use language to communicate with each other, we also use language to communicate with machines. However unlike natural languages, machine-oriented communication is fixed, formal, and generally inflexible—typically designed to favour computational properties ("computer understandability") over expressivity ("human understandability"). This is a necessary evil—it's easier to train a human to understand a (provably) hard language than to teach the computer. Making it easier for one side makes it harder for the other.
Yet this need not always be the case—many languages used by the artificial intelligence community have features that can be exploited to improve both human fluency and computer execution speed. My research identifies several such opportunities with case studies from the Game Description Language, Agent Logic Programs, and the Situation Calculus.
Game Description Language is a spartan language able to describe any game. It provides a small set of game-related constructs and three time points (initially, now, next). The rest is plain logic programming, so axiomatisers must invent structures within the language in order to describe the complexities of arbitrary game rules. Further, common structures (such as graphs, sequences, orders, numbers, turns) often look the same across different games from different authors. By identifying the common "design patterns" we can teach automatic systems to understand rules in the way humans do, facilitating deeper analysis of rules, semantic "grammar" checkers, and dynamically optimised reasoners.
Agent Logic Programs are a concise, declarative language for specifying cognitive robotics control strategies. They also allow a clear separation from the domain axiomatisation, which can be replaced with any action language or calculus, subject to a few small requirements. Contrast this with Golog (tied to Situation Calculus) and Flux (tied to Fluent Calculus).
We convert Agent Logic Programs to the native input language of the new reactive answer set solver oClingo. While oClingo's format is more powerful, it offers features typically unnecessary for cognitive robotics descriptions, and is further encumbered by semantic restrictions which are hard to check. By uniting these two technologies we simultaneously provide a new implementation to Agent Logic Programs and make oClingo easier to use.
Situation Calculus is one of the oldest and most mature action calculi. Several special classes of Basic Action Theory have long been known, including the (poorly named) "context free" and the "literal-based" classes. While the logical expressivity of these classes has also been discussed, the computational complexity has been ignored. By viewing situations as words, we can examine what types of language each of these classes can recognise from an automata perspective.