The maPO Schema

Ontology Diagram

The maPO schema, illustrating the classes and properties for modeling the MAPF planning and conflict-resolution workflow.

The maPO extends the foundational concepts of the standard Planning Ontology (PO) to address the unique complexities of multi-agent scenarios. It creates a formal, queryable knowledge base that supports on-demand explainability. To ensure interoperability, maPO reuses concepts from established W3C and IEEE standards.

Core Components

• Agent and State Representation: Models each agent's identity, capabilities, and location at specific points in time. The ma:Agent class is defined as a subclass of both plan:ProblemObject and sosa:Platform to ground it as an entity capable of perception and action.
• Multi-Agent Plan Representation: Defines the hierarchy of a global ma:JointPlan composed of individual ma:AgentSubPlan instances. It distinguishes between the initial ma:OriginalSubPlan and any subsequent ma:ResolvedSubPlan generated after conflict resolution.
• Conflict and Resolution Modeling: Captures the entire lifecycle of a conflict, from a ma:CollisionEvent to a ma:ConflictAlert and the resulting ma:ReplanningStrategy. It uses the PROV Ontology (PROV-O) to create a traceable, auditable record of how and why a plan was revised, using properties like prov:wasDerivedFrom to link plan versions.

Ontologies Reused

To ground our ontology in established semantic standards and enhance interoperability, maPO reuses concepts from several widely adopted resources:

• SOSA/SSN: To model agents as platforms capable of sensing and acting.
• Provenance Ontology (PROV-O): To formally link original and revised plans, creating a traceable history of the planner's conflict resolution decisions.
• OWL-Time: To represent time instants and intervals for events, states, and path segments.
• CORA: To define agent capabilities in a structured manner.
• RDF Schema: To structure agent path sequences and other foundational data types.

Ontology Prefixes

Use Cases & Competency Questions

To ensure our ontology effectively supports explainability, its design was guided by a set of competency questions (CQs). These questions represent concrete explanatory needs an end-user would have when analyzing a multi-agent plan.

• C1: Which CollisionEvents (including their time, type, location, and involved agents) were detected during planning?
• C2: For a given CollisionEvent, which agent(s) received a ConflictAlert?
• C3: What was an agent's original, conflict-unaware plan, and how does it compare to its final, resolved plan?
• C4: Why did a specific agent have to wait or reroute in its final plan?
• C5: For a given ConflictAlert, which ReplanningStrategy did the agent use?
• C6: What was the cost change associated with a revised AgentSubPlan?
• C7: Why was a particular agent (from a set of conflicting agents) chosen to be the one to replan? (i.e., what was the planner's selectionRationale?)
• C8: What is the final JointPlan after all conflicts are resolved, and what is its overall makespan?

Below are key examples of how these questions are answered, along with the SPARQL queries and Natural Language templates used to generate the explanations.

SELECT ?conflict ?timestamp ?type 
  (GROUP_CONCAT(DISTINCT ?otherAgentName; separator=", ") as ?involvedAgents) 
  (GROUP_CONCAT(CONCAT("(", STR(?y), ",", STR(?x), ")"); separator=";") as ?locations) 
WHERE { 
  ?conflict a ma:CollisionEvent ; 
            ma:involvesAgentsEvent ma:agent-1, ?otherAgent ; 
            ma:occursAtTime/time:inXSDDateTimeStamp ?timestamp ; 
            ma:conflictTypeEvent ?type ; 
            ma:conflictLocation ?locNode . 
  ?locNode ma:xCoordinate ?x ; ma:yCoordinate ?y . 
  FILTER(?otherAgent != ma:agent-1) 
  BIND(STRAFTER(STR(?otherAgent), "#") AS ?otherAgentName) 
} GROUP BY ?conflict ?timestamp ?type ORDER BY ?timestamp

[Agent Name] was involved in these conflicts (highlighted on grid):
Time: [timestamp]
Type: [type]
Location: [locations]
With: [involvedAgents]

SELECT ?startTS ?endTS ?otherAgentName ?conflictTS ?x ?y 
WHERE { 
  ?resolvedPlan a ma:ResolvedSubPlan; ma:belongsToAgent ma:agent-1 . 
  FILTER EXISTS { ma:FinalJointPlan ma:composedOfSubPlans ?resolvedPlan . } 
  ?resolvedPlan ma:planData ?seg1, ?seg2 . 
  ?seg1 ma:hasPathSequence/rdf:rest*/rdf:first ?locNode . 
  ?seg1 ma:hasValidTime/time:hasBeginning/time:inXSDDateTimeStamp ?startTS . 
  ?seg2 ma:hasPathSequence/rdf:rest*/rdf:first ?locNode . 
  ?seg2 ma:hasValidTime/time:hasBeginning/time:inXSDDateTimeStamp ?endTS . 
  ?resolvedPlan ma:resolvesConflict ?conflict . 
  ?conflict ma:involvesAgentsEvent ?otherAgent ; 
            ma:occursAtTime/time:inXSDDateTimeStamp ?conflictTS ; 
            ma:conflictLocation ?locNode . 
  ?locNode ma:xCoordinate ?x ; ma:yCoordinate ?y . 
  FILTER(?otherAgent != ma:agent-1) 
  BIND(STRAFTER(STR(?otherAgent), "#") AS ?otherAgentName) 
}

[Agent Name] had to wait for a total of [Total Wait] second(s) in its final plan. 
This was necessary to avoid a planned conflict with [Other Agent Name] that would have occurred at ([X],[Y]) at T=[Conflict Time].

SELECT ?planType ?planCost ?timestamp ?x ?y ?rationale (GROUP_CONCAT(DISTINCT ?otherAgentName) AS ?otherAgents)
WHERE {
  BIND(ma:agent-1 AS ?agent)
  { 
    ?plan a ma:OriginalSubPlan ; ma:belongsToAgent ?agent .
    BIND("Original Plan" as ?planType) ...
  } UNION {
    ?plan a ma:ResolvedSubPlan ;
          ma:belongsToAgent ?agent ;
          ma:resolvesConflict ?conflict ;
          ma:generatedBy ?activity .
    ?activity prov:used/ma:triggeredBy/ma:selectionRationale ?rationale .
    ?conflict ma:occursAtTime/time:inXSDDateTimeStamp ?timestamp ;
              ma:conflictLocation ?locNode ;
              ma:involvesAgentsEvent ?otherAgent .
    ?locNode ma:xCoordinate ?x ; ma:yCoordinate ?y .
    FILTER (?otherAgent != ?agent)
    BIND("Resolved Plan" as ?planType)
    BIND(STRAFTER(STR(?otherAgent), "#") as ?otherAgentName)
  }
} GROUP BY ?plan ?planType ?planCost ?timestamp ?x ?y ?rationale ORDER BY ?timestamp

A conflict occurred at location [Locations]. To resolve the conflict with [Other Agent Name], [Replanning Agent Name] changed its plan. 
This changed the plan cost from [Original Cost] to [New Cost].
Rationale: Using a [Alert Type] strategy, [Rationale].

# Query for Global Makespan (C8)
SELECT ?makespan WHERE {
  ma:FinalJointPlan ma:hasGlobalMakespan ?makespan .
}

# Query for Per-Agent Final Cost (C6)
SELECT (STRAFTER(STR(?agent), "#") AS ?agentName) ?cost WHERE {
  ma:FinalJointPlan ma:composedOfSubPlans ?plan .
  ?plan ma:belongsToAgent ?agent ;
        ma:hasPlanCost ?cost .
}

Here is a summary of the final joint plan:
The overall makespan is [Makespan].
The sum of individual plan costs is [Sum of Costs].
To achieve this solution, a total of [Replan Count] replans were required.

Interactive Demo

Explore the capabilities of the maPO framework through our interactive dashboard. The demo allows you to upload a knowledge graph generated from a MAPF planner's trace and visually analyze the solution. You can step through the simulation, inspect conflicts, and ask natural language questions to generate real-time explanations.

Key Features

• Knowledge Graph Upload: Start by uploading a `.ttl` file containing the MAPF execution trace.
• Grid Simulation: Visualize the multi-agent plan on a grid, with agents, obstacles, and paths clearly marked.
• Time-Step Simulation: Use the slider to step through the plan execution and see agent movements over time.
• Explanation Panel: Click on agents or grid cells to ask context-specific questions, or choose from a list of general queries to understand the plan's global properties.
• SPARQL Query Interface: For advanced users, an integrated SPARQL editor allows you to run custom queries against the loaded knowledge graph.

Demo Video