Current and Future Challenges in Knowledge Representation and Reasoning

In this invited talk I give a brief, and selective history of KR, starting with Aristotle and focusing mostly on work between 1950 and 2000. I talk about Newell’s Knowledge Level, the Physical Symbol Hypothesis and early theorem provers, and key advances such as the resolution rule of inference which then led to Prolog and also Datalog. I talk about Frames, and the “scruffy vs neat” debate in the 1970s. I mention the rise of description logics, the semantic web, constraint reasoning and the origins of non monotonic logic. I discuss the representation of particular kinds of knowledge, including taxonomic knowledge and qualitative representation and reasoning methods focusing on spatial knowledge. Finally I note the founding of KR Inc in 1993 and the series of very successful KR conferences it has run since 1989.

In this talk, I give a brief account of the history of KR, which however is done in a selective manner and in a subjective perspective in which some developments and results are cherry-picked. The presentation will go by decades, covering the time from the beginnings of AI in the 1950s up to the late decade, even if this view is not well-suited as there are overlaps and interesting developments may start or end a bit earlier, and similarly done or start a bit later. Special emphasis is given to the KR conference and the co-development of other venues and communities such as for logic programming, constraint satisfaction, and planning. The talk ends with a status-quo assessment and an outlook on future challenges.

KR was central to early work on AI, e.g., at the famous Dartmouth Conference, where several of the well-known protagonists made important contributions to KR. Expert systems, a subsequent high-profile development in AI, is also closely linked to KR. Although there have been ups and downs in the intervening years, we now have practical KR systems that are used in important applications, particularly in bio-health. An interesting recent (ish) phenomenon is the development of large-scale knowledge graphs (KGs) such as the Google KG. Such KGs are now pervasive in search, e-commerce, and personal assistants (Alexa, Siri, etc.). This success has encouraged the development of general-purpose KG systems and these are now being successfully applied in areas such as industrial design and configuration. So why are KR systems “suddenly” so successful? At least in part due to (i) increasing processing power; (ii) advances in theory and algorithms; (iii) availability of data and digitisation. Of course, many challenges remain, not least knowledge creation and curation – these are still hard problems!

Machine Learning (ML) has grown massively in the last 10 years or so, predominantly due to increased processing power availability, big data, and powerful statistical and probabilistic models. ML is predominantly data-driven these days, with the ambition to automate reasoning as a vector, rather than a manipulator. In this talk, I have expressed the role that KR may have in ML, as well as (to a lower extent) the role that ML may have to KR. I have identified the need for ML to be verified and explained, so as to identify any artifacts and biases that may be present in ML models. KR can (and does) play an important role to support ML. Also, KR can contribute to ‘hybrid ML models, integrating reasoning components with statistical/neural ML, as in inductive logic programming. KR-based verification/explanation methods and hybrid systems are all examples of how KR can support ML. On the other hand, ML can help KR with knowledge elicitation (e.g. for argumentation or knowledge graphs). Overall, ML is an important area of AI research and the KR community can gain lots from joining forces with the ML community.

An Information System (IS) is an integration of components for collecting, storing, and processing data, where the data is used to provide information and contribute to knowledge and digital products that facilitate decision making. This definition illustrates that the key elements that an IS has to deal with are data, knowledge, and processes operating over them. These are exactly the elements Knowledge Representation and Reasoning (KRR) has been concerned with, by studying semantic and computational aspects, developing techniques, and building tools. In this presentation we start by providing a brief overview of the main formalisms, techniques, and tools that have been proposed in KRR (notably, based on lightweight Description Logics) to address static and structural aspects of data and knowledge as they are encountered in ISs. We then move to dynamic and temporal aspects, which are related to the evolution and change over time of data and knowledge due to processes that operate over them. We discuss proposals and results on the integrated modeling and reasoning over data, knowledge, and processes, which is a major concern in ISs. We conclude by presenting some challenges that this poses for KRR.

While KR was central to building autonomous robots initially, as demonstrated by the robot Shakey in the late sixties, the field diverged, and KR techniques have started to play a role starting in the late nineties, with good examples being the museum tour guides Rhino and Minerva. One of the most addressed KR frameworks for robots is the KnowRob system developed by Tenorth and Beetz, combining rich ontologies with specialized reasoning. Planning techniques also play a major role, starting with domain-dependent planners like IxTeT and TAL, and later, domain-independent planners like FF and TFD, followed by a combination of action programming languages like Golog and PDDL planners, task and motion planners as well as conditional planners. Task planning needs to be complemented by action execution and maintenance. For the diagnosis of failures model-based techniques with strong KR foundations have been developed. After touching on these issues, my talk ended by proposing the Robocup Logistic League, where a team of robots needs to dynamically assemble products with the help of machines, as a rich benchmark for research in KR and robotics.

Uncertainty arises in many applications: it may come from incomplete information in games like Poker (or other adversarial scenarios), in the presence of random events (like dice rolls), and is a result of extracting information from text, images, audio, video. KR has early on recognized the need of dealing with uncertainty and proposed a range of solutions to various problems. In my talk, I survey the most important concepts that have been identified during the last 40 years (of course the choice is highly subjective): possible world semantics, probabilities, independence, graphical models, updates, and probabilistic and epistemic logic.

Knowledge plays a vital role in modern companies and organizations, be it in production, storage, or workforce management. Most crucial is the knowledge needed to accomplish creative processes, such as designing a product, an assembly line, a shift schedule or timetable, or planning a trip, routing vehicles, or diagnosing remote systems. All of these tasks involve taking knowledgeable decisions while respecting constraints and preferences. Answer Set Programming (ASP) has become a popular approach for modeling and solving such knowledge-intense combinatorial (optimization) problems. What makes ASP attractive is its combination of a declarative modeling language with highly effective solving engines. This allows us to concentrate on specifying – rather than programming the algorithm for solving – a problem at hand. The talk highlighted some current research topics, and concluded with an outlook on the ASP’s potential impact as a knowledge-driven AI tool.

Three systems with a clear KR&R component were presented: (1) A two-armed Blocksworld problem-solving robot with a high-level, symbolic (re-)planning component connected to a low-level robotic controller. (2) An interactive artwork with a BDI-based high-level agent programming component connected to a unity-based controller for virtual characters interacting with human users. (3) A general game-playing system that understands logic-based rule descriptions of new games and uses a propositional logic interface for reasoning connected to a neural network that, with the help of Monte Carlo tree search, learns to play any new game without human intervention.

Participants were divided in four different groups to discuss possible updates of the call for papers of KRR. Each group had 45 minutes to discuss between themselves and their conclusions were shared afterwards. The main points elicited were:

(i)

Title of the conference: participants discussed the possibility of updating the conference title (e.g., replacing it by the more general “The international conference on knowledge representation and reasoning”). However, changing the name also has disadvantages since information might be lost (on google search engine, for example). An alternative is to keep the current official name and add the “new title” as a subtitle (as done by other conferences).

(ii)

Definition of what KRR is: participants agreed that the main text introducing KRR needs updates. Some updates discussed at the Workshop have already been implemented in the Call for Papers for KR 2023.

(iii)

Topics of interest: there are too many topics listed. An alternative is to elicit about 10 topics and add examples of subtopics (e.g. KRR and cognition (e.g. cognitive systems, cognitive reasoning…)). Just hiding all subtopics, however, might not be a good idea since less knowledgeable authors might not understand that their work does not fit the conference.

The working group emphasized that there were few submissions to KR and robotics 2022, there being only one paper accepted. The discussion on how it can be improved elicited a few alternatives: (i) besides a special track, introduce a workshop or summer school on the topic; (ii) inclusion of short papers; (iii) linking to a recently created European conference that integrates KR and robotics. Overall, the three main challenges identified by the participants were the following: (1) continuously learning about the world that is changing, i.e. the need for the identification of what KR issues are raised for a robot that works for long periods of time (not just setting a table, but a whole day task, for example); (ii) cognition: learn from demonstration, exchange information and knowledge given by human or available in ontologies; (iii) multi-agent path finding: a complete representation of everything going on robot to understand why they fail is necessary; there is still a lack of good solutions for this problem.

The participants of the work group agreed that KR is based on a sound foundational footing, but that many foundational questions remain open. An example that was mentioned is the case of a particular form of non-monotonic reasoning known as “rational closure” (or system Z). The question was raised whether this form of reasoning can really be described as rational. One possibility that was mooted is that of collaboration with psychologists to help with analyzing these theories. The participants also discussed the issue that, although there are many success stories of foundational KR being turned into applications, more ought to be done when it comes to being sufficiently successful with solving real-world problems. In summary, three main challenges were identified: (i) obtaining more precise models of different types of knowledge; (ii) the well-known bottleneck on knowledge acquisition; (iii) differentiating quantitative approaches to reasoning from qualitative approaches.

The working group identified three concrete challenges within KR and information systems: (1) high-level descriptions and abstractions of dynamic data-centric systems and processes, and reasoning about them; (2) support for more comprehensive data management tasks in knowledge-enriched systems, such as analytical queries (numeric values, aggregation), updates, security and privacy, customization, and efficient system design; (3) better collaboration with communities like KGs, the semantic Web, and graph DBs. In particular, it is necessary to be aware and understand the standards of these communities so that we can leverage them to (a) make our techniques readily usable in practice, (b) identify and address their research challenges, and (c) increase the confidence in our solutions in different contexts. Regarding success stories in the field, we can highlight data integration (although several challenges still remain) and ontologies in biomedical domains. Medical ontologies are purpose-specific and hard to reuse, making it challenging their use in practice. One typically needs to extract some “relevant” knowledge, combine ontologies, match terms from different sources, etc., and the tools for such tasks are still underdeveloped. We lack easy-to-use tools that would allow developers to quickly use the existing knowledge. When it comes to processes with data, there are some theoretical results on temporal verification of dynamic data-centric systems, but still far from what is needed in practice. An example is the existence of a model-checker based on SMT, which still plays with toy examples, far from being deployed into real-world business processes. There are also some open challenges regarding privacy and security of information systems, namely (i) confidentiality: keeping the information secure and private (existing approaches are not secure and have many vulnerabilities); (ii) integrity: KBs should be correct (who inserts it? Is it trusted? Did I manage my ontology?); and (iii) availability: the KB should be reliable and not easy to crash.

Obtaining formalized knowledge is seen as a challenge that was discussed in this working group. The participants identified three main challenges regarding knowledge acquisition: (i) learning: it is possible to learn axioms, for example, but it still presents high uncertainty, (ii) maintenance: there are methods to develop ontologies, but not to maintain them, (iii) reasoning on (medical) guidelines, extracting and reasoning on rules is still challenging. Regarding success from last 5 years, the participants highlight: (i) a long running competition, (ii) learned graphs, (iii) availability of huge knowledge bases (fact bases, including certain levels of taxonomy), (iv) wide use of Protege, which offers a plugin architecture with successful built-in reasoners. Protege is not restricted to only the last 5 years, but it is still strongly relevant for the community.

The participants discussed major trends and challenges in description logic research. For instance,

(i)

Ontology-based data access has been a major research topic in description logic over the past 15 years. The development of novel and efficient query answering algorithms has been an important achievement. There are now powerful implemented tools for ontology-based data access that are used in various applications. Meaningful benchmarking for query answering remains an important challenge.

(ii)

A comprehensive study of the complexity of query answering is another highlight. This includes novel alternative approaches to complexity such as non-uniform and parametrized complexity.

(iii)

Making description logics nonmonotonic has been a major research topic with contributions ranging from the development of defeasible description logics to applying circumscription to description logics. Developing tool support remains a major challenge.

(iv)

The development of support for ontology engineering has been another major area of research. Principled approaches to explanation, forgetting, repairing, modularity, and versioning have been suggested and investigated. Tools have been developed for some of these approaches.

(v)

Explanation of entailments, abduction, and provenance have also been investigated in depth, with significant development of tool support in particular for explanation.

(vi)

The close link between description logics and datalog/existential rules has triggered fruitful interaction with the database community; with results and techniques being transferred in both directions.

(vii)

Temporal description logics have been investigated in depth over the past 20 years. Here implemented systems are still missing.

(viii)

Inconsistency handling in ontology-based data access has been a major research area, again with significant interaction with the database community.

(xii)

Adding features for handling uncertain knowledge to description logics has a long history and many approaches have been proposed and investigated. Tool support is still limited.

(xi)

Areas that have recently attracted attention but in which challenging problems remain include description logic and learning, description logic and knowledge graphs, security and privacy of description logic ontologies.

Participants discussed current trends and challenges regarding reasoning about action. Several trends were identified, including:

(i)

epistemic planning

(ii)

generalized planning

(iii)

controller synthesis (e.g. using LTL, LTLf , timed automata, situation calculus)

(iv)

expressive action logics with uncertainty, including regression and progression reasoning, and verification of belief programs

(v)

ontologies for robots

(vi)

causality

(vii)

goal reasoning

(viii)

learning action representations, and

(ix)

KR techniques for informed reinforcement learning.

As well, various challenges were identified, including

(i)

solvers for epistemic planners (the problem is undecidable in general)

(ii)

learning representations of actions, affordances, and game rules from data

(iii)

rational reconstruction of implemented KR systems for robots, like KnowRob, and

(iv)

connections between KR work on causality and machine learning.

Participants discussed alternatives to attract new talents to the community. Launching tangible practical challenges (e.g. angry birds, robotics), as done by other communities, is an alternative that would catch the attention of students. However, it was also highlighted that the process to attract new students must start early, with undergraduate students. It was identified that students might be interested in the field, but they do not have the necessary background. This way, it is important that universities keep elective courses on symbolic reasoning, for example. In alternative, providing high quality online material would support this lack of background. Finally, the participants discussed the creation of very short videos, possibly with testimonials, to motivate new students.

The group identified that the KR community is underrepresented in 3 important regions: North America, China, and southern Asia. Organising workshops addressing relevant KR topics (e.g. knowledge graphs) in North America could contribute to the promotion of the field in this area. Regarding China, participants identified that there are not many submissions from this area as KR is not ranked as a top conference there. The possibility of contacting acquaintances in China to discuss this issue and try an application for a re-ranking was considered. Finally, the participants agreed that to promote KR in southern Asia members of the KR community could offer to give tutorials and guest lectures in the area. Such tutorials and lectures would also be an opportunity to establish new collaborations in KR with researchers in the region.

The group discussed several kinds of events differing from the standard format of the KR conference. Four recommendations are proposed.

First, we propose to reconsider holding KR every second year as an online event (either fully online or hybrid). Instead of simply copying the on-site format and having a one-week online event, we propose a series of sessions. This is inspired from successful recent experiences with thematic groups (e.g. the Online Social Choice and Welfare Seminar Series, https://www.sites.google.com/view/2021onlinescwseminars), projects (e.g. the EU TAILOR project), local groups advertising their online seminars (e.g. the LUCI Lunch Seminar Series, https://luci.unimi.it/events/), and national seminars (e.g. the French KR seminar, https://www.gdria.fr/seminaire/). Among the pros of this suggestion are: (i) no travel costs; (ii) good for the planet; (iii) it favors participation from developing countries, (iv) it is easier to attract people from adjacent fields such as roboticists (similar to colocation with another conference), and (v) talks can be recorded easily and cheaply. Among the cons, we list: (i) people from the KR field favor of on-site conferences; (ii) choosing the slot(s) will be problematic: there are several solutions but none is optimal, the merits of each of them should be weighed carefully; (iii) it may become apparent that there is too much heterogeneity in our field, e.g. only argumentation people attend argumentation sessions.

Second, we should try to establish benchmark and system competitions in areas where this makes sense. We might take inspiration from the NSF-funded StarExec platform (https://www.starexec.org/starexec/public/about.jsp) for first-order SAT solvers or the ICLP Prolog Programming Contests (https://people.cs.kuleuven.be/~bart.demoen
/PrologProgrammingContests/Contest99.html).

Third, we propose to get more involved in summer schools such as: (i) ESSLLI (https://2022.esslli.eu/), (ii) NASSLLI (https://ml-la.github.io/nasslli2022/), (iii) the EurAI ACAI Summer School (eurai.org/acai), and (iv) the Reasoning Web Summer School (reasoningweb.org). Beyond KR people individually submitting courses, KR Inc. may propose to sponsor 2 or 3 courses.

Finally, KR Inc. might support tutorials and other small events such as schools in underrepresented countries in order to attract locals; local attendance can be expected to go beyond the KR field.

The panel session started with a presentation of results from a survey with 24 participants to identify key challenges, areas of increasing and decreasing importance in knowledge representation and reasoning and topics to which participants plan to make contributions. As key successes the participants identified existing industry-strength applications, in particular in the areas of answer set programming, description logics and ontologies, and knowledge graphs. In the following discussion it became clear that applications use KR techniques, but this use is often not very visible. In order to make KR applications more visible, a journal special issue on applications was proposed as well as special tracks with instructions to reviewers as to how applications papers are to be reviewed were identified. A topic that is seen as very important is the area of hybrid AI, i.e., combining knowledge and learning-based methods. While progress in this direction is seen, this is an area that needs significant attention in the future to which at least some of the seminar participants want to contribute. To support this kind of interdisciplinary work, more tutorials and invited talks from the machine learning community can be incorporated into conferences and (summer) schools. Progress in this area was identified as crucial in order for KR to stay relevant as an area, while it was also clear that KR techniques have clear potential to advance intelligent systems, e.g., in terms of explainability or interpretability and when it comes to integrate existing knowledge. Finally, reaching out to neighboring areas is seen as very important as well as to actively showcase the KR successes and work on the still open challenges that so far hinder a wider adoption of KR techniques such as handling uncertainty or inconsistencies.