Logical Approaches to Dynamical Structures in AI

Imagine that you must get from your home near Valby station to your office at DTU near Lyngby station. In order to get to your destination, you need to choose a route from your current location.

You might choose to take the H train from Valby station to Østerport station, and from there change to the A train to Lyngby station as you believe that is the fastest route.

We can use mathematics to represent this scenario as a graph where the above scenario is illustrated in the figure. Each train line connecting two train station represents the agent’s – in our case your - interaction with its environment in order to get from Valby station to Lyngby station.

However, the train system is known to be prone to delays and cancellations, and just as you arrive at Østerport station, you discover that the A train is cancelled. You are stuck.

How do you find an alternative route to Lyngby? Is it possible to get to your destination at all?

Alternatively, as you reach Østerport station, a new express train Ax allows you to reach you destination faster and you might find it reasonable to update your original knowledge of how to reach Lyngby station.

Our initial scenario has now become a dynamic environment, something which we can model with a dynamic graph. We can reflect these changes by adding more possible train lines or train stations in the case where new connections are made in the train system or by deleting existing train lines or stations in case of cancellations or a train station being shut down.

The agent can act – choose a to take a certain train line going from train station A to train station B, as well as it can learn about the structure environment – which train stations are risky to change trains at. Such properties can be formalized using logic, namely dynamic logic which can either look at environment from an external or internal viewpoint. Using this, the agent can learn about the structure of the environment, represented as a graph.

This is a simple example of how (artificial) agents can behave in a dynamic situation, where the goal to reach your destination can be seen as a strategic interaction between the agent and the train system. The agent must choose a strategy to get to their destination without getting stuck. Hence, the agent must reason about what train stations are saftest to change at, such that they always have at least one alternative route. This can be formalized using logics for instance: Modal Sabotage logic. Modal Sabotage logic is one of several logics that describes how AI can handle dynamic situations, where you want to reason from an internal point of view of the network - the current train station you are at. Analogously, reasoning for change of the agent’s knowledge can be modelled in a similar way.

To represent such dynamic situations, dynamic networks or graphs are very useful, as this data structure provides a wide range of algorithms to solve problems such as the connectivity problem mentioned in our example.

The overall aim of this research project is to study the relation between dynamic graphs and dynamic logic such that agent can learn in a previously unknown environment, exploiting complexity results from the dynamic graphs and the variety of dynamic logics that can describe different types of dynamics.