Knowledge Representation

Logic supplies rules of valid inference. Knowledge representation decides what the symbols mean, which distinctions matter, and how facts change. A technically valid representation may still be useless if it omits time, confuses unknown with false, or encodes the wrong level of detail.

Design Goals

A representation should support:

• the questions an agent must answer;
• the actions it must choose;
• efficient inference;
• revision when the world changes;
• explanations and provenance;
• interoperability with other data.

No representation is neutral. Choosing a category boundary or relation determines which conclusions become easy, difficult, or impossible.

Representation Levels

The same domain can be described at several levels. A delivery system might store raw coordinates, named locations, connectivity relations, or high-level facts such as PackageAtDepot. More detail is not automatically better. It increases storage and inference cost and may expose distinctions the task never uses.

A useful representation preserves distinctions that can change an answer or action while hiding irrelevant detail. This is the same principle of abstraction used in search:

• objects identify entities that persist;
• properties describe their current attributes;
• relations connect entities;
• events describe occurrences at a time;
• actions describe controlled changes;
• constraints rule out invalid worlds.

Before choosing a formalism, write the questions it must answer. A room-allocation model needs capacity, availability, and equipment. It probably does not need wall color. If accessibility later becomes a requirement, the representation must evolve because the decision boundary has changed.

World Assumptions

Under the closed-world assumption, anything not known true is treated as false. This is practical for a complete local database.

Under the open-world assumption, missing information remains unknown. Public knowledge graphs and medical records often need this interpretation.

If an allergy is absent from a record, concluding “no allergy” may be unsafe. Systems should represent at least true, false, and unknown when incompleteness matters.

Classical reasoning is also monotonic: adding facts cannot retract an earlier conclusion. Everyday rules often have exceptions:

Bird(x) → NormallyFlies(x)
Penguin(x) → ¬Flies(x)

Default and non-monotonic reasoning allow tentative conclusions to be withdrawn.

Ontologies

An ontology defines:

• classes;
• instances;
• relations;
• property constraints;
• subclass structure.

Example:

LabCourse ⊆ Course
hasInstructor(Course, Person)
requiresRoom(ProjectCourse, Studio)

Ontologies create a shared vocabulary and allow inherited facts. If every project course is a course and every course has credit, a project course inherits that expectation.

Overly broad hierarchies create false inheritance. “TeachingAssistant is a Student” may be true institutionally but insufficient for permissions, employment, or assessment rules.

Semantic Alignment

Two datasets can use the same word differently or different words for the same concept. course, for example, may mean a catalog definition, one scheduled offering, or one student’s enrollment. Combining them without alignment creates plausible but false joins.

Alignment requires explicit mappings:

• equivalence between concepts;
• broader or narrower relationships;
• unit and datatype conversion;
• identity rules for entities;
• treatment of missing and conflicting values.

Identifiers are not semantics. Matching two records by name can merge different people; assigning separate identifiers can duplicate one person. Identity resolution should retain evidence and allow uncertain or contested matches.

Interoperability also depends on constraints. If one source permits multiple instructors while another stores one column, conversion may lose information even when labels align.

Knowledge Graphs

A knowledge graph stores facts as relationships:

(ArtificialIntelligence, hasTopic, AStar)
(AStar, isA, InformedSearch)
(InformedSearch, isA, SearchMethod)

Graph queries can discover multi-step relations. Provenance should accompany facts:

claim, source, observed_at, confidence, valid_until

Without provenance, conflicting values cannot be audited. A graph is structured knowledge, not automatically trustworthy knowledge.

Time and Change

A fact may be true now, true during an interval, or true only at a recorded observation time. Storing teaches(Person, Course) without a term silently turns a temporary assignment into a permanent claim.

Common temporal patterns include:

valid_during(claim, start, end)
observed_at(claim, time)
holds_at(fact, time)
before(event_a, event_b)

Event-based models store changes and reconstruct state; snapshot models store the state at selected times. Events preserve history but make current-state queries more involved. Snapshots make current queries easy but duplicate data and can obscure why a value changed.

Conflicts also need policy. A system may prefer the newest observation, the most authoritative source, or the claim with stronger evidence. Such a policy should remain explicit rather than being hidden inside insertion order.

Action Models

Planning represents an action using preconditions and effects:

Action: move(robot, from, to)
Preconditions:
    At(robot, from)
    Connected(from, to)
Add:
    At(robot, to)
Delete:
    At(robot, from)

Applicable actions generate successor states, so symbolic planning becomes search over logical descriptions.

The frame problem asks how to represent everything that does not change. Add/delete lists handle this operationally: facts persist unless an effect changes them.

Planning Choices

Forward planning begins at the initial state and applies legal actions. Backward planning begins with goals and asks which actions could establish them.

Forward search knows the current state precisely but may explore irrelevant actions. Backward search stays goal-directed but must reason about interactions among subgoals.

Planning heuristics often relax delete effects. If achievements can never be undone, the relaxed problem is easier and its solution can guide the real search.

Planning differs from ordinary route search mainly in representation. Search nodes are symbolic world states, while operators are action schemas that can apply to many objects. Grounding every schema in advance can create a huge action set, so practical planners generate relevant instances selectively.

Planning Example

The following planner represents a state as an immutable set of true propositions. A grounded action has positive preconditions, add effects, and delete effects. Breadth-first search then finds a plan with the fewest actions.

from collections import deque

def applicable(action, state):
    return action["requires"].issubset(state)

def apply_action(action, state):
    if not applicable(action, state):
        raise ValueError(action["name"] + " is not applicable")

    new_state = state.copy()
    new_state.difference_update(action["deletes"])
    new_state.update(action["adds"])
    return new_state

def state_key(state):
    return tuple(sorted(state))

def breadth_first_plan(initial, goal, actions):
    frontier = deque([(initial, [])])
    discovered = {state_key(initial)}

    while frontier:
        state, plan = frontier.popleft()
        if goal.issubset(state):
            return plan

        for action in actions:
            if not applicable(action, state):
                continue
            successor = apply_action(action, state)
            key = state_key(successor)
            if key in discovered:
                continue
            discovered.add(key)
            frontier.append((
                successor,
                plan + [action["name"]],
            ))

    return None

ACTIONS = [
    {
        "name": "move workshop to hall",
        "requires": {"robot_at_lab"},
        "adds": {"robot_at_hall"},
        "deletes": {"robot_at_lab"},
    },
    {
        "name": "pick package",
        "requires": {"robot_at_lab", "package_at_lab"},
        "adds": {"carrying_package"},
        "deletes": {"package_at_lab"},
    },
    {
        "name": "deliver package",
        "requires": {"robot_at_hall", "carrying_package"},
        "adds": {"package_at_hall"},
        "deletes": {"carrying_package"},
    },
]

plan = breadth_first_plan(
    initial={"robot_at_lab", "package_at_lab"},
    goal={"package_at_hall"},
    actions=ACTIONS,
)
assert plan == [
    "pick package",
    "move workshop to hall",
    "deliver package",
]

The action list is grounded: it names specific locations and one package. A schema-based planner would define move(robot, from, to) once and instantiate it with objects satisfying type and connectivity constraints.

The model also illustrates delete effects. Moving removes the old location, and picking removes the package from the workshop. Omitting either deletion creates impossible worlds in which one object occupies two locations.

Diagnosis Example

Suppose:

Connected(sensor, controller)
Powered(controller)
¬Reading(sensor)

A rule might infer SuspectSensor(sensor). That is a hypothesis, not proof of cause. A broken cable or software fault may produce the same observation.

A stronger system can:

1. represent multiple hypotheses;
2. attach probabilities;
3. choose a test that distinguishes them;
4. record the evidence supporting each conclusion.

This shows how symbolic and probabilistic representations complement one another.

Hybrid Systems

Learned perception can convert images or text into symbols; symbolic rules can enforce constraints; probabilistic models can represent uncertain recognition. Hybrid designs are useful when neither pure rules nor pure statistical prediction provides sufficient control.

The interface matters. A learned label should not be inserted as certain fact when its confidence is low.

Representation Tests

Knowledge bases need tests just as programs do:

• competency tests: required queries return expected answers;
• consistency tests: prohibited combinations are not simultaneously accepted;
• coverage tests: every required class and relation has a definition;
• provenance tests: externally supplied claims retain source and time;
• change tests: updates retract or invalidate dependent conclusions;
• round-trip tests: imported and exported data preserve intended meaning.

For action models, test every operator’s preconditions, positive effects, negative effects, and invariants. A plan reaching the goal is not sufficient if intermediate states violate constraints the representation forgot to encode.

Ontology tests should include counterexamples. If TeachingAssistant inherits permissions from both Student and Employee, verify the combination is intended rather than merely checking that inheritance works mechanically.

Common Mistakes

• Treating unknown as false.
• Omitting provenance.
• Confusing a class with an instance.
• Representing unnecessary detail while omitting decision-critical facts.
• Modelling actions without delete effects.
• Building an ontology before defining required queries.
• Assuming a graph relation is causal.
• Allowing stale facts to remain timeless.

Exercises

1. Design an ontology for courses, sections, rooms, and instructors.
2. Add provenance and validity dates to five knowledge-graph claims.
3. Model pickup and delivery actions with preconditions and effects.
4. Compare forward and backward planning on a simple delivery task.
5. Give a rule requiring non-monotonic revision.
6. Design a hybrid diagnosis system combining rules and probabilities.
7. Represent a changing course assignment using both snapshots and events.
8. List the competency questions that should guide a library ontology.
9. Extend the planner with return travel and a second package.
10. Add a state invariant and reject actions that violate it.