Assemble a robot. It can be anything with wheels that moves: either you build one from scratch, you convert a toy or get a dedicated platform. Ideally it should be able to keep pace with a running human.

Personally I go for 4WD rovers, where each wheel has its own motor (with reducer), and a strong H-Bridge capable of higher current. The movement must be differential, to allow on spot turn around. 

A microcontroller board and a dual h-bridge is needed to control movement. 

The code I prepared is for Atmel microcontrollers, specifically the ATMEGA328. Go for that if you like, as the code on Github is all set for that. 

Additionally you can add a serial Bluetooth adapter , that is to be able to control the robot using your Android phone as a remote. Source code for that is on Github too.

Build at least two ultrasonic receivers (PCB design files are on Github), and place them at the frond of the robot.

 If you want to increase it's sensing capabilities, add more of these, and adjust the code accordingly. You're pretty much done at this step, congrats on building a robo-dog!