My Facebook Privacy Settings

There has been a lot of talk in the news about Facebook and their privacy/security settings. Here is how I have set up my account to make sure only certain people can see certain parts of my Facebook profile.

Step 1 - Create Friend Lists

All of the privacy settings are based on which lists of people can see which parts of your profile, so the first step is to create those lists. The two lists we want to create now are:

• Full Access: used for your friends that can see all of your profile.
• No Access: used for the "friends" that you don't want to see anything on your page

Everyone who falls between these two lists will just get "default" access, and we don't need to create a list for them since they are part of your "all friends" list.

To create a list, click on "Friends" on the right side


Then click on "+ Create a List," give it a name and pick which people you want in the list.

Step 2 - Set Up Privacy

Go to the privacy settings. Then choose "Custom" and then "Customize Settings"

For each item that you want to restrict (I do all of them), select the drop down, and choose "Custom"



Then say "Specific People" and choose the "Full Access" list (or whatever you called it)

You can choose what you want each group to see. If you only want the "Full Access" people to see something, do what I mentioned above.

If you want all of your friends except the "No Access" group, do this:

Note: if you say "Everyone" that is everyone in the world, not just your friends.

Repeat this for all the items under "Things I share," "Things others share," and "Contact information."

Step 3 - Protect your pictures

Privacy for your photos is set up per album. Go to this link to change the privacy settings for each album.

Step 4 - Preview your changes

One useful tool Facebook provides is allowing you to see your profile as your friends see it. Go back to the privacy setting in step 2 and click the button at the top labeled "Preview My Profile." Click that and you will be able to type in a friend's name and see what they will see of your profile. Try it with people in your new lists.


If you see something that doesn't look right, go back and update your privacy settings.

Summary

This should be enough to get you started. If you want to be more specific, just create more than two friend lists. For example, I have a "Work People" list that can see my employers and education, but most of those people aren't in the "Full Access" list so they can't see all my pictures.

If you have any questions, let me know.

Read more...

Route Finding Code

I uploaded the full source-code for the Route Finding Problem and the Touring Problem.

Source Code (box.net)

Read more...

Extending to Traveling Salesman Problem

My next step in my A.I. investigation was to extend the route-finding problem to do a touring problem. This is basically a simplified traveling salesman problem where you pick a starting node and have to visit each node one time.

This turned out to be pretty easy with the code I already had. I first created a new interface called Goal with just one method:

public interface GoalInterface {
  public boolean goalMet(State currentState);
}

For the existing route finding problem, I moved the goalTest method to an implementation of this interface:

@Override
public boolean goalMet(State currentState) {
  return currentState.getCurrentNode().getNodeName()
          .equalsIgnoreCase(goalNode.getNodeName());
}

Note that the constructor for this goal takes in the goalNode

Then I just updated the RouteFindingProblem to take a Goal (described below) instead of an goalNode.

The new signature for solve:

public Path solve(final Node initialNode, final GoalInterface goal) { }

And instead of calling the goalTest method, I just call goal.goalMet(). At this point the initial route-finiding problem produces the same results and all the tests still pass.

For the touring problem, I just had to create a new goal. The goalMet() method just checks if every node has been visited by calling this method:

private boolean isEveryNodeVisited(final State currentState) {
  boolean tourComplete = true;
  final List<Action> currentPathActions = currentState.getCurrentPath()
          .getActions();
  final Set<Node> currentlyVisitedNodes = new HashSet<Node>();
  for (Action nextPathAction : currentPathActions) {
      currentlyVisitedNodes.add(nextPathAction.resultOfAction(allNodes));
  }

  // make sure all nodes were visited
  for (Node nextNode : allNodes) {
      if (!currentlyVisitedNodes.contains(nextNode)
              && !nextNode.getNodeName().equalsIgnoreCase(
                      initialNode.getNodeName())) {
          tourComplete = false;
          break;
      }
  }
  return tourComplete;
}

A couple things about this. First, it is not very efficient, but for my testing that is not a big deal. Next, I had to add an extra check for the initialNode since the path that is stored in currentState has a list of actions after the initialNode, but does not include the initialNode.

The last thing I had to do was simplify the map. Since my map of Romania had a few branches that had only one route, there was no way to visit each city only one time. I just "trimmed" the branches and ended up with these segments:

segments = [
      new Segment(start:"Arad", end:"Zerind", cost:75),
      new Segment(start:"Arad", end:"Sibiu", cost:140),
      new Segment(start:"Arad", end:"Timisoara", cost:118),
      new Segment(start:"Bucharest", end:"Fagaras", cost:211),
      new Segment(start:"Bucharest", end:"Pitesti", cost:101),
      new Segment(start:"Craiova", end:"Drobeta", cost:120),
      new Segment(start:"Craiova", end:"Pitesti", cost:138),
      new Segment(start:"Craiova", end:"Rimnieu Vilcea", cost:146),
      new Segment(start:"Drobeta", end:"Mehadia", cost:75),
      new Segment(start:"Fagaras", end:"Sibiu", cost:99),
      new Segment(start:"Lugoj", end:"Mehadia", cost:70),
      new Segment(start:"Lugoj", end:"Timisoara", cost:111),
      new Segment(start:"Oradea", end:"Sibiu", cost:151),
      new Segment(start:"Oradea", end:"Zerind", cost:71),
      new Segment(start:"Pitesti", end:"Rimnieu Vilcea", cost:97),
      new Segment(start:"Rimnieu Vilcea", end:"Sibiu", cost:80)
  ];

Then I ran these tests in Groovy:

//make sure each node results in a path
nodes.each {assert problem.solve(it, new TouringGoal(it, nodes)) != null}
//check a couple paths
assert 1327 == (problem.solve(findNode(nodes, "Arad"), new TouringGoal(findNode(nodes, "Arad"), nodes))).getPathCost();
assert 1294 == (problem.solve(findNode(nodes, "Sibiu"), new TouringGoal(findNode(nodes, "Sibiu"), nodes))).getPathCost();

And finally I did a test to display the results in Groovy:

Node testNode = findNode(nodes, "Bucharest");
Path resultPath = problem.solve(testNode, new TouringGoal(testNode, nodes));
//display the results
println("Shortest tour from " + testNode.toString());
if(resultPath == null){
  println("No route found");
} else {
  for (Action nextAction : resultPath.getActions()) {
      println(nextAction.toString());
  }
}

With the results:

Shortest tour from In(Bucharest)
Go(Pitesti)(101)
Go(Rimnieu Vilcea)(97)
Go(Craiova)(146)
Go(Drobeta)(120)
Go(Mehadia)(75)
Go(Lugoj)(70)
Go(Timisoara)(111)
Go(Arad)(118)
Go(Zerind)(75)
Go(Oradea)(71)
Go(Sibiu)(151)
Go(Fagaras)(99)

Let me know if you have any questions or suggestions on improvements!

Update 7/27/10: Uploaded the source code.

Read more...

Route Finding Applied

Now that I implemented a simple route-finding agent, I thought I would try to apply it to a real-world situation: the shortest route to my office.

I created a new map that looks like this:
My house is at node "P" and work is node "A." The weights are based on the distance and speed limits and are basically the amount of time in minutes * 10 (just to get some rounded numbers).

To my surprise, the shortest route is not the route I typically take to work. The path ended up being:

P -> O -> N -> M -> L -> K -> J -> I -> D -> C -> B -> A

I will have to try this new route on the way to work on Monday!

This does not take into account things like stoplights, which I'm sure will have an effect on the overall time.

Read more...

Adding Segments

I made a small update to my previous solution to the problem-solving agent. The developer in me hated the duplicate "code" of when I defined the nodes. For example, when I defined that Arad was 75 units from Zerind, I also had to define that Zerind was 75 units from Arad. For this example that was not huge, but it could lead to errors.

Here is what it was:

nodes = [
   createNode("Arad", ["Zerind":75, "Sibiu":140, "Timisoara":118]),
   ...
   createNode("Zerind", ["Oradea":71, "Arad":75])
];

To make it a little less error-prone, I added the idea of a "segment." Now I just have to define each segment one time instead of twice. It looks like this:

segments = [
   new Segment(start:"Arad", end:"Zerind", cost:75),
   new Segment(start:"Arad", end:"Sibiu", cost:140),
   new Segment(start:"Arad", end:"Timisoara", cost:118),
   new Segment(start:"Bucharest", end:"Fagaras", cost:211),
   new Segment(start:"Bucharest", end:"Giurgiu", cost:90),
   new Segment(start:"Bucharest", end:"Pitesti", cost:101),
   new Segment(start:"Bucharest", end:"Urziemi", cost:85),
   new Segment(start:"Craiova", end:"Drobeta", cost:120),
   new Segment(start:"Craiova", end:"Pitesti", cost:138),
   new Segment(start:"Craiova", end:"Rimnieu Vilcea", cost:146),
   new Segment(start:"Drobeta", end:"Mehadia", cost:75),
   new Segment(start:"Eforie", end:"Hirsova", cost:86),
   new Segment(start:"Fagaras", end:"Sibiu", cost:99),
   new Segment(start:"Hirsova", end:"Urziemi", cost:98),
   new Segment(start:"Iasi", end:"Neamt", cost:87),
   new Segment(start:"Iasi", end:"Vaslui", cost:92),
   new Segment(start:"Lugoj", end:"Mehadia", cost:70),
   new Segment(start:"Lugoj", end:"Timisoara", cost:111),
   new Segment(start:"Oradea", end:"Sibiu", cost:151),
   new Segment(start:"Oradea", end:"Zerind", cost:71),
   new Segment(start:"Pitesti", end:"Rimnieu Vilcea", cost:97),
   new Segment(start:"Rimnieu Vilcea", end:"Sibiu", cost:80),
   new Segment(start:"Urziemi", end:"Vaslui", cost:142),
];

Then in the Segment class I created a method to convert a list of Segments into a list of Nodes so I just needed to do this in my groovy script to have the same information I did before:

nodes = Segment.convertSegmentsToNodes(segments);

I also had to move the createActionList and createNode methods into the Segment class, which helped clean up my groovy script.

Read more...

Groovy/Java Problem Solving Agent

Today I'm going to look at implementing a simple problem-solving agent using Java and Groovy. This is based on chapter 3 in my old A.I. textbook, "Solving Problems By Searching." I am going to tackle the route-finding problem which takes a number of cities in Romania (p 68 on Google Books) with paths between them with the goal of having to find the shortest route between any two cities.

Let's get started. First, I created a few simple Java classes to represent a Node (a city), an Action (go from one node to another), a Path (list of Actions that have gotten me where I am now), and a State (what Node am I at and how did I get here). These classes are not that interesting, but here are the basics of each one without the implementations:

Node:

public class Node {
  public Node(String nodeName, List availableActions) {  }
  public String getNodeName() {  }
  public List getAvailableActions() {  }
}

Action:

public class Action {
  public Action(String actionName, int stepCost) { }
  public Node resultOfAction(List availableNodes) {
      //if I execute this action, where am I?
  }
  public int getStepCost() { }
}

Path:

public class Path {
  public void addAction(Action action) {  }
  public int getPathCost() {  }
  public List<action> getActions() {  }
  public Path clone() {  }
}

State:

public class State {
  public State(Node currentNode, Path currentPath, List closedNodes){ }
  public Node getCurrentNode() { }
  public Path getCurrentPath() { }
  public List getClosedNodes() { }
}

I also created a couple simple data structures to represent a Queue and a Stack (called SimpleQueue and SimpleStack). When searching for the solution, I needed to decide if I wanted to do a Depth-first search (using a Stack - LIFO) or a Breadth-first search (Queue - FIFO). I decided to use a depth-first search since I tried to be a little smart about only finding solutions that are shorter than any others I've already found. By doing a depth-first search, I tried to expand the search tree until I found a solution, then went back and tried to find other solutions that were shorter.

Now is where the actual searching happens. I created another Java class called RouteFindingProblem. I'll describe each part of that class starting with the "solve" method:

solve:

public Path solve(final Node initialNode, final Node goalNode) {
  if (initialNode.getNodeName().equalsIgnoreCase(goalNode.getNodeName())) {
      resultPath = new Path(new Action("Stay" + initialNode.getNodeName(), 0));
  } else {
      resultPath = null;
      lowestPathCost = Integer.MAX_VALUE;

      // find the paths
      doSearch(initialNode, goalNode);
  }
  return resultPath;
}

This is the entry point into the solving logic. It will return the shortest path from the initialNode to the goalNode. The first check is just to make sure the initialNode is not the same as the goalNode. If it is I am done and I'll just create a new "stay" action. Next (in the else statement) I initialize some variables and then call doSearch.

doSearch:

private void doSearch(final Node initialNode, final Node goalNode) {
  stateDataStructure = new SimpleStack<State>();

  // create the first state
  stateDataStructure
      .put(new State(initialNode, new Path(), new ArrayList<node>()));

  while (!stateDataStructure.isEmpty()) {
      if (goalTest(stateDataStructure.peek(), goalNode)) {
          handleGoalReached(stateDataStructure.get());
      } else {
          successorFunction(stateDataStructure.get(), goalNode);
      }
  }
}

I basically create the first state and add it to the stack. Then I keep going until the stack is empty. If I've reached the goal, then I just check if this is the shortest path (in handleGoalReached). If I haven't reached the goal, then I find all the successors of this state and add them to the Stack.

The last interesting piece of code in this class is the successorFunction method. I don't love this name, but that is what they call it my book. It would be more appropriately called "addSubStates" or something.

successorFunciton:

private void successorFunction(final State currentState, final Node goalNode) {
  // make a copy of the closed list for each sub state
  final List<Node> cloneClosedList = cloneClosedList(currentState
      .getClosedNodes());
  cloneClosedList.add(currentState.getCurrentNode());

  // for each action after this, add it to the queue
  for (Action nextAction : currentState.getCurrentNode()
      .getAvailableActions()) {
      final Node nextNode = nextAction.resultOfAction(nodes);
      // make sure I haven't already checked this node (circular)
      if (!cloneClosedList.contains(nextNode)) {
          final Path clonePath = currentState.getCurrentPath().clone();
          clonePath.addAction(nextAction);

          // only add the next state if the current path is
          // lower than any previous paths
          if (clonePath.getPathCost() < lowestPathCost) {
              stateDataStructure.put(new State(nextNode, clonePath,
                  cloneClosedList));
          }
      }
  }
}

In a nutshell, this just finds the next set of states and adds them to the stack.

All that is left is to set up the actual data and run some tests. To do this I used Groovy, partly because I thought it would be easier to script some of the setup and tests, and partly because I don't know much about Groovy so this was a chance for me to learn more about it.

First off, I created some helper methods (closures) to use in my Groovy script.

createActionList = {actionMap ->
  List<Action> actions = new ArrayList<Action>();
  actionMap.each {place,cost -> actions.add(new Action("Go(" + place + ")", cost)) };
  return actions;
}

createNode = {nodeName, actionMap ->
  return new Node("In(" + nodeName + ")", createActionList(actionMap));
}

findNode = {nodeList, nodeToFind ->
  for(nextNode in nodeList){
      if(nextNode != null && nextNode.getNodeName().equalsIgnoreCase("In(" + nodeToFind + ")")){
          return nextNode;
      }
  }
}

Then I set up all the nodes in this problem (cities in Romania):

nodes = [
  createNode("Arad", ["Zerind":75, "Sibiu":140, "Timisoara":118]),
  createNode("Bucharest", ["Pitesti":101, "Fagaras":211, "Giurgiu":90, "Urziemi":85]),
  createNode("Craiova", ["Drobeta":120, "Rimnieu Vilcea":146, "Pitesti":138]),
  createNode("Drobeta", ["Mehadia":75, "Craiova":120]),
  createNode("Eforie", ["Hirsova":86]),
  createNode("Fagaras", ["Sibiu":99, "Bucharest":211]),
  createNode("Giurgiu", ["Bucharest":90]),
  createNode("Hirsova", ["Urziemi":98, "Eforie":86]),
  createNode("Iasi", ["Vaslui":92, "Neamt":87]),
  createNode("Lugoj", ["Timisoara":111, "Mehadia":70]),
  createNode("Mehadia", ["Lugoj":70, "Drobeta":75]),
  createNode("Neamt", ["Iasi":87]),
  createNode("Oradea", ["Zerind":71, "Sibiu":151]),
  createNode("Pitesti", ["Rimnieu Vilcea":97, "Craiova":138, "Bucharest":101]),
  createNode("Rimnieu Vilcea", ["Sibiu":80, "Craiova":146, "Pitesti":97]),
  createNode("Sibiu", ["Oradea":151, "Arad": 140, "Fagaras":999, "Rimnieu Vilcea":80]),
  createNode("Timisoara", ["Arad":118, "Lugoj":70]),
  createNode("Urziemi", ["Bucharest":85, "Vaslui":142, "Hirsova":98]),
  createNode("Vaslui", ["Urziemi":142, "Iasi":92]),
  createNode("Zerind", ["Oradea":71, "Arad":75])
];

Update:See this post about defining Segments instead of Nodes.

Then I set up some Groovy unit tests to make sure this was working as expected:

RouteFindingProblem problem = new RouteFindingProblem(nodes);

//same initial/goal
assert 0 == (problem.solve(findNode(nodes, "Arad"), findNode(nodes, "Arad"))).getPathCost();
//neighbors
assert 75 == (problem.solve(findNode(nodes, "Arad"), findNode(nodes, "Zerind"))).getPathCost();
assert 75 == (problem.solve(findNode(nodes, "Zerind"), findNode(nodes, "Arad"))).getPathCost();
//2 hops
assert 215 == (problem.solve(findNode(nodes, "Zerind"), findNode(nodes, "Sibiu"))).getPathCost();
//one end to the other
assert 698 == (problem.solve(findNode(nodes, "Oradea"), findNode(nodes, "Eforie"))).getPathCost();

Finally I did a test to print out the path from one end of Romania to the other:

Path resultPath = problem.solve(findNode(nodes, "Oradea"), findNode(nodes, "Eforie"));
//display the results
println("Shortest path from " + findNode(nodes, "Oradea").toString() + " to " + findNode(nodes, "Eforie").toString());
for (Action nextAction : resultPath.getActions()) {
  println(nextAction.toString());
}

The output is:

Shortest path from In(Oradea) to In(Eforie)
Go(Sibiu)(151)
Go(Rimnieu Vilcea)(80)
Go(Pitesti)(97)
Go(Bucharest)(101)
Go(Urziemi)(85)
Go(Hirsova)(98)
Go(Eforie)(86)

Next Steps:
This is just one simple problem-solving agent. I tried to make this fairly generic, but to implement the other examples from the book (sliding block puzzle, 8-queens problem, touring problem), it will take a little work.


Update 7/27/10: Uploaded the source code.

Read more...

A.I. Reference Book

While doing my graduate work, I took a class on Artificial Intelligence. It was very interesting though I haven't had much time until now to look into it more. I am looking back though the textbook: Artificial Intelligence: A Modern Approach (2nd Edition).



There is a limited version of the book at Google Books here.

Read more...

Geek vs. Nerd vs. Dork

I am a geek. Not to be confused with a "nerd," "dork," or "dweeb." If you are confused, check out the Venn diagram at this site.

Read more...