Building a Distance-Finding Chatbot with AWS Services

In this project, we will build an intelligent chatbot that computes the shortest distance between two cities in a directed graph using AWS Lambda, API Gateway, DynamoDB, Cognito, and Lex. The graph is directed, and each edge has a weight of 1. We will store graph data in DynamoDB, retrieve it via Lex, and implement the A* algorithm to optimize pathfinding.

Step 1: Setting Up AWS Lambda and DynamoDB for Graph Storage

We'll begin by writing a Lambda function that takes a graph and stores it in DynamoDB. The graph will be represented as a series of directed edges, like "Chicago->Urbana,Urbana->Springfield,Chicago->Lafayette". Each edge signifies that there is a directed path between two cities.

import boto3
import json
from collections import defaultdict, deque
 
def bfs(graph, start):
    distances = {}
    queue = deque([(start, 0)])
    while queue:
        node, distance = queue.popleft()
        if node in distances:
            continue
        distances[node] = distance
        for neighbor in graph.get(node, []):
            queue.append((neighbor, distance + 1))
    return distances
 
def lambda_handler(event, context):
    dynamodb = boto3.resource('dynamodb')
    table = dynamodb.Table('mp3_db')
 
    graph_str = event['graph']
    edges = graph_str.split(',')
    graph = defaultdict(list)
    for edge in edges:
        source, destination = edge.split('->')
        graph[source].append(destination)
 
    distances = {}
    for node in graph:
        distances[node] = bfs(graph, node)
 
    try:
        for source, dests in distances.items():
            for destination, distance in dests.items():
                if source == destination:
                    continue
                table.put_item(
                    Item={
                        'source': source,
                        'destination': destination,
                        'distance': distance
                    }
                )
 
        return {
            'statusCode': 200,
            'body': json.dumps('Successfully stored graph in DynamoDB')
        }
    except:
        return {
            'statusCode': 400,
            'body': json.dumps('Error saving the graph')
        }

This Lambda function will:

Parse the graph.
Use Breadth-First Search (BFS) to calculate the shortest distances from each city to every other city.
Store the distances in DynamoDB.

You can trigger this Lambda function using AWS API Gateway, which will allow you to send HTTP POST requests with graph data.

Step 2: Create a Chatbot with AWS Lex

Next, we’ll set up a chatbot using AWS Lex. Lex allows us to create conversational interfaces that understand natural language input. Our chatbot will ask users for two cities and return the shortest distance between them.

Configure Lex to recognize utterances like:

"What is the distance from Chicago to Springfield?"
"Find distance from Urbana to Lafayette."

Lex will extract the city names using slot types (AMAZON.US_CITY), which ensures that the chatbot recognizes valid city names.

Here’s an example Lambda function linked to Lex to query DynamoDB for the stored distances:

import json
import boto3
from boto3.dynamodb.conditions import Key
 
def lambda_handler(event, context):
    source = event['currentIntent']['slots']['source']
    destination = event['currentIntent']['slots']['destination']
 
    dynamodb = boto3.resource('dynamodb')
    table = dynamodb.Table('mp3_db')
 
    response = table.query(
        KeyConditionExpression=Key('source').eq(source) & Key('destination').eq(destination)
    )
 
    if response['Items']:
        distance = response['Items'][0]['distance']
    else:
        distance = "unknown"
 
    return {
        "dialogAction": {
            "type": "Close",
            "fulfillmentState": "Fulfilled",
            "message": {
              "contentType": "PlainText",
              "content": f"The distance from {source} to {destination} is {distance}."
            },
        }
    }

Step 3: Integrating Lambda with Lex

Once you’ve created your chatbot, you’ll need to integrate the chatbot’s fulfillment with the Lambda function. To do this:

In your Lex console, navigate to the intent.
Under the Fulfillment section, specify the Lambda function you’ve created for fetching distances.

Step 4: Adding AWS Cognito for User Authentication

To make your chatbot publicly accessible, you'll need to configure AWS Cognito Identity Pools. This step ensures secure interaction with your Lex bot. Follow the official AWS guide to complete the setup.

Step 5: Implementing A*

While BFS is simple and effective for unweighted graphs, A* is more efficient for graphs where we can estimate the cost to the destination using a heuristic function.

Here’s how you can implement A*:

import heapq
 
def a_star(graph, start, goal, heuristic):
    frontier = [(0, start)]  # priority queue of (cost, node)
    came_from = {start: None}
    cost_so_far = {start: 0}
 
    while frontier:
        current_cost, current_node = heapq.heappop(frontier)
 
        if current_node == goal:
            break
 
        for neighbor in graph[current_node]:
            new_cost = cost_so_far[current_node] + 1  # all edges have weight 1
            if neighbor not in cost_so_far or new_cost < cost_so_far[neighbor]:
                cost_so_far[neighbor] = new_cost
                priority = new_cost + heuristic(neighbor, goal)
                heapq.heappush(frontier, (priority, neighbor))
                came_from[neighbor] = current_node
 
    return came_from, cost_so_far
 
# Example heuristic function (using Manhattan distance for simplicity):
def heuristic(node, goal):
    # Use a heuristic to estimate distance between node and goal
    return abs(ord(goal[0]) - ord(node[0]))

In A*:

We maintain a priority queue of nodes to explore, prioritized by their estimated total cost (current cost + heuristic).
The heuristic function helps guide the search toward the goal by estimating the distance to the destination.

Conclusion

By following these steps, you'll have a fully functional chatbot that calculates distances between cities and returns them via natural language interaction. Additionally, using A* for more efficient pathfinding in larger graphs will improve performance.

Happy coding!