decision_control/slotplanner.cc

   1 /*
   2 This file is part of I am car.
   3
   4 I am car is free software: you can redistribute it and/or modify
   5 it under the terms of the GNU General Public License as published by
   6 the Free Software Foundation, either version 3 of the License, or
   7 (at your option) any later version.
   8
   9 I am car is distributed in the hope that it will be useful,
  10 but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12 GNU General Public License for more details.
  13
  14 You should have received a copy of the GNU General Public License
  15 along with I am car. If not, see <http://www.gnu.org/licenses/>.
  16 */
  17
  18 #include <algorithm>
  19 #include <cmath>
  20 #include <list>
  21 #include <queue>
  22 #include "slotplanner.h"
  23
  24 ParallelSlot::ParallelSlot()
  25 {}
  26
  27 // getter
  28 std::vector<std::vector<RRTNode *>> &ParallelSlot::cusp()
  29 {
  30         return this->cusp_;
  31 }
  32
  33 float ParallelSlot::DH() const
  34 {
  35         return this->DH_;
  36 }
  37
  38 PolygonObstacle &ParallelSlot::slot()
  39 {
  40         return this->slot_;
  41 }
  42
  43 float ParallelSlot::slotHeading()
  44 {
  45         float y0 = this->slot().bnodes()[0]->y();
  46         float x0 = this->slot().bnodes()[0]->x();
  47         float y3 = this->slot().bnodes()[3]->y();
  48         float x3 = this->slot().bnodes()[3]->x();
  49         float dy = y0 - y3;
  50         float dx = x0 - x3;
  51         return atan2(dy, dx);
  52 }
  53
  54 SlotSide ParallelSlot::slotSide()
  55 {
  56         if (!this->slotSide_) {
  57                 float y0 = this->slot().bnodes()[0]->y();
  58                 float x0 = this->slot().bnodes()[0]->x();
  59                 float y1 = this->slot().bnodes()[1]->y();
  60                 float x1 = this->slot().bnodes()[1]->x();
  61                 float y3 = this->slot().bnodes()[3]->y();
  62                 float x3 = this->slot().bnodes()[3]->x();
  63                 if (sgn((x1 - x3) * (y0 - y3) - (y1 - y3) * (x0 - x3)) < 0)
  64                         this->slotSide_ = LEFT;
  65                 else
  66                         this->slotSide_ = RIGHT;
  67         }
  68         return this->slotSide_;
  69 }
  70
  71 SlotType ParallelSlot::slotType()
  72 {
  73         if (!this->slotType_) {
  74                 float d1 = EDIST(
  75                         this->slot().bnodes()[0],
  76                         this->slot().bnodes()[1]
  77                 );
  78                 float d2 = EDIST(
  79                         this->slot().bnodes()[1],
  80                         this->slot().bnodes()[2]
  81                 );
  82                 if (d1 > d2)
  83                         this->slotType_ = PERPENDICULAR;
  84                 else
  85                         this->slotType_ = PARALLEL;
  86         }
  87         return this->slotType_;
  88 }
  89
  90 // setter
  91 void ParallelSlot::DH(float dh)
  92 {
  93         this->DH_ = dh;
  94 }
  95
  96 // other
  97 void ParallelSlot::fip()
  98 {
  99         // see https://courses.cs.washington.edu/courses/cse326/03su/homework/hw3/bfs.html
 100         // RRTNode.s() works as iteration level
 101         std::queue<BicycleCar *, std::list<BicycleCar *>> q;
 102         std::queue<BicycleCar *, std::list<BicycleCar *>> empty;
 103
 104         // TODO add init nodes
 105         // for now just copy fpose()
 106         bool left = false; // right parking slot
 107         float di = -1;
 108         // new pose for parallel parking to right slot
 109         float tnx;
 110         float tny;
 111         float nx;
 112         float ny;
 113         // temporary tnx is angle
 114         tnx = this->slotHeading() + M_PI;
 115         if (this->slotSide() == RIGHT)
 116                 tnx -= M_PI / 4;
 117         else
 118                 tnx += M_PI / 4;
 119         nx = this->fposecenter()->x() + 0.01 * cos(tnx);
 120         ny = this->fposecenter()->y() + 0.01 * sin(tnx);
 121         BicycleCar *CC = new BicycleCar(nx, ny, this->slotHeading());
 122         // move left by car width / 2
 123         tnx = CC->x() + CC->width() / 2 * cos(CC->h() + M_PI / 2);
 124         tny = CC->y() + CC->width() / 2 * sin(CC->h() + M_PI / 2);
 125         // move down
 126         nx = tnx - (CC->length() + CC->wheelbase()) / 2 * cos(CC->h());
 127         ny = tny - (CC->length() + CC->wheelbase()) / 2 * sin(CC->h());
 128         if (this->slotSide() == LEFT) {
 129                 std::cerr << "left PS" << std::endl;
 130                 left = true;
 131                 di = 1;
 132                 // move right by car width / 2
 133                 tnx = CC->x() + CC->width() / 2 * cos(CC->h() - M_PI / 2);
 134                 tny = CC->y() + CC->width() / 2 * sin(CC->h() - M_PI / 2);
 135                 // move down
 136                 nx = tnx - (CC->length() + CC->wheelbase()) / 2 * cos(CC->h());
 137                 ny = tny - (CC->length() + CC->wheelbase()) / 2 * sin(CC->h());
 138         }
 139         BicycleCar *B = new BicycleCar(nx, ny, CC->h());
 140         this->DH(di * 0.01 / CC->out_radi());
 141         BicycleCar *c;
 142         int i = 0;
 143         c = B->move(CC, -i * di * 0.01 / CC->diag_radi());
 144         while (!this->slot().collide(c->frame())) {
 145                 q.push(c);
 146                 c = B->move(CC, -i * di * 0.01 / CC->diag_radi());
 147                 i += 1;
 148         }
 149         delete c; // not in q and collide
 150         // BFS
 151         while (!q.empty()) {
 152                 c = q.front();
 153                 q.pop();
 154                 if (this->isInside(c)) {
 155                         goto createcuspandfinish;
 156                 } else if (c->s() < 9) {
 157                         BicycleCar *cc = this->flnc(c);
 158                         cc->s(c->s() + 1);
 159                         cc->bcparent(c);
 160                         q.push(cc);
 161                 } else {
 162                         delete c; // not in q and collide
 163                 }
 164         }
 165         std::swap(q, empty);
 166         return;
 167 createcuspandfinish:
 168         std::vector<RRTNode *> cusp;
 169         while (c) {
 170                 cusp.push_back(new RRTNode(c->x(), c->y(), c->h()));
 171                 c = c->bcparent();
 172         }
 173         std::reverse(cusp.begin(), cusp.end());
 174         this->cusp().push_back(cusp);
 175         std::swap(q, empty);
 176 }
 177
 178 void ParallelSlot::fipr(BicycleCar *B)
 179 {
 180         // TODO for right parallel parking also
 181         // it's only for lpar scenario now
 182         std::vector<RRTNode *> cusp;
 183         cusp.push_back(new RRTNode(B->x(), B->y(), B->h()));
 184         // just copied from fip()
 185         int di = 1;
 186         if (this->slotSide() == LEFT)
 187                 di = -1;
 188         this->DH(di * 0.01 / B->out_radi());
 189         BicycleCar *c;
 190         c = this->flncr(B);
 191         while (this->slot().collide(new RRTNode(c->lfx(), c->lfy(), 0))) {
 192                 cusp.push_back(new RRTNode(c->x(), c->y(), c->h()));
 193                 BicycleCar *cc = this->flncr(c);
 194                 cc->s(c->s() + 1);
 195                 delete c;
 196                 c = cc;
 197         }
 198         cusp.push_back(new RRTNode(c->x(), c->y(), c->h()));
 199         std::reverse(cusp.begin(), cusp.end());
 200         this->cusp().push_back(cusp);
 201 }
 202
 203 BicycleCar *ParallelSlot::flnc(BicycleCar *B)
 204 {
 205         // TODO find last not colliding
 206         // for now just copy flast()
 207         RRTNode *cc;
 208         if (int(B->s()) % 2 == 0) {
 209                 cc = BicycleCar(B->x(), B->y(), B->h()).ccr();
 210         } else {
 211                 cc = BicycleCar(B->x(), B->y(), B->h()).ccl();
 212         }
 213         float di = -1;
 214         if (this->slotSide() == LEFT)
 215                 di = 1;
 216         BicycleCar *p;
 217         int i = 1;
 218         p = B->move(cc, i * di * this->DH());
 219         while (!this->slot().collide(p->frame())) {
 220                 delete p;
 221                 i += 10;
 222                 p = B->move(cc, i * this->DH());
 223         }
 224         i -= 10;
 225         p = B->move(cc, i * di * this->DH());
 226         while (!this->slot().collide(p->frame())) {
 227                 if (this->isInside(p)) {
 228                         i += 1;
 229                         break;
 230                 }
 231                 delete p;
 232                 i += 1;
 233                 p = B->move(cc, i * this->DH());
 234         }
 235         delete p;
 236         return B->move(cc, (i - 1) * this->DH());
 237 }
 238
 239 BicycleCar *ParallelSlot::flncr(BicycleCar *B)
 240 {
 241         // TODO find last not colliding
 242         // for now just copy flast()
 243         RRTNode *cc;
 244         if (int(B->s()) % 2 == 0)
 245                 cc = BicycleCar(B->x(), B->y(), B->h()).ccr();
 246         else
 247                 cc = BicycleCar(B->x(), B->y(), B->h()).ccl();
 248         BicycleCar *p;
 249         int i = 1;
 250         p = B->move(cc, i * this->DH());
 251         while (
 252                 !this->slot().collide(p->frame())
 253                 && this->slot().collide(new RRTNode(p->lfx(), p->lfy(), 0))
 254         ) {
 255                 delete p;
 256                 i += 10;
 257                 p = B->move(cc, i * this->DH());
 258         }
 259         i -= 10;
 260         p = B->move(cc, i * this->DH());
 261         while (!this->slot().collide(p->frame())) {
 262                 if(!this->slot().collide(new RRTNode(p->lfx(), p->lfy(), 0))) {
 263                         i += 1;
 264                         break;
 265                 }
 266                 //if (this->DH() < 0 && p->lfx() >= 0) {
 267                 //        i += 1;
 268                 //        break;
 269                 //}
 270                 delete p;
 271                 i += 1;
 272                 p = B->move(cc, i * this->DH());
 273         }
 274         delete p;
 275         return B->move(cc, (i - 1) * this->DH());
 276 }
 277
 278 RRTNode *ParallelSlot::fposecenter()
 279 {
 280         return this->slot().bnodes().front();
 281 }
 282
 283 bool ParallelSlot::flast(
 284         RRTNode *P,
 285         bool right,
 286         int il,
 287         std::vector<RRTNode *> &cusp
 288 )
 289 {
 290         BicycleCar *B = new BicycleCar(P->x(), P->y(), P->h());
 291         RRTNode *cc;
 292         if (right)
 293                 cc = BicycleCar(B->x(), B->y(), B->h()).ccr();
 294         else
 295                 cc = BicycleCar(B->x(), B->y(), B->h()).ccl();
 296         BicycleCar *p;
 297         int i = 1;
 298         p = B->move(cc, i * this->DH());
 299         while (!this->slot().collide(p->frame())
 300                         && (
 301                                 (this->DH() > 0 && p->x() <= 0)
 302                                 || (this->DH() < 0 && p->x() >= 0)
 303                         )) {
 304                 delete p;
 305                 i += 10;
 306                 p = B->move(cc, i * this->DH());
 307         }
 308         i -= 10;
 309         p = B->move(cc, i * this->DH());
 310         while (!this->slot().collide(p->frame())
 311                         && (
 312                                 (this->DH() > 0 && p->x() <= 0)
 313                                 || (this->DH() < 0 && p->x() >= 0)
 314                         )) {
 315                 if (this->DH() > 0 && p->rfx() <= 0 && p->rrx() <= 0) {
 316                         i += 1;
 317                         break;
 318                 }
 319                 if (this->DH() < 0 && p->lfx() >= 0 && p->lrx() >= 0) {
 320                         i += 1;
 321                         break;
 322                 }
 323                 delete p;
 324                 i += 1;
 325                 p = B->move(cc, i * this->DH());
 326         }
 327         delete p;
 328         p = B->move(cc, (i - 1) * this->DH());
 329         if (this->DH() > 0 && p->rfx() <= 0 && p->rrx() <= 0) {
 330                 cusp.push_back(p);
 331                 return true;
 332         } else if (this->DH() < 0 && p->lfx() >= 0 && p->lrx() >= 0) {
 333                 cusp.push_back(p);
 334                 return true;
 335         } else if (il < 8) {
 336                 cusp.push_back(p);
 337                 return this->flast(p, !right, il + 1, cusp);
 338         }
 339         return false;
 340 }
 341
 342 void ParallelSlot::fpose()
 343 {
 344         bool left = false; // right parking slot
 345         float di = -1;
 346         BicycleCar *CC = new BicycleCar(
 347                 this->fposecenter()->x(),
 348                 this->fposecenter()->y() - 0.01,
 349                 this->slotHeading()
 350         );
 351         BicycleCar *B = new BicycleCar(
 352                 CC->x() - CC->width() / 2,
 353                 CC->y() - (CC->length() + CC->wheelbase()) / 2,
 354                 this->slotHeading()
 355         );
 356         if (this->slot().bnodes()[0]->x() > this->slot().bnodes()[1]->x()) {
 357                 left = true;
 358                 di = 1;
 359                 delete B;
 360                 B = new BicycleCar(
 361                         CC->x() + CC->width() / 2,
 362                         CC->y() - (CC->length() + CC->wheelbase()) / 2,
 363                         this->slotHeading()
 364                 );
 365         }
 366         this->DH(di * 0.01 / CC->out_radi());
 367         BicycleCar *p;
 368         int i = 0;
 369         p = B->move(CC, -i * di * 0.01 / CC->diag_radi());
 370         while (!this->slot().collide(p->frame())) {
 371                 std::vector<RRTNode *> tmpcusp;
 372                 tmpcusp.push_back(new BicycleCar(p->x(), p->y(), p->h()));
 373                 if (this->flast(p, left, 0, tmpcusp)) {
 374                         this->cusp().push_back(tmpcusp);
 375                         return;
 376                 }
 377                 i += 1;
 378                 delete p;
 379                 p = B->move(CC, -i * di * 0.01 / CC->diag_radi());
 380         }
 381 }
 382
 383 BicycleCar *ParallelSlot::getFP()
 384 {
 385         float x = this->slot().bnodes()[3]->x();
 386         float y = this->slot().bnodes()[3]->y();
 387         float h = this->slotHeading();
 388         float nx;
 389         float ny;
 390         if (this->slotSide() == LEFT) {
 391                 nx = x + BCAR_WIDTH / 2 * cos(h + M_PI / 2);
 392                 ny = y + BCAR_WIDTH / 2 * sin(h + M_PI / 2);
 393         } else {
 394                 nx = x + BCAR_WIDTH / 2 * cos(h - M_PI / 2);
 395                 ny = y + BCAR_WIDTH / 2 * sin(h - M_PI / 2);
 396         }
 397         x = nx + ((BCAR_LENGTH - BCAR_WHEEL_BASE) / 2 + 0.01) * cos(h);
 398         y = ny + ((BCAR_LENGTH - BCAR_WHEEL_BASE) / 2 + 0.01) * sin(h);
 399         return new BicycleCar(x, y, h);
 400 }
 401
 402 bool ParallelSlot::isInside(BicycleCar *c)
 403 {
 404         bool inside = true;
 405         RRTNode *tmpn;
 406         tmpn = new RRTNode(c->lfx(), c->lfy(), 0);
 407         if (!this->slot().collide(tmpn))
 408                 inside = false;
 409         delete tmpn;
 410         tmpn = new RRTNode(c->lrx(), c->lry(), 0);
 411         if (!this->slot().collide(tmpn))
 412                 inside = false;
 413         delete tmpn;
 414         tmpn = new RRTNode(c->rrx(), c->rry(), 0);
 415         if (!this->slot().collide(tmpn))
 416                 inside = false;
 417         delete tmpn;
 418         tmpn = new RRTNode(c->rfx(), c->rfy(), 0);
 419         if (!this->slot().collide(tmpn))
 420                 inside = false;
 421         delete tmpn;
 422         return inside;
 423 }
 424
 425 struct SamplingInfo ParallelSlot::getSamplingInfo()
 426 {
 427         struct SamplingInfo si;
 428         BicycleCar *CC = new BicycleCar(
 429                 this->fposecenter()->x(),
 430                 this->fposecenter()->y() - 0.01,
 431                 this->slotHeading()
 432         );
 433         si.x = this->slot().bnodes()[0]->x();
 434         si.y = this->slot().bnodes()[0]->y();
 435         si.r = CC->diag_radi();
 436         si.h = this->slotHeading() - acos(EDIST( // TODO generalize
 437                 this->slot().bnodes()[0],
 438                 this->slot().bnodes()[1]
 439         ) / BCAR_LENGTH);
 440         return si;
 441 }