Advanced Planning and Scheduling with Semantic Knowledge Graphs and LLMs

Nenad Petrovic, Milorad Tosic

University of Niš, Faculty of Electronic Engineering, Niš, Serbia

​

​

​

​

​

Objectives

​

• Provide experimental evidence about possible directions to more reliable, reasonable and responsible AI

​

• Improve usability of existing solution for enterprise planning & scheduling

​

• Explore value add of SKGs & LLMs in enterprise

​

Background: APS in Manufacturing

• Manufacturing operations in modern digital enterprise are becoming increasingly complex
• Advanced Planning and Scheduling (APS)
• Any computer program that uses advanced mathematical algorithms or logic to perform optimization or simulation on finite capacity scheduling
• Increasingly important in challenging Industry 4.0
• Recent advances in Artificial Intelligence (AI) offer a promising approach to improve business value generated by APS.

Background: AI application layers challenge

Background: AI application layers challenge

Approach

• Leverage ontology-driven APS solution
• Adopt Large Language Models (LLM) to reduce APS costs by starting from textual descriptions
• End-users do not necessarily need specific expert knowledge
• In this way, the high potential of adopting ontologies for implementation of the cognitive intelligence would be proven.

​

LLM

ontologies

APS

Proposed solution

• Different variations of context/prompt engineering techniques considered
• Focus on the so-called In-Context Learning (ICL) prompting strategy, where
• ontologies and
• KG segments as examples are embedded within a prompt.
• The main advantage of the approach is that pre-trained general LLMs can perform new tasks without requiring additional fine-tuning, which is time and resources intensive procedure.

​

Proposed solution

• Direct embedding of textual serialization of planning ontologies in the context is not practical due to large volume of data contained.
• huge costs resulting from token consumption
• hallucinations in the case when the context is arbitrarily cut.
• Additional strategy is needed for preprocessing of textual content of the target domain ontologies
• Retrieval Augmented Generated (RAG) method is adopted, particularly Retrieve and Re-Rank (RRR) process, when content of the set of ontologies is larger than the context of commonly used LLM solutions.

Implementation: Architecture

• User describes what is ordered together with related resources (such as machines and employees) as a freeform text.
• User-provided text {story} is leveraged as input to RRR

​

1,5-User input {story} 2a-RDF schema 2b-RDF knowledge graph 3a-Ontology chunks 3b-Knowledge graph excerpt chunks 4a-Context: ontology excerpt {context1} 4b-Context: knowledge graph template {context2} 6-Intermediary result 7-Triplets 8-Order definition 9-Generated work plan.

Implementation: Architecture

• As result of the RRR, the most relevant excerpts of the ontology collection based on the user description are extracted (4a-context1)

​

1,5-User input {story} 2a-RDF schema 2b-RDF knowledge graph 3a-Ontolgy chunks 3b-Knowledge graph excerpt chunks 4a-Context: ontology excerpt {context1} 4b-Context: knowledge graph template {context2} 6-Intermediary result 7-Triplets 8-Order definition 9-Generated work plan.

Implementation: Architecture

• A representative excerpt of knowledge graph is taken into account in order to ensure that LLM will hit the right terms without hallucinations (4b-context2)

​

1,5-User input {story} 2a-RDF schema 2b-RDF knowledge graph 3a-Ontolgy chunks 3b-Knowledge graph excerpt chunks 4a-Context: ontology excerpt {context1} 4b-Context: knowledge graph template {context2} 6-Intermediary result 7-Triplets 8-Order definition 9-Generated work plan.

Retrieve and Re-Rank for In-Context Learning (RRR4ICL) – Workflow overview

• Preprocessing
• transform input textual files into format suitable for next phases (such as splitting document into chunks).
• Retrieve
• Initial retrieval of a broad set of potentially relevant parts of text (chunks).
• Re-Rank
• Re-ranking to isolate the most relevant subset of chunks

​

RRR4ICL components - RecursiveSplitter

• The first phase is documents chnaking
• An existing library adopted for creation of document chunks:

https://python.langchain.com/api_reference/text_splitters/character/langchain_text_splitters.character.RecursiveCharacterTextSplitter.html

• “Syntax driven” chunking
• Splits by separators hierarchy;
• Keeps natural units together;
• Merges smaller chunks;
• Recursive splitting for large units;
• Final chunks are of varying length
• Parameters (based on empirical estimation)
• chunk_size - 600 characters

maximum number of characters or tokens allowed in a single chunk

• chunk_overlap - up to 200 characters

number of characters or tokens shared between consecutive chunks.

RRR4ICL components – SentenceTransformer

• The second phase begins with semantic search using the Bi-Encoder model
• Given a search query, a large set of potentially relevant text segments (or chunks) is generated by using dense retrieval
• SentenceTransformer -based Bi-Encoder is used.
• However, this method can sometimes return results that are only loosely related to the query.

RRR4ICL components – CrossEncoder

• The third phase : CrossEncoder evaluates and scores the relevance of each candidate segment more precisely.
• The final output is a ranked list of results optimized for relevance.
• The dense retrieval approach leverages semantic search, mapping both the query and documents into a shared vector space to retrieve the closest matches.

• This method surpasses traditional lexical search by recognizing synonyms, acronyms, and semantically similar terms.

RRR4ICL – Steps

• First, sentences and paragraphs are converted into 384-dimensional dense vectors (multi-qa-MiniLM-L6-cos-v1 model).
• Than, cross-encoder is applied to re-rank (ms-marco-MiniLM-L-6-v2 model).

RRR4ICL – Prompt templates used

• Prompt 1 - From text to planner inputs
• "Create set of RDF triplets for semantic knowledge graph in XML with respect to given ontologies: {context1 – ontology excerpt} and example graph {context2 – knowledge graph template} based on user story: {story}“
• Prompt 2 - Update of input knowledge graph
• "Update the given semantic knowledge graph {graph} based on the given user story: {story}"
• Prompt 3 - Planning assistant
• "Answer the question about ontology: {story}, based on given excerpt: {context1 – ontology excerpt}"

Deployment overview

• Planning-related components and semantic triple store
• Part of Tasor semantic planner infrastructure which is part of commercial solution.
• RRR approach models
• deployable on local server
• two language models used as bi-encoder and cross-encoder are not as large as text generation solutions.
• LLM service unifying RRR with prompting against GPT-4o
• local server, making use of Langchain library and Ollama for deployment of bi-encoder and cross-encoder models.
• Result generation and prompting
• GPT-4o which is a commercial solution and deployed on OpenAI’s cloud infrastructure.

1-HTTP request containing user story; 2-Prompt to GPT-4o; 3-Response of GPT-4o; 4-Triplet insertion; 5-Planning output; 6-HTTP response (created triplets/plan).

Development environment

• Python-based Flask API web service implementation
• Execution environment
• Laptop with Intel i5-10300H 2.50GHz CPU, 24GB of RAM and NVIDIA GTX1650 with 4GB of VRAM
• LangChain
• open-source framework whose aim is to aid developers build applications relying on LLMs in more effective and efficient manner, by providing set of tools and abstractions.
• Ollama
• open-source platform that enables running and management of LLMs directly on local machine
• Simplifies the deployment of open-source LLMs, allowing terminal and API iteration without relying on cloud services.

1-HTTP request containing user story; 2-Prompt to GPT-4o; 3-Response of GPT-4o; 4-Triplet insertion; 5-Planning output; 6-HTTP response (created triplets/plan).

API overview

Experiments and evaluation

• Two sets of user interaction experiments
• Text-based Planner input: User description->Knowledge base
• Question answering about Planner ontologies
• Three approach variants
• A1 - simpler solution leveraging only relevant parts of ontology as context
• A2 - incorporating example graph excerpts within the context
• A1’ - no RAG-extracted context

​

Experiment1: Text-based planner input

result - achieved accuracy, A1 - only relevant parts of ontology as context, A2 – with sample graph excerpts, A1’ - no RAG-extracted context, Y-yes, N-no, WS-wrong syntax, RAG - retrieval of context

Experiment1: Results’ accuracy estimation

• The ratio of correctly identified RDF resources (classes, properties and individuals) is taken into account
• Results based on average of 10 executions
• Correctness of generated triplets was evaluated based on human inspection of LLM outputs and their comparison to the triplets from Tasor Planner.
• Surplus RDF resources within output considered
• Do not exist in any of the production-related ontologies, resulting as outcome of LLM’s hallucination effect

​

Experiment1: Results discussion

• Approach with example graph excerpts within the context (A2) clearly outperforms the solution leveraging only relevant parts of ontology (A1).
• Hallucinations are usually avoided considering the fact that correct classes, relation and properties are present within the example graph.
• A1 in activity flow definition, as well as other more complex scenarios, is ineffective and prone to hallucinations.
• A2 requires more processing time, taking into account that RRR process will be executed twice and the length of the prompt is also increased.
• When it comes to graph update scenario, even the simpler approach A1’, which does not leverage RAG-extracted context, provides correct result.
• A1 has advantage of much shorter execution time (no RRR process invocation).

Experiment2: Questions about ontologies

• Based on prompt 3: Answer the question about ontology: {story}, based on given excerpt: {context1 – ontology excerpt}"

Experiment2: Results discussion

• The best performance is for attribute retrieval, while answering about relations is a bit more challenging.
• This phenomenon can be explained that attribute retrieval and direct relation identification are simpler case, considering the locality of information which is extracted from document and injected into context.
• However, relations in ontology, especially the indirect ones rely on information which is usually not stored inside the document close to each other.
• Conclusion: the proposed approach exhibits better results when contextual information is stored within the continuous region inside the document.

Conclusions and discussion

• Experimental evidence of potential of Retrieval Augmented Generation (RAG) for handling larger textual inputs containing semantic data.
• Symbolic and statistical paradigms of cognition should be considered as complementing.
• One possible practical implementation of synergy between symbolic and statistical paradigms of cognition is illustrated.

Future work

• More detailed comparison of semantic-driven planning solutions against the more traditional ones.
• Explore other strategies and additional steps required for adoption of smaller, locally deployable models
• Focused LLM-based extraction of raw triplets with respect to simplified ontology representation.
• More comprehensive evaluation of the proposed approach for other domains
• Consider additional aspects, such as relationships and value constraints.
• Improvements of individual components of the proposed RRR4ICL workflow:
• “Semantics driven” recursive chunking instead of currently used “syntax driven”

Thank you!

Questions?

​

Prof dr Milorad Tosic

milorad.tosic@elfak.ni.ac.rs

milorad.tosic@virtuonasoft.com

​