Currently I am in an MS program with a research concentration in theoretical/formal computer science (mostly spatial and temporal knowledge representation and reasoning). However, I find myself getting more attracted towards artificial intelligence and robotics. When applying for a PhD do you think my MS research is a good concentration for a PhD research in Artificial Intelligence and Robotics? (I have taken courses that cover both artificial intelligence and robotics during the MS)
As always, it's going to come down to your application and your history.
From the sounds of it, you'll be a very strong candidate based on your theory background -- You just need to find the right school / supervisor that will see how to help you pursue those interests. Look for schools with good AI programs.
Knowing the research focuses at the CS Department in the University of Alberta, I think you'd have a good shot there with a number of supervisors, both in reinforcement learning and in machine learning.
Really though, it's going to come down to a demonstration that you can do the research, via your reference letters, CV, etc.