An Year in ResearchPublished on March 22, 2017.
July, 24th 2015 was a hot and sunny summer day, perfect to go to the beach or have a trip to the mountains. But that day I had other plans: I was graduating. After returning back from the six months period in Spain a year back, finishing the last round of exams was hard and stressing, leaving less time and energy than I wished to focus on the thesis, but now I was ready to end the last part of my life at university. Excepting that, as I already knew, it was not going to be the end of anything, but the start of something new.
I have had in mind to do a Ph.D. for some years. The idea was born mainly because of my interest in mathematical aspects of Computer Science, which has grown relatively late in my life. I wanted to learn more, and this was the only way to achieve my goal. My love for Science in general also played a role: I wanted to actually do some Science, even if in very little parts, not just learn about it. Then I was accepted at the Ph.D. program in my own university, and everything started to look real: I was going to start this adventure! At the beginning I knew nothing about how research looked like, and I knew nothing about how my research had to look like. Now, a year later, I know nothing + ε, so I can try to share this ε with you.
So what are you doing exactly?
I’m sure explaining one’s own research topic is a tough task for anybody, but it is more so for a Ph.D. student in computer science. Everybody knows what medicine is for, or what engineers do, even if they might know nothing about the disciplines. But theoretical computer scientists, well, they just don’t exist in people’s mind. I’m going to explain in a few words what I did and what I’m going to do in the next two years, but I don’t know who you are. You might be my supervisor, or my grandmother, so I’ll try being clear enough without too much words. If you are reading, though, I assume you’re interested, so if you don’t get something, then do me one favor: ask me to explain.
Planning my research
Being into my second year, I can already tell you what my Ph.D. thesis will approximately be about: a theoretical study of logical expressiveness and computational complexity of Automated Planning languages and problems. Planning is a classical topic in that part of AI research dealing with automated reasoning (rather than learning, the other part of AI that is recently gaining all the glories). The aim is to design systems able to reach a given goal, as independently as possible, given a description, as general as possible, of what they can possibly do. If it seems too general to you, it’s because it is. The problem is exactly that of being able to perform tasks as diverse as possible with a reasoning process as general as possible. This generality, and flexibility, means the problem in its general terms can be very hard: the easiest variants are PSPACE-complete. Despite the theoretical complexity, planning systems have been very successful in practice, being able to handle huge problems. The technology is used everywhere, from managing airports to handling logistics, from industrial robotics to management space operations.
A planner typically expects as input a description of its environment, and of how it can interact with it, i.e., what are the admissible actions that can be performed to operate inside this environment. The second part of the input is the goal, i.e., what we want it to do. The output can be, depending on the problem, a list of actions to perform to obtain the goal, or a more generic recipe that also explains how to react to the environment, that often can be a priori unpredictable. The input the planner expects has, of course, to be expressed in some syntax, a domain description language, and as it turns out, the choice of this language has profound effects on the problem itself. The language has to be flexible enough to allow you to express all the details that are needed to model your problem, but constrained enough for the problem to be solved in a reasonable amount of time. The trade-off between expressiveness and computational complexity is a classical topic in computational logic: every time you increase the expressiveness of your language you have to pay for it in terms of how difficult it is to deal with it. This can go to the extremes, since if you add too much, the problem may become too complex or even undecidable, while if you constrain it too much, you won’t be able to model and solve real-world problems.
So here it comes my Ph.D. thesis: trying to settle some questions about expressiveness and computational complexity of a certain class of planning problems known as timeline-based planning problems. Basically, common planning languages reason about what a single executor can do. Toggle that switch, lift that load, move that piece, switch on the engine, etc. They are quite imperative in style, even if expressed very declaratively. In contrast, timeline-based planners reason about the whole system as a set of components, modelling them separately, and then compose their behavior with a set of temporal constraints that describe how the components interact with each other. This paradigm is more compositional, and allows us to model more easily domains where a lot of different components have to interact. Moreover, timelines can be flexible, meaning that they can represent uncertainty in the behavior of your components, e.g., imagine that you know that you can go from \(A\) to \(B\), but you cannot know precisely how much time it will require. You can also model uncontrollable components: parts of the system that are not under your control, maybe because part of the environment itself. All these features are very convenient in highly unpredictable environments, and it is not a coincidence that timeline-based planners have been successfully used in practice for easy tasks like space missions.
So what can I do about it? Despite a lot of success in practice, the theoretical side of the equation is less developed than for more common, action-based languages. Little is known, for timeline-based planning, on the theoretical issues I told you above. So I spent my first year trying to understand the framework and then identify some key questions that still need to be answered: what is the computational complexity of the problem in its generality? How much expressive is it really, compared with other approaches? In other words, is this only syntactic sugar or there really is more under the hood (tl;dr: yes, there is)? What is the logical counterpart of the problem? That is, we know classical planning is equivalent to satisfiability checking of Linear Temporal Logic formulas: what is the logic that captures timelines instead? Potentially interesting questions are many, and I doubt to be able to finish everything in the next two years. The first results are two papers, one just accepted to ICAPS, that show that a very constrained version of the problem is already very hard, i.e. EXPSPACE-complete, and that a certain class of action-based planning languages can be expressed through timeline-based problems in a compact way (and the converse is not true).
How did I come to work on this stuff? Who knows me knows that I always loved the theoretical aspects of Computer Science, but that I didn’t have these topics in mind until very recently, so what happened? As unlikely as it may seem, everything started in Spain. During my Erasmus period in Valencia, in 2014, I took some courses about Artificial Intelligence, specifically Neural Networks and Machine Learning. It was a really cool topic, and when I returned to Udine I tried to link it to everything I was doing. So as it often happens, by chance, I asked the right question to the right people. In that period, prof. Mark Reynolds from the UWA was visiting Udine to give a course about Temporal Logics, as part of the Automatic Systems Verification course held by prof. Angelo Montanari. I always liked a lot logics and automata, and I was enjoying the course very much, but that year in my head was the year of AI, so I asked what, in hindsight, must have felt like a very naive question: are there any links between these topics and AI? Of course there are! I was pointed to a paper by, among others, Marta Cialdea Mayer, from the University of Roma Tre, and Andrea Orlandini, from the italian National Research Council, which showed the encoding of classical planning into LTL that I mentioned before. This was the starting point for my master thesis, of which Marta and Andrea were co-supervisors. This experience turned into a fruitful collaboration that continues today with our joint work on timeline-based planning – we worked together on both the papers above – which is one of their core expertise area.
The 2014 visit of Mark Reynolds was also the opportunity to know about one of his recent works, on a new tableau-based procedure for checking the satisfiability of Linear Temporal Logic formulas. It was a new way of solving a problem that was already been studied for a long time, which seemed very promising. A colleague of mine, Matteo Bertello, as the exam for that course, worked on implementing it in C++, creating a tool he called Leviathan, and he spent little less than a year doing an amazing job optimizing it for performance. By when he finished, I was just starting my Ph.D., and we managed to publish the results in a joint paper where I handled the experimental evaluation of the performance of the tool and the writing of the actual manuscript. That was basically my first published paper (I had a previous publication, but without being involved in writing), and considering I had been there for only three months, it was a very good start. Publishing it also implied a very nice side effect, that I will tell you later. Even if tableau-based systems for LTL do not belong to my main research topic, it’s a very interesting one. Recently, a year later, Mark Reynolds returned visiting us again, and we managed to submit a second paper, which has just been accepted to LPAR-21, and to collect material for at least two more. Starting as a side project, the work on this topic has become a relevant part of my research activity.
Side projects without side effects
Talking about side projects, you know I cannot reason on only one thing at the time, so I’ve been busy doing a lot of things in the meantime, fact that also caused some troubles. Last year I went to Meeting C++ to give a talk about Functional Programming in C++. I know, I promised a follow-up post a year and a half ago. Please be patient. Still talking about C++, a mention goes to our C++ User Group Udine, which is now three years old. We had a meeting in December and it was great, with nearly forty people and great guests giving talks. Somehow I managed to find time to handle the logistics of that meeting, and I’m quite proud of our group.
Still talking about functional programming, at the beginning of the year I was also involved in a side project that allowed me to learn a lot about the internals of GHC, the Glasgow Haskell Compiler. The project involved the STM library, a popular concurrency library that implements Software Transactional Memory in Haskell, and resulted into the bachelor thesis of a talented friend of mine, Valentino Picotti, also an active member of the C++ User Group. What is the STM? Using this library, you can run concurrent code inside transactions with guarantees that resemble those provided by database systems: atomicity, consistency, isolation, and durability (commonly called ACID guarantees). In practice, this means that instead of having to lock some synchronization primitive before accessing a shared variable, you can just enclose your mutating code inside a
atomically block, and let the runtime do the dirty job:
Here, the atomicity guarantees that the code inside the
do block is executed either entirely or not at all, while isolation ensures that no other concurrent transaction can see the effects of this code until it has committed in turn. This is really convenient as you can write concurrent code in a very natural way without worrying about locks or race conditions. A colleague of mine, Marco Peressotti, worked on a generalization of this paradigm, which allows the use of open transactions. This means that, dropping the isolation guarantee, the execution of a transaction may be influenced by mutations to variables done by other committed transactions. This basically allows two concurrent transactions to communicate, thus avoiding the use of IO actions to coordinate the operations of different transactions.
Marco did all the theoretical work, formally defining the semantics of the new system. The project, then, consisted in the implementation of this idea. The first step in this direction was to understand in details how the STM worked, in order to borrow as many ideas as possible without reinventing the wheel. However, it was not feasible to hack on GHC directly without a lot of experience, so we decided to implement a separate library, that would have been inevitably slower but easier to design and suitable to be a realistic proof of concept. I helped in the design phase, and Valentino did a great job with the implementation, which had to be written in C because of the low level interaction with the Haskell runtime. The library still have to be polished, and we plan to finalize the work sooner or later, maybe for some future Haskell Symposium. In the meantime, the incredible amount of things learned in the process was well worth the effort.
A whole new world
One of the best benefits of being part of the academic world, especially in the Computer Science community, is the great amount of opportunities to travel around the world. In fact, last year, from June to September, I’ve been at home for maybe no more than three weeks in total.
Science and The City
The paper on the implementation of Reynolds’ tableau was published at IJCAI, the International Joint Conference on Artificial Intelligence, which in 2016 was held in New York City. This is one of the biggest conferences in this area and participating to it was an exciting experience, which was also very useful as an opportunity to meet and discuss about our research with a lot of other people. The poster session, in particular, was extremely productive. But as professional as I may have been, I cannot hide that the biggest feature of the conference was its location. This was my first trip outside Europe, and can be regarded as one of the most intense and interesting trips of my life. New York City is simply astonishing. The famous jungle of skyscrapers is familiar to anyone who has seen at least a couple of Hollywood movies, but the feeling of walking through Times Square or in Central Park is that of being literally inside those movies. The urban landscape of NYC simply feels unique, similar to a natural landscape shaped by a natural phenomenon of some kind, as if the clouds were designed together with the skyscrapers to reflect on the glass-made walls of other skyscrapers. But it is at sunset that New York gives its best. The city has been deliberately built on a straight grid: you have Avenues going North/South, and Streets going East/West, perpendicularly all through the Manhattan Island. This means that staying in the middle of a Street you can see all through the other side of the island, and at sunset this combines with the sun setting near the horizon in a uniquely beautiful scene. When I took the picture you see here (click to see the entire album on Flikr), I were one among at least other ten people taking pictures of the same landscape, one even with a full tripod set up in the middle of the zebras. The cultural landscape seemed at least as interesting as the urban one, from the typical Broadway musicals to the many and important art museums (that, fortunately, I managed to visit). Unfortunately, ten days busy at conferences are not enough to live the city in all its edges, but are sufficient to get a taste of it.
Of course, such a complex city also has a price: the rhythm is really chaotic, the traffic is terrible (air quality? what’s that?), and the cost of living is absurdly high. I paid $139 per night for an ugly two star bed & breakfast (only bad with no breakfast, actually). I can’t really imagine living there for an extended period (unless I were rich enough to get a Central Park-facing attic), but I can definitely understand what makes New Yorkers so proud of their city. They feel to be part of something great.
School’s out for summer
I hope Alice Cooper won’t take it personally, but sometimes one has to go to school during summer, too. Indeed, no survey of my summer journeys would be complete without mentioning ESSLLI 2016, the 28th European Summer School in Logic, Language and Information: two intense weeks of courses on transversal disciplines ranging from computational logic, to natural language semantics, to philosophy. Located in the wonderful dolomitic landscapes of Bolzano, this summer school was a really formative experience. The courses were interesting and held by internationally recognized experts in their fields, but among all of them, one was enlightening: Social Choice Theory for Logicians. Eric Pacuit is a very talented lecturer, and, most importantly, his lectures constantly transmitted his passion for what he does. I’ve had heard of Arrow’s theorem1 before, but I was barely aware of the existence of Social Choice Theory as a field, before attending this course. After, I wished to switch my research topic. Well, maybe I’m exaggerating a bit, but he definitely got everybody’s attention.
Besides the interesting courses, the most important attractive of ESSLLI is probably the cross-fertilization between different disciplines. Among the students attending were computer scientists, logicians, linguists, engineers, and even philosophers, coming from all around the world, from China to Uruguay. In this way, I’ve learnt things that I would have not come to know otherwise. Did you know many linguists commonly use lambda calculus to modeling natural language semantics? Neither did I.
In October I went to Copenhagen to present our first paper on the expressiveness of timeline-based planning problems at TIME 2016, the 23rd International Symposium on Temporal Representation and Reasoning. TIME is a small but well-known conference which aims to let experts of very different disciplines meet each other, under a common denominator, which is temporal reasoning. The conference is interested in temporal reasoning motivated by or applied to a broad variety of fields, ranging from AI to logic, to formal verification, to databases. It fits perfectly the kind of work that I’m doing, and it was the perfect venue where to start presenting my research.
But this conference in particular had an important emotional meaning to me. In 2014, when I was still a master student, I attended TIME 2014, held in Verona, invited by prof. Montanari, who sponsored the trip. That was a very troubling period for me, after returning from Spain, having to catch up with the exams, to work at the thesis, and, most importantly, to chose what to do next. TIME 2014 were the first time I attended an academic conference, and was a very enlightening experience. Two years later, I were at TIME 2016, presenting the first little steps of my own research, feeling like I was closing the circle in some way. Time flies, and this feeling remembered me why mine was spent well. It was a very little step, all considered, but it was worth all the effort. A thing is sure: I would not have been able to do anything without the support of many special people: my family, my friends, but especially my girlfriend: to stand any battle, even the smallest one, we all need someone to fight for.
While I was starting writing this post, I thought to have just a few thing to say, just to realize later how many things can be done in a single year. For instance, I didn’t even mention other two conferences and another summer school that I attended, but this post already grew too long. Maybe, instead of waiting an entire year to find time to write up something, I will be able to come to this blog more often, as originally intended. Maybe ;)