When we lived in town I had a small hedge along the sidewalk going to the driveway--all herbs. Chives, oregano, sage, rosemary, all perennials. Since I used them so often the hedge never got much more than 8" tall, but it was pretty and smelled great!
I think filling in the gap with a perennial herb is a great idea,
(By the way, your patio area is gorgeous!)