Knowledge Representation Issues & AI Solutions

TAKEAWAYS:

• Knowledge representation issues include ambiguity, scalability, and inefficiency in reasoning, which can be mitigated by structured formats like semantic networks or ontologies.
• Heuristic search (e.g., A*) outperforms uninformed search (e.g., BFS/DFS) by using domain-specific knowledge to prune search spaces, but requires careful heuristic design to avoid suboptimal paths.
• Semantic networks visually model relationships (e.g., "is-a" hierarchies) but struggle with complex constraints, while frames organize knowledge into slots and default values for efficiency.
• Ontologies provide formal, shared vocabularies (e.g., for medical diagnoses or eSewa’s citizen-service categories) but demand high maintenance for evolving domains.
• Real-world applications: A* optimizes Pathao’s ride-matching routes, semantic networks power Ncell’s customer-service chatbots, and ontologies standardize NEPSE’s stock-trading rules.
• Exam focus: Compare search algorithms, solve constraint problems (e.g., N-Queens), and justify solutions to representation issues with examples.

1. Knowledge Representation Issues

Knowledge representation (KR) is the cornerstone of AI, but real-world systems face critical challenges:

A. Core Issues

1. Ambiguity and Uncertainty

   • Problem: Natural language (e.g., "The bank loan was denied because the applicant was poor") is inherently ambiguous. Is "poor" a financial term or a moral judgment? KR systems must disambiguate context.
   • Example: In eSewa, a user’s query "My bill is high" could refer to electricity, water, or internet. The system must infer intent from user history or semantic links.
   • Visual:

     graph LR
       A["User Query: 'Bill is high'"] --> B["Electricity Bill"]
       A --> C["Water Bill"]
       A --> D["Internet Bill"]
       B --> E["Check eSewa history"]
       C --> F["Check NTC records"]
       D --> G["Check Ncell portal"]

2. Scalability

   • Problem: Representing knowledge for large domains (e.g., medical diagnoses or Daraz’s inventory) becomes computationally infeasible with naive methods like propositional logic.
   • Example: Ncell’s network routing must represent millions of base stations and user devices. A flat KR system would collapse under the data load.

3. Inefficient Reasoning

   • Problem: Some KR formats (e.g., predicate logic) force brute-force searches, slowing down applications like real-time fraud detection in banks.
   • Example: Khalti’s transaction verification must quickly validate user identities. A slow KR system could enable fraud.

4. Dynamic Knowledge

   • Problem: Real-world knowledge evolves (e.g., traffic rules in Kathmandu change annually). Static KR systems become obsolete.
   • Example: Pathao’s surge pricing relies on real-time demand data. A KR system must update dynamically.

5. Interoperability

   • Problem: Different AI systems (e.g., NTC’s grid management vs. NEPSE’s trading) use incompatible KR formats, hindering integration.
   • Example: Smart city projects in Nepal require seamless data exchange between traffic (KTMMC), energy (NTC), and transport (Pathao) systems.

B. Solutions to KR Issues

2. Search Techniques Revisited: Heuristics in Action

To solve KR issues, AI often combines search techniques with domain knowledge. Compare:

A. Uninformed vs. Informed Search

B. Heuristic Functions: How They Work

A heuristic $h(n)$ estimates the cost from node $n$ to the goal. For A*: $$f(n)=g(n)+h(n)$$

• $g(n)$: Cost from start to $n$
• $h(n)$: Heuristic estimate to goal

Example: Pathao’s Ride-Matching

• State: Current driver locations, passenger pickup/drop points.
• Operators: Assign driver → passenger, update routes.
• Heuristic: $h(n)=\text{Manhattan distance}$ (approximate travel time).
• Goal: Minimize total ride time.

graph TD
  A["Start: Driver at A, Passenger at P"] -->|"h(A)=5"| B["Assign Driver 1"]
  B -->|"g(B)=3"| C["Driver moves to P"]
  C -->|"h(C)=2"| D["Passenger reaches D"]
  D["Goal: Total cost = 5"]

Trace for A vs. Greedy*: Assume grid coordinates (start at (0,0), goal at (4,4)) and heuristic $h(n)=\text{Manhattan distance}$.

Greedy might take (0,0) → (4,0) → (4,4) (cost = 8), but A* finds the optimal path (diagonal) with cost = 8 (same here, but differs in complex grids).

3. Knowledge Representation Formats

A. Semantic Networks

• Definition: Directed graphs where nodes represent concepts and edges represent relationships (e.g., is-a, has-part).
• Example: Ncell’s Customer Service

  graph TD
    A["Customer"] -->|"is-a"| B["User"]
    B -->|"has"| C["Subscription"]
    C -->|"type"| D["Prepaid"]
    C -->|"type"| E["Postpaid"]
    D -->|"includes"| F["Data Plan"]
    E -->|"includes"| G["Roaming"]

• Pros: Intuitive, handles hierarchies well.
• Cons: Struggles with complex constraints (e.g., "if X then Y unless Z").

B. Frames

• Definition: Structured templates with slots (attributes) and default values.
• Example: Daraz’s Product Catalog

  classDiagram
    class Product {
      +name: String
      +price: Float
      +stock: Integer
      +category: String
      +is_available(): Boolean
    }
    class Electronics {
      +warranty: String
      +brand: String
    }
    Product <|-- Electronics

• Pros: Efficient for object-oriented data (e.g., inventory).
• Cons: Inflexible for non-hierarchical relationships.

C. Ontologies

• Definition: Formal, shared vocabularies with hierarchical relationships (e.g., OWL, RDF).
• Example: NEPSE’s Trading Rules
  • Stock is-a FinancialInstrument
  • Trade has-part Buyer and Seller
  • Buyer must-have DematAccount
• Pros: Enables interoperability (e.g., between banks and NEPSE).
• Cons: Requires expert curation.

4. Real-World Applications

A. A in Pathao’s Route Optimization*

• Problem: Match drivers to passengers in Kathmandu’s traffic (dynamic obstacles, tolls, one-way streets).
• Heuristic: $h(n)=\text{Estimated time}=\frac{\text{Distance}}{\text{Average speed}}+\text{Toll costs}$.
• Example Trace:
  1. State: Driver at Thapathali, passenger at Lakshmi Chowk.
  2. Heuristic: Avoids Ring Road (tolls) → suggests route via Putalisadak.
  3. Result: 12-minute ride vs. 18-minute toll-heavy path.

B. Semantic Networks in eSewa

• Problem: Disambiguate user queries like "My bill is pending."
• Solution: Links queries to:
  • Bill → Type (electricity/water/internet)
  • Status → Pending/Paid/Disputed
• Visual:

  graph TD
    A["User: 'Bill pending'"] --> B["Electricity Bill"]
    A --> C["Water Bill"]
    B --> D["Check NTC Portal"]
    C --> E["Check Kathmandu Uddyog Laghubitta"]

C. Frames in Daraz’s Inventory

• Problem: Track product attributes (e.g., size, color, stock).
• Solution: Frame for Electronics:

  classDiagram
    class Electronics {
      +name: String
      +price: Float
      +stock: Integer
      +category: String
      +specs: Map<String, String>
    }
    class Smartphone {
      +brand: String
      +ram: String
      +storage: String
    }
    Electronics <|-- Smartphone

• Example: A Smartphone frame auto-filters low-stock items for restock alerts.

D. Ontologies in NEPSE

• Problem: Standardize trading rules across brokers.
• Solution: OWL ontology defines:
  • Trade must have Buyer, Seller, Quantity, Price.
  • Buyer must have DematAccount with Balance > 0.
• Impact: Reduces fraud by enforcing rules uniformly.

5. Constraint Satisfaction with Heuristics

A. N-Queens Problem with Heuristic Search

Problem: Place 4 queens on a 4×4 board so no two attack each other. States: Board configurations. Operators: Place/remove a queen. Constraints:

1. No two queens share a row/column/diagonal.
2. Heuristic: $h(n)=\text{Number of attacking pairs}$.

Trace with A*:

1. Initial State: Empty board.
2. Place Queen at (0,0) → $h(n)=0$.
3. Place Queen at (1,2) → Check diagonals/columns.
4. Place Queen at (2,1) → Conflict with (0,0) diagonal.
   • Backtrack and try (1,3).
5. Place Queen at (3,0) → Valid solution.

graph TD
  A["Start"] --> B["(0,0)"] --> C["(1,2)"] --> D["(2,1) Conflict"]
  D --> E["Backtrack"] --> F["(1,3)"] --> G["(3,0) Solution"]

Real Analogy: Kathmandu Traffic Routes

• Queens = Vehicles at intersections.
• Constraints = No two vehicles block each other.
• Heuristic: Prioritize routes with least congestion (like A*’s $h(n)$).

6. Exam Tip: How to Score Full Marks

1. Compare Search Algorithms

   • Always show a table (like above) and a trace with small numbers (e.g., 4×4 grid).
   • Highlight why A is better: "A guarantees optimality if $h(n)$ is admissible, unlike greedy which may take suboptimal paths."

2. Solve Constraint Problems

   • For N-Queens or similar, list states, operators, and constraints explicitly.
   • Use a visual trace (like the Mermaid graph above) to show backtracking.

3. Knowledge Representation Issues

   • Name the issue (e.g., "ambiguity") and link to a real system (e.g., "eSewa’s query disambiguation").
   • Propose a solution with pros/cons (e.g., "semantic networks reduce ambiguity but require manual annotation").

4. Ontologies vs. Frames

   • Ontologies = Shared vocabularies (e.g., NEPSE’s trading rules).
   • Frames = Object templates (e.g., Daraz’s product catalog).
   • Contrast: "Frames are efficient for static data, while ontologies handle dynamic, interoperable domains."

5. Heuristic Design

   • For A*, explain why your heuristic is admissible (e.g., "Manhattan distance never overestimates actual path cost").
   • Example: In Pathao, "Toll costs are fixed and known in advance, so they can be added to $h(n)$ without overestimation."

Final Note: This unit tests your ability to connect theory to real systems. Always tie examples to Nepalese contexts (e.g., Ncell, Daraz, eSewa) and use visual traces for search problems. For ontologies, draw a small hierarchy; for frames, use a class diagram. Good luck!